41 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?

Leave a Reply

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