[Google] My onsite Interview Experience

Hi guys,
Today, I want to share my experience interviewing with Amazon for L4 position. In total, I have 5 interviews, which was from 10AM-3:30PM.

  1. First Round: Technical question
    The question is quite vague. The interviewer asked me to implement a logging system. This system supposed to keep track and print out logging file in order of time. The log comes in with start time and an end time. You are supposed to implement 2 function, start (given id, start time): keep track of start time, stop (given id, stop time): print out the logs that are done if there are no log started earlier than those but have not finished. This stop gave me a lot of trouble. In order to visualize this easier, let us go through an example:
    log 1, start at 1 -> print out nothing
    log 2, start at 2 -> print out nothing
    log 2, end at 3 -> because log 1 starts before log2 but not finish
    log 1, stop at 4 -> print out 1 and 2
    So, the invariant here is that if the stop function print out a given id, then all the left (the one that starts earlier) have to finished already. In addition, you might have to print some of the log that starts after our given id, but also finished before our given id. I think my big mistake is not differentiate those 2 cases, and try to tackle them at the same time, and try to solve it optimally. In the interview, my solution was not correct. I could see that mile away. After done with the interview, I try to redo it. Here is my implementation with comment, please try it yourself before checking it out. Also, I am not sure mine is totally correct and optimal
Summary
class Log:
    def __init__(self):
        self.arr = []
        self.highesIndexDone = None
    def start(self,id,startTime):
        self.arr.append([id,startTime,None])
    def stop(self,id,stopTime):
        self.arr[id][2] = stopTime
        res = []      
        if self.highesIndexDone == None:
            if self.arr[0][0] == id:
                res.append(id)
                self.highesIndexDone = 0
                 # we traverse toward the right until we hit something is not done
                 for i in range(1,len(self.arr)):
                    nextId,nextStart,nextStop = self.arr[i]
                    if nextStop != None:
                        res.append(nextId)
                        self.highesIndexDone = i
                    else:
                        # we are done
                        break
            return res
        else:
            # we know our index at isDone is the highest possible
            # we check if this index +1 is equal to our id index
            index = self.binarySearch(self.highesIndexDone,id)
            if self.highesIndexDone+1 == index:
                res = [id]
                # we scan up to the first one that does not have endTime
                for i in range(index+1,len(self.arr)):
                    nextId,nextStart,nextStop = self.arr[i]
                    if nextStop!=None:
                        res.append(nextId)
                        self.highesIndexDone = nextId
                    else:
                        break
            
            return res
        
def binarySearch(self,start,id):
    stop = len(self.arr)-1
    while start+1<stop:
        mid = (start+stop) //2
        if self.arr[mid][0] == id:
            return mid
        elif self.arr[mid][0] > id:
            stop = mid
        else:
            start = mid
    if self.arr[start][0] == id:
        return 0
    if self.arr[stop][0] == id:
        return stop
  1. Second Round: Technical question
    The interviewer starts of by asking me to rank several algorithm run time, which basically boil down to ranking multiplication matrix and insertion sort, and binary search in sorted array. He then asked me how to prove that multiplication in 2D matrix are always slower than insertion sort, which I reason based on the output size (2D matrix requires n^2 to display or parse through).
    Then, the main question is that, given a sorted array, and 3 number a,b,c where a,b ,c are coefficient of a quadratic function (f(x) = ax^2+bx+c). Return an array of element from the original array, which is computed by the quadratic function, and the array have to be sorted. The idea here is that we are given a sorted array, hence we need to try how to utilize that into our quadratic function. In a sense, for any consecutive pair of x1, x2 in our sorted array, we know that x1 <= x2. How can we tell about f(x1) and f(x2). Basically, we are interested in this equation: g(x1,x2) = (f(x1)-f(x2))/(x1-x2). Apparently, if this is monotonic, then we are good. Here, we can recognize this is quite similar to the derivative of our f(x), which boils down to 2a+b. And, if we look at the graph of any quadratic, it is basically a parabola. You can see that our function will decrease until x = 2a+b, and then increase, or vice versa. Henceforth, you can compute all the value , find the breaking point, seperate it into 2 list and then merge them. You can achieve such things in O(n).
  2. Round 3: Behavioral question
    Suppose to be a behavioral round, my interviewer asked me about a coding problem. Given a 2D array of 0 and 1. You start off at index 0,0. You can move to anywhere in the grid, every grid you choose, the grid and all of the neighbors to the grid flip themselves (1 to 0 and 0 to 1). Neighbor here means that all adjacent that share same value as your current grid. For example:
    1 1 1 0
    1 1 0 0
    1 0 0 1
    0 1 1 1
    You start at 0,0, so flipping the grid and all the neigbor becomes
    0 0 0 0
    0 0 0 0
    0 0 0 1
    0 1 1 1
    You have to find the fewest number of move to flip all to 1.
    So the behavioral round became a technical round, I was going through it with him for like 15 mins until he realized that it was supposed to be a behavior. The last 15 mins was kind of awkward of behavioral questions haha.
  3. Fourth Round: Technical question
    It is a variant version of Word Ladder. The different here is that it is all number, and you cant have a snake through it. You have to find the most common prime number in the matrix. It is quite standard, just go through each grid, then read to the right, left, top, bottom, diagonal, check if it is prime and store the count. I do not think we can do better than O(n^3) for this. He then ask for other approach, in which we can just find all subsequence for each row, col, diagonal and test for prime.
  4. Fifth Round: Technical question
    You are given a bench that is represented by an array of 0 and 1. 0 means empty seat, 1 means occupy.
    a. You need to find a seat that maximize the distance to the nearest person. This version is basically this problem on leetcode.
    b. The interviewer then extend to what if there are several people want to use this method, how to find it faster. I presented a heap implement that store the largest group of 0.
    c. Extend it again, now we can remove people. I have no optimal answer here. I just provide a linear solution to add and remove people.

Overall, the problems are really cool and very practical. I can see the second problem being generalize so that it is a polynomial function. Then, we only need to find the changing direction (by solving the differentiate equation), and do a k-merge sorted list. The thing is, if the degree is greater than the size of the array, then it is not worth it anymore. Why is that?
Let denote n be the size of our array, and k be the degree of our polynomial function.
If we just compute the function, and sort it. Then it takes O(nlogn)
If we differentiate our polynomial , we have a degree of k-1, which give us k interval in worst case scenario. This k interval provides k sorted array, where using our heap implement to merge, provide us O(nlogk) time.
Therefore, if k is larger than n, it is not worth it to consider this approach. However, we need to consider this in real life. The problem arise when you have a sorted array of data, and have a polynomial function (maybe trying to predict habit based on our data which is age), how often does our polynomial function have higher degree than the size of our data? Not usually right?
Therefore, overall, it is usually the case that we can try our approach and make it more efficient. However, what is the caveat, did we glimpse over something? Yes, solving a k -1 linear equation is not simple. Although we can use computer to approximate it, we might have some error. How big is the error, how much it can affect us, it totally depends on the break point and the data we have.

Oh wow, I talk a lot. I think this is it for the day. I almost forgot about the problem 1. Luckily, I have the coded it right after my interview and save it on my computer :slight_smile: Btw, I have dedicate github repo for company question here I do not know if it can be helpful to anyone, but I hope you guys can learn what type of question those companies ask. Again, good luck to everyone and happy lunar new year :slight_smile:

P.S: I failed the Google interview, and it took them 1 month to tell me that :frowning: I feel really sad but I will try again in the future.

7 Likes