Google SRE-2 | Warsaw | Phone Screen Round

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.

Edit: Got selected!