Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Google SWE coding round, one question the whole time. It looked like a list merging problem but the edge cases kept stacking up and I underestimated how much state management was involved.

Questions Asked (1)

Design an iterator class that merges two ordered streams (favorites and photos), yields all items from the first stream before the second, skips any IDs present in a blocked list, and never emits the same ID twice. Must support hasNext and next.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I got the basic structure down pretty fast, two pointers, drain the first list, then the second.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the requirements and edge cases first, then design a stateful iterator that lazily pulls from each stream in order, using a hash set to track emitted IDs and skip blocked or duplicate IDs. Implement hasNext and next with careful handling of stream exhaustion and blocking, and discuss trade-offs between eager vs lazy processing and memory usage.

Pro tip: Emphasize that the iterator should be lazy to handle large or infinite streams efficiently, and that using a hash set for seen IDs is acceptable but discuss memory implications and potential alternatives like Bloom filters for massive scale.

1. Clarify requirements and edge cases

Ask about stream characteristics (sorted? infinite? duplicates within a stream?), blocked list size, and whether IDs are integers or strings. Confirm that all favorites must be emitted before any photos, and that duplicates across streams are skipped.

2. Design the iterator state

Maintain references to both streams, a set of seen IDs, a set of blocked IDs, and a flag indicating which stream is currently active. Ensure the iterator can lazily fetch the next valid item.

3. Implement hasNext and next

In hasNext, advance through the current stream until a valid ID is found or the stream is exhausted, then switch to the next stream if needed. In next, return the pre-fetched valid ID and update state.

4. Handle edge cases and complexity

Consider empty streams, all items blocked, duplicates within a stream, and memory usage of the seen set. Discuss time complexity (amortized O(1) per next) and space complexity (O(n) for seen set).

5. Discuss trade-offs and optimizations

Compare eager vs lazy processing, and propose alternatives for the seen set (e.g., if IDs are sorted, use a last-seen pointer; for massive scale, consider probabilistic data structures).

Key Points to Mention

Lazy evaluation to support large or infinite streams and avoid unnecessary computation.
Use of a hash set to track emitted IDs for O(1) duplicate detection, with discussion of memory trade-offs.
Blocked list can be stored in a hash set for O(1) lookup, and should be checked before emitting.
Order guarantee: all favorites must be emitted before any photos, requiring a state machine to switch streams only when the first is exhausted.
Handling of duplicates within a single stream (e.g., if the stream itself contains repeated IDs).
Amortized time complexity per next() and overall space complexity, including the seen set.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.