Applied on their careers page and got the call.
Interviewer was from Zurich. He was very friendly and helpful.
Was given 1 month to study.
Question was a spinoff of "Kth Largest element in a data stream"
You are given a collection(basically a class) which has 2 functions.
-
addNum
(adds a number given as parameter to the stream) -
findLargest
(finds the kth largest in the stream, here k is given as parameter in the stream)
Clarifying questions asked:
❓Does the stream contain duplicates?
➡️Yes
❓How big can the stream be?
➡️It will fit in memeory
❓ Discussed a few testcases with him then.
➡️like [1,2,3,4,5,6,8,8,8,9,10] Here, the 1st largest is 10, 2nd largest is 9 and 3rd, 4th, and 5th largest is 8 and then so on to understand the handling of 8.
❓ What is k is greater than length of data stream or can k be negative?
➡️Return None and not -1 as numbers in the stream can be negative
Approach Discussed:
- Use Binary Search for finding index of insertion and insert(TC: O(log N))
For the time complexity, I made a mistake as insert in Python takes O(N) but I said O(1), so overall it is O(N) and not O(logN). - findLargest(use len of num and subract the kth value from it and return, here the interviewer said you are open to use 0 based indexing and 1 based indexing, k is given as a parameter), I used 1 based indexing.
The interviewer agreed and said sounds good.
I started coding it and was done in the next 10 minutes.
Follow up 1: What if k == len(stream): I dry ran the code and showed that it worked fine and returned the lement of the 0th index.
Discussion: Since, add takes O(N) and findLargest takes O(1), can we make add a little light and findLargest a bit heavy time complexity wise, I was thinking but then he gave the hint of queue like a priority queue. I did say yes, then we can do add in O(log N) and return kth largest in O(1)
Follow Up 2:
Return kth largest everytime, like basically it was like:
add(2) #[2]
add(3) #[3,2]
findLargest() #returns 3
add(4) #[4,3,2]
findLargest() #returns 3
findLargest() #return 2
I replied with we can take a pointer and keep it increasing after we get an element, once it goes out of length of stream, we return -1 and he was satisfied.
After this the time was over and we ended the interview after I asked him his day to day life at Google.
Do you guys think? Will I be selected for onsite interviews?
My personal review: Lean Hire/Hire.