Mock Interview
Questions: Given a binary search tree, and a range [L, R], find all keys that lie within the range.
Follow-up Question:
Write an iterative approach.
Candidate's Approach
Run a recursive inorder traversal and if the key you are exploring doesn't lie in range, don't go to right.
Interviewer's Feedback
Strong Hire (Coded and interviewer said it works).
Screening Round
Questions:
- Given an array of integers, and you can jump to arr[arr[i]] from arr[i]. Find the minimum cost to reach n-1.
- Given an array of integers representing the height of fences and a paint brush able to make horizontal and vertical strokes. 1 stroke is counted as not lifting the brush from the fence. Find the minimum number of strokes to paint the fence.
Candidate's Approach
- Wrote a DP solution. (Coded and interviewer said, he is fine with the solution and it works).
- If any fence height is 0 then array breaks into two parts at that point. Find the minimum of (max height of each such part, size of that subarray).
Interviewer's Feedback
Strong hire (Coded and interviewer said, he is fine with the solution and it works).
Onsite 1
Questions: Imagine you have an RPC server that produces log of entries and we're analyzing it offline. There are two entries for each call, one when the RPC starts and one when the RPC finishes processing. We’d like to know as soon as possible if there’s an RPC that took too much time / timed out given a threshold.
Follow-up Question:
If multiple requests at the same timestamp. Start and end times are not unique.
Candidate's Approach
Use a list
Interviewer's Feedback
Hire (Coded and interviewer said, he is fine with the solution and it works).
Onsite 2
Questions: Given 12 tiles, each with a color and a number. Find if 4 winning hands exist. 1 winning hand is decided by either all tiles are same (both color and number) or (color is same but numbers are consecutive).
Candidate's Approach
Used backtracking and implemented some pruning. Tried proving that backtracking would always yield the correct answer.
Interviewer's Feedback
Not hire (Coded and interviewer said she is not sure if it works well).
Onsite 3
Questions: Make an ad server, that given some ads with content and a score, build an insert ad and serveAd (this serves best ad). The higher the score, the better the ad. We have to take care to not serve the same ad consecutively.
Follow-up Question:
Now each ad also contains a delay (let's say 5, possibly different for each ad) with it which represents we can't serve that ad until the next 5 ads. The previous question was a case with delay as 1 for each ad.
Candidate's Approach
Use a max heap of scores and store the ad served previously. After serving an ad, insert that in the new heap as insert the delay + ads served so far. Before serving any ad, check if any of the ads from the second heap can be inserted back in heap1 (basically the ads whose delay period has ended).
Interviewer's Feedback
Not hire (Coded and interviewer said, she is fine with the solution and it works).
Googlyness and Leadership
Questions: Some questions about how I deal with my managers, my juniors. How would I deal with stressful situations, etc.
Candidate's Approach
N/A
Interviewer's Feedback
Hire.