Google India Engineers in a Mock Coding Interview

hi my name is ashwatha I'm a software engineer at Google I am a Hands-On software engineer involved in coding mainly with Java and C plus plus I also Mentor other engineers and I am involved in design and architecture decisions as well hi I'm swathi I'm a software engineer at Google in today's video we will talk and demonstrate of how a Google engineer approaches an engineering problem so I'll be giving a problem to ashwatha and he'll talk us through the process of solving it and towards the end we'll also look at the positive aspects that he demonstrated through the interview process so ashwatha the question that I'm going to give you today is this I have a collection of numbers and you have to take this collection and find pairs which sum up to the number that I give you okay for example the collection of numbers is one two three nine and you have to find the target 10 okay the pair of numbers which adds up to 10 okay and you could also have a Target like eight which does not unique system with them I have shared this problem as well in the Google Talk okay okay let me ask some clarifying questions and we'll make some notes as we as we go so in this second example that you gave me where the target was eight uh we don't have a pair of numbers in this array that we can that will Advocate on the other other hand the first example is possible so so both of those can happen in in this case Okay uh so how would these numbers be given to me uh for example will these fit into memory is this an array how does this work yes it would be in memory and you can consider an array okay okay and how do we handle duplicate elements here for example if the sum is 8 and there were to be a 4 in the array can I just add 4 to itself and and make it we wouldn't have a number repeating itself at the same index however there could be repeated numbers in the array okay so there may be two force in the array but I wouldn't be able to reuse a four that already exists earlier okay uh can I assume that these are all integers for example can there be a floating Point numbers here can there be negative numbers there could be negative numbers and integers only no floating Point numbers okay that sounds good thank you uh so when I think about this uh the simplest possible solution here is just brute force uh we can use two indices in the array let's call them I and J the I index would iterate through the whole array and the J index would start at I plus 1 and then iterate through the rest of the array that way we avoid any duplicates as we discussed and for each pair of elements we would add them up and we'll see if they add up to the target number that you give me if they do then we have found a pair on the other hand if they don't and we iterate through the whole array for both indices we will know that there is no possible solution to this one it's not very efficient but it should work what's the complexity of the solution this would be quadratic okay um let's think about it better than quadratic the elements are sorted so we should be able to use that as we iterate through the array for example the first element is one here and let's say we are looking for a sum of eight we can think of the complement of one which is seven so we can search for seven in this array since it's already sorted we can do buying research we go to the middle of the array if that element is bigger than 7 we go left otherwise we go right so overfl login complexity for the search itself and we'll repeat it for every element in the array so that would be o of n log n for the whole solution uh this is still not the optimal solution you could just still going linear could you think of something better okay uh let's think about that I'm trying to see if we can bound this problem in some way for example in this example array the last two elements would give me the biggest possible sum since the array is sorted so that would be 3 plus 9 or 12 and the first two elements would give me the smallest sum because again those are the two smallest elements in the array and everything in between is my range of values so if I started with two indices one pointing to the beginning of the array and one pointing to the end of the array let's say we add them so in this case 1 plus 9 is 10. that's bigger than the sum that we are looking for so we would move the the right index towards the left to try and see if we can make the sum smaller that's not the case and if my initial sum is bigger than the target we would move out left index towards the right to see if we can make our sum bigger and we would stop whenever we find a matching pair or whenever the two indices essentially cross over each other in which at which point we know that there is no solution that would be a linear solution I think you like down the problem now sure we can try to code this up uh what's your language actually is C plus plus okay okay sure sure sounds good so I I realize we haven't discussed what to return in this case uh should we just return a Boolean indicating if there is a solution or not or do we want to return the matching page itself uh do you see a problem in returning the matching plan uh not really it should be fairly easy if we find a pair that matches we just return the pair uh if we don't we would have to return a Boolean so we can think of creating some data structure that has a Boolean field indicating whether we found a matching pair or not and then a matching pair it's not very elegant but it's it's doable would be fine okay so let's do that for now I'll start coding uh [Music] okay let's call this as paved with sum and the input is is a vector okay for the array yes Vector is there okay I'm going to call that data in here and then there is an integer which is the sum that you're that you're looking for okay um so I'm going to have two indices uh well let's call one of them low and that starts off as zero and there is another one let's call that high which starts off at the right end of the array okay so what I'm going to do is as long as low is less than High and that in fact that also takes care of the situation where we start start with an empty Vector because what that would mean is low would be zero and high would be -1 so we would never really enter this Loop so we don't have to worry about that edge case here okay so while low is less than high we add up the elements at those two indices so we basically check if data or flow Plus data of high is equal to the sum that you gave me and if it is we can just return true right here if not we keep going so so we do need to adjust the low end High here if the sum of these two elements is bigger than the Target that you gave me will have to decrement high otherwise we'll have to increment low so that's something that we'll have to do to make this easier I'm just going to declare a separate variable that stores that that sum so that I don't have to recalculate every time [Music] okay so if that sum is less than the Target that you gave me if that sum is less than the target then we need to try and make it bigger so I'm going to increment my low and by the time the while loop finishes if you still haven't found a matching pair with written false this should do it through a branch ouch okay let's assume that okay okay so if the collection is not sorted of course this will not work but maybe we can just start it that's of n log n we can sort it initially and then just do the same thing here that would work it wouldn't be linear anymore but it would still be of n log n are we looking for anything faster yeah you could do it faster than a lot okay uh let's think about that so let's go back to the initial idea that we had of iterating through the array picking an element and then looking for its complement if it was sorted we could have used binary search but that go that's not possible here since there is no longer sorted we can do a linear search but that will make the solution quadratic again let's see if we can do something better than that okay so we'll stick with the complements idea so I'm going to write down an example array here so let's still use one two three nine and we'll add one more we'll call it 22. okay and let's say we are looking for a sum of 10 uh I start iterating through the array the initial element is one now I'm looking for a 7. if there is a way I know that I have seen a 7 before then I'll be able to do it uh so in other words I think what we're looking for is a data structure where we can easily look up elements or their complements that we have seen before and then go from there uh and I think that would again be linear so we should be able to do it linearly a hash table might be a good data structure for this okay what would be the key of the hash table that's an interesting question I guess we don't really need a hash table we just want to keep track of what values we have seen here not necessarily map keys to values so we might get away with just a hash set so in C plus plus I think that's an unordered set as we are scanning through the values for each value we we see if we have seen its complement before from our set if we haven't we compute its complement and we add it to the set and then we can keep going it's a little tricky because as we discussed earlier we don't want to repeat elements from the same index so we should take care that we don't add values to the set before we have already checked if its complement was in there but that should be workable and it would still be a linear solution for this how about the collection has Million numbers so if we have millions of numbers would they still fit in memory probably not at this point okay so that would make it harder so if we have a very large set of values maybe we can still consider ranges of value so if the range of these values is bounded in some sense we can take separate sets of values as a break up the whole range into sub ranges and we can use different computers to compute this kind of hash set of complements for different ranges of values so when we scan through the full set of values we'd still need to know which computer to check in to find the complement So It's Tricky but it's absolutely doable do you want to code it at this point sure so in C plus plus for the hash set we'll be using an unordered set of integers in this case it should be called complements I'm going to call it comp because I don't want to type this every time okay so what we'll do is we'll iterate through the values in the input vector in each case we will check if we have already seen its complement so we will say the syntax might be slightly off but the basic idea should be here so we're inserting complements so we'll just just check if in my set of complements we already have this value and if we do we can just return true if not we will compute its complement and essentially add it to our set and I think it's just com dot add and that should be it uh if in in case we don't find any matches we'll return a false at the end so so that should work it's the code itself is fairly simple but let me trace it on an example to make sure that it works so let's use this example array one two three four nine and 22 and let's say our Target is 10. so initially when we start this code when we start the for Loop that I am highlighting here obviously the unordered set is empty to start with we look at the element one we try to find find it in our set we don't find it so we add its complement to the set so it will have a 9 in it at that point um and then we look at the element two uh we see we see if that's in the complement set it's not so we add two's complement as well which is eight uh we'll do the same thing with three's complement and force complement as well right uh so uh and then we get to the element nine we check it in our set it's already here so at that point we have found a matching pair so we are done at this point we'll return true if we were looking for a different Target like eight we would never find its complement in our set so we'll essentially iterate through the whole array and we'll return false so so yes I think this will this will work okay great job thank you [Music] all right so just to recap the interview that we just saw there were a couple of things that you should be aware of while interviewing one is to make sure that you understand the problem right and ask clarifying questions in order to do so ask for the question to be repeated if it helps and also to be written down verbatim so that the question is clear one of the questions that ashwatha asked was about the floating Point integers and that does affect the problem so yes it's a good one to be asked the other thing that you could do is to always think out loud the solution this helps the interviewer understand your thought process and also course correct when required it's also good to ask questions which demonstrate your expertise and also helps to come closer to the solution faster it's always good to brainstorm with your interviewer after all two mindset a problem is always better one thing he did really well was to come up with a simpler solution and articulate it the first solution is not going to be the best and it's not the best for anyone the interviewer will challenge you to do better be more efficient and the idea is to get to the right solution and then code it another great thing that you did really well and I would encourage is to test the solution you can test it with some examples that the interviewer has already given or come up with your own examples and test out the solution another good idea is to always test with the edge cases like in this case we took the example of empty Collections and tested it as an edge case that gives you the confidence that your solution works for all different types of examples just like we saw in this interview do the trade-off analysis of your choices proactively the interview is time bound so manage your time well as you navigate the solution Write Clean and structured code do not over complicated leverage the latest features of the technical language for your advantage and stick to one language only throughout the code best is to do all of these proactively

Channel: Life at Google

Views: 162,142

Keywords: google, life at google, google jobs

Id: 21pmwl0hrME

Length: 15min 29sec (929 seconds)

Published: Thu Jun 22 2023