How to Crack a Google Coding Interview - An Ex-Googler’s Guide

Key Takeaways

hey everyone my name is YK and I'm a former software developer at Google in this video I'm going to walk you through the process I would personally use to get through an actual coding intimate question from Google here I'm going to use a question from Google as an example but you'll be able to use the same process to get to programming interviews with any company and I chose a relatively simple problem here so that I can explain the whole process quickly now here's the problem you're given an array of integers for example 1 3 2 4 which represents a number this array represents 1324 and the problem is writing a function that takes this array and as 1/2 this number so your function if you're given this array should return 1 3 to 5 which represents 1325 now how would I solve this problem let me walk you through the whole process I would personally use to solve this problem step by step step 1 start with clarifying questions and a high-level discussion one of the clarifying questions you could have asked here is could this array be empty and the interviewer might say no it cannot be empty and you could also ask can we always assume that each element of this array is always an integer between 0 and 9 now let's say it is indeed the case so each element of this array is always an integer between 0 & 9 and you might ask a few more questions to clarify all the assumptions you have once you feel like you have enough information to start solving this problem you should start with a high-level discussion in this stage just explain the ideas you have in concept first without using too much code and it's important not to start coding right away especially for a more complex problem so that you don't waste time writing code on a solution that doesn't work in the end for example for this problem you might say something like what this problem would be easy if the given array ends with a number that's not nice for example for this array 1 3 2 4 because in that case we can just add 1 to the last item and we get 5 and then copy over everything else if the last integer is 9 so if we had for example 1 3 2 9 instead of 1 3 2 4 then we need to change this number to 0 and then carry 1 to the next number and keep repeating this process until we have nothing to carry at that point we can copy over everything else and we are done the only tricky case for this problem is when we have something like 999 or 999 in the given array because then the new array will need to be 1 0 0 0 so from our function we'll need to create a new array with a different length a length for here and then we turn this new array for this problem or maybe if the problem is more complex I'd recommend that you list out a few potential approaches you could use to solve this problem for example for this particular problem you might say well I'm thinking about using either an iterative approach with a for loop or with a recursive approach with recursion especially for a more complex problem it's really important to list out a few potential solutions you have in mind because it's rare for you to get to the optimal solution with your first idea if you're confident enough that your first idea is the optimal solution then go for it but if not list out a few potential solutions before you start coding now on to step 2 choose your approach and start coding here in this example you might say something like well I think the iterative solution is a good solution so let me start coding with that or if you're not 100% sure if your solution is correct or optimal you could also say something like well I think the EDA resolution is good should I start coding with that just by asking that question should I start coding you're communicating more with the interviewer which is always good in a coding interview and you're also making sure that you're going in the right direction just by asking that question now I'm going to switch to a Google Doc to explain this idea just like a phone interview but if you're using a whiteboard to solve this problem in an in-person interview it's the same idea I'm going to use pseudocode to explain my solution here but in the real interview usually you're supposed to use a real language whether it's Python Java or JavaScript the first thing I would recommend that you do with this type of problem is to write your function header in this case it might look like this define add one or a function with the input given array and explain the input and the output for this function you might say something like this function is going to take the given array as the input and the output will be the new array for example if you're given 1 3 4 as the given array the output from this function will be 1 3 5 and you might say instead of modifying the given array directly I'm going to create a new instance of an array and then return that instead this is necessary in case for example when the given array is 9 9 9 because in that case we'll need to return an array whose length is different from the original array after that start writing your solution as you explain the code and this process will be iterative in nature so you might write a little bit of code and then you might go back to thinking a little bit about your solution and then write your code a little bit more and my recommendation here is to always think with specific examples in mind as you write code so for example with this particular problem you might say something like well the first thing we'll need to do is we'll need to create a new instance of an array and then I'm going to create it with the length being the same as the original array for example 1 3 4 and if we have an edge case like this where we have 999 or 999 then we'll need to create a new array again at the end of the function and then we turn that instead so to create a new instance of an array with the same length as the original one in suit code we might write something like this result will be the new array and then we're initializing a new array an integer array let's say with the length being the same as given arrays length and another thing we'll need to take care of is the carry so for example if we had 1 9 9 and then if we initialize this array for example to 0 0 0 then when we look at this number then we'll know that the last digit in the new number should be 0 and they will need to carry 1 to this number and we'll know that the second number should be 0 and then carry 1 again and we'll know that this number should be 2 and to keep track of if we need to carry anything we'll just initialize a new variable called carry and then we'll set it to 1 because we need to add 1 to the last digit and with the example we saw earlier this example we saw that we need to iterate over each item or each digit from right to left so we're going to do that with a for loop with for i from given array length minus 1 down to 0 again with this example given array dot length will be 3 so given array dot length minus 1 will be 2 which will point to this item or that's the index for this item and then I will go from 2 to 1 to 0 so that we can iterate over each digit and we'll need to add the carry either 1 or 0 to the current item the current digit will do that with some eCos given array square brackets I the current digit plus carry and if this sum is equal to 10 we'll set care to one because we'll need to carry one to the next number and if some is not equal to ten or else we'll set carried to zero and the current digit in the new number or result of square brackets I for example if we're examining this number right here we're talking about this digit that number or result square brackets I should be some mod 10 and this is just to say if the sum is ten we should have zero end result and if the sum is less than 10 we should have the same number as some in the result for example if the sum is 5 5 mod 10 will be just 5 now this takes care of most cases except for this case when all the digits are 9 in that case what we would have is we'd have 0 0 0 as the current result and the carry at that point will be 1 because of course when we are examining this number the carry there is 1 and 1 plus 9 is 10 and they will have carry equals to 1 so after the for loop if carry is still equal to 1 that means we have a case like this where all the digits are 9 we're going to take care of that by creating a new array and assigning it to result with a new integer array given array the length plus 1 so we're creating a new array here with the length being one item longer than the given array and assuming that this initializes an array with all the elements being 0 we'll just need to set the first item to one and that way we'll be able to take care of this case when all the items are 9 after that just return result and that's my solution now step 3 check your solution and discuss performance such as time and space complexity I've copied over the code we had earlier right here to check your solution you should walk through your code line by line using maybe a few weeks simples and make sure it works and here's how I would do it let's think of one example for example one two nine nine as the input given array then we can just look over this code line by line carry will be 1 and then result at the beginning will be let's say 0 0 0 0 because this is just an array of the same length as the original array after that we're going to run a for loop for I from given array length minus 1 given array dot length is 4 so I will start at 3 and it'll go to 2 to 1 to 0 when I is equal to 3 we'd be examining these elements and the total will be given array square brackets 3 which is 9 plus carry which is 1 so the total will be 10 and since total is 10 carry will still be 1 and the current item of result or real result square brackets I or result square brackets 3 in this case will be total mod of 10 which is 0 and we go to the next value of I which is 2 we're going to repeat the same thing and the current value of result will be 0 carry will still be 1 and then I becomes 1 when I is equal to 1 total this time will be given a race car buckets I which is 2 plus carry which is 1 and so total will be 3 and since total is not equal to 10 Kerry will be 0 and then result will be 3 mod 10 which is 3 so the current value of result will be 3 and since at that point Kerry will be 0 total will be just given a race car buckets I plus carry but we can just ignore Kerry since its darrell and total here will be 1 and Kerry will still be 0 and the current item in the result array or results car bracket 0 will be total mod 10 which is 1 after that since Carrie is not equal to one it's still zero we're going to return results which is one three zero zero so that's how you can go through one example to be sure you can go through a few other examples too for example 999 or just zero now in this particular example the space complexity and the time complexity are fairly simple let's first think about time complexity because we go through this entire array at most once or twice when we create a new array in the case of 9 9 9 the time complexity is Big O of n where n is the number of items in the given array the space complexity will be big-oh of n as well because the most we create the most space we create is for the new array which is Big O of N and that's the framework I would personally use for cracking a googol coding interview or coding interviews from any other company for that matter if you like this video I would also recommend my course on udemy 11 essential coding into big questions and that's the framework I would personally use for cracking a Google coding interview or coding interviews from any other company for that matter if you like this video I would also recommend my course on udemy 11 essential coding into big questions in which I cover eleven of the most essential coding interview questions to master for your next coding interview in case you're interested in taking a course I put a discount code below in the description or our thanks for watching this video and I'll see you soon