google logo
Google· SRE-2

Google SRE-2 | Warsaw | Phone Screen Round

Location
Warsaw
Posted
15 Apr 2025
357 reads

Summary

I had a phone screen for an SRE-2 role at Google in Warsaw. The interviewer was friendly, and I was given a problem based on 'Kth Largest element in a data stream', which I successfully solved and discussed follow-up questions. I was later selected for onsite interviews.

How it went

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!

Questions asked (1)

  1. 01

    Kth Largest Element in a Data Stream (Custom Class)

    Data Structures & Algorithms

    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

How they prepared

Was given 1 month to study.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!