Coding interviews
Reveal answer and reasoning
For distributed aggregation, carry both total count and the minimum globally meaningful sequence token for each key. Merge counts by addition and first tokens by minimum, then apply the same final ranking. If producers cannot supply a comparable global token, redefine the tie rule instead of presenting local arrival order as a global fact.
With n events and u keys, counting uses expected O(n) dictionary work and O(u) retained counts. A fully sorted baseline costs O(u log u) comparisons. The actual LINQ ordered-prefix pipeline can use runtime-specific partial selection; its operator contract is not a promise of that exact comparison bound. It still examines and buffers candidates rather than using O(k) total memory. An explicit size-k heap offers a different selection design with O(u log k) heap work after counting.
PriorityQueue does not promise FIFO behavior for equal priorities. A stable sort cannot rescue a wrong explicit secondary key, and relying on incidental dictionary order hides the contract. Negative k should be explicitly rejected or documented rather than inheriting an accidental library behavior.
A good interview solution begins with the stable tie contract, implements the clearest correct ranking and states counting and buffering costs while qualifying runtime selection optimizations. Optimization follows only if input and k bounds justify it. The tested event sequence creates three equal-frequency candidates but retains two, making the boundary observable. Explain how an explicit secondary key differs from incidental collection order and from equal-priority heap behavior.
A senior discussion considers which ordering evidence survives partitioned aggregation. It does not claim that reducing output to k entries also reduces counting memory or makes a global arrival order appear automatically.
What a strong answer covers
- For distributed aggregation, carry both total count and the minimum globally meaningful sequence token for each key.
- With n events and u keys, counting uses expected O(n) dictionary work and O(u) retained counts.
- PriorityQueue does not promise FIFO behavior for equal priorities.
Common pitfall
PriorityQueue does not promise FIFO behavior for equal priorities. A stable sort cannot rescue a wrong explicit secondary key, and relying on incidental dictionary order hides the contract. Negative k should be explicitly rejected or documented rather than inheriting an accidental library behavior.
Follow-up questions
- Change the event order without changing final counts and predict the new top two. Hint: change only first occurrence positions. Then test k larger than the number of keys and decide whether returning all keys is the desired public behavior.
- Which metadata must partial aggregators retain to preserve a globally defined first-seen tie rule?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.