49 thoughts on “How to: Work at Google — Example Coding/Engineering Interview

  1. The value that you are looking for should be the complement (ie sum-value), not the value itself, great video btw

  2. At time =15m44s,
    I want to know about complexity of
    line —— if(comp.find(value)! —–
    As I implement same in C,
    When I compare/Find like function as —comp.find(value) —
    Complexity of this step becomes N i.e. for finding element in compliment array,
    so total complexity becomes N^2 in worst case , average it less than N^2.

  3. I know its been a year since the posting of the video, but I have a question regarding your code which I hope you would explain it to me. First, I like the way you solved this problem. This is really clever solution. second, My Question is: why do you need ( != comp.end ) part? Since you are checking before inserting, its always going to check only the previously added complements. Thanks for posting the video anyway.

  4. Wow great job brilliant solution. but am worried what if the set was of the form [1, 2, 2 ,4]. This algorithm seems to dual mostly on two digits that sum to the required number and not when we have multiple digits.

  5. I haven't watched video yet, just problem. First idea I am having to solve it is, looping through all the numbers in array, then using binary search to find the needed matching pair to make 8, if any. This will be O(nlogn). Let's how I did. Will continue watching video now.

  6. For the last part of the problem, wouldn't it have made sense to do some pruning along the way for repeat complements? It would have bumped up the running time, but for a case where space seems to be the main issue, that would be a necessary sacrifice for the problem if you were to not use multiple systems, wouldn't it?

  7. def checkSum(myList, s):
    start, end = 0, -1
    for x in range(len(myList)):
    k = myList[start]+myList[end]
    if k == s:return True
    else:
    if k > s:end -= 1
    elif k < s:start += 1
    return False

    print(checkSum([1, 4, 4, 5], 8))

    #did that in 2 minutes in python, before he writes the code…!

  8. That noob man…
    He crossed the first array 2:00 …. and then asked her if he could repeat the elements… and they are making 'example interview'

  9. I thought of a better solution than him that would work in half the time of what he is proposing.
    So does this mean I can get an internship??

  10. Can someone explain the scaling part to me.
    19:47 “If my set fits in memory, but my whole input doesn’t fit in memory then I can just process it in chunks. I chunk it, I just put it in a set, and accumulate it in the set.” –This doesn’t make sense to me. If the whole input doesn’t fit in memory, in worst case the set would contain the whole input (the case where there is no sum) sooo the set wouldn’t fit in memory either? Even if your processing the data in chunks, you would be using the same set for every chunk which doesn’t work?

  11. I still have something unclear, if the whole input does not fit in memory, and you are processing it parallel, and adding the compliments in the list, when we reach towards the end (while merging) it will still be big enough not to work on a single computer, what am I missing? Is it that the merged array would be built and stored in a distributed manner?

  12. I'm asking this VERY seriously: Is this a joke???
    I'm learning programming for no more than one year now, and I solved it as he's final result maybe 5 minutes into this video.
    So regarding my question, is this really the level required for Google?
    Is that in general considered a high-level programming?

  13. I didn't understand something about the solution to "throwing in the wrench." How is it better than the first solution (brute force where for each element, you check each other element). He says it's linear, but I don't see that. You loop n times through the for loop, but in each iteration, you have to find an element in comp. To find whether a value is in comp, you need to check each element of comp. So the time complexity would surely be O(sum(r from r=1 to n)) = O(n^2). Unless I'm misunderstanding something about how unordered_set and how comp.find(value) works (I don't really know how they work at all, but I don't see how the complexity of comp.find(value) wouldn't depend on the length of comp)

  14. This question was way too easy. Literally every single google interview question i've seen so far on youtube has been so easy. Is it really this easy

Leave a Reply

Your email address will not be published. Required fields are marked *