Google L4 Phone screening
Summary
I had a phone screening interview with Google for an L4 position, where I was challenged with a problem involving stream processing and triplet formation.
Full Experience
During my Google L4 phone screen, I was presented with an interesting data structure problem. The task involved continuously processing a stream of integers. For each new number, I needed to determine if a triplet could be formed from the current set of numbers in memory such that the difference between the maximum and minimum of the three numbers was at most a given value d. If such a triplet was found, it had to be immediately removed and returned. This required careful consideration of how to efficiently manage the numbers in memory and quickly identify valid triplets as they arrived.
Interview Questions (1)
You are given a stream of integers arriving one by one, and an integer d. At any time, you may form a triplet of numbers from the stream if the difference between the maximum and minimum of the three numbers is at most d. Once a triplet is formed, those three numbers must be immediately removed from memory and cannot be reused in any other triplet.
Design a data structure that processes the stream online:
- When a new number arrives, insert it into memory.
- If any valid triplet can be formed, remove it immediately and return it.
Continue this process for the entire stream.