Coding interviews
Reveal answer and reasoning
Return the k most frequent keys, breaking equal counts by the position where each key first appeared. A first-seen tie is different from lexical order and from an unspecified heap order. Zero returns no results; this fixture uses a nonnegative k. The implementation counts all events and requests an ordered prefix rather than assuming a small output makes the whole algorithm O(k).
Runtime selection optimizations do not remove the count map. Specify the ranking as an ordered pair: count descending and first input position ascending. That is a total order for distinct keys because two different keys cannot have the same first position in this sequential input. The number k limits the returned list, not the amount of input that must be inspected.
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.
When discussing a heap optimization, distinguish building counts from selecting among those counts. A small heap reduces only the selection phase, and all unique-key counts still occupy storage. The heap priority must make the worst retained candidate removable, including which equal-count key is worse under first-seen ordering.
What a strong answer covers
- Return the k most frequent keys, breaking equal counts by the position where each key first appeared.
- Preserving old.First on every count update is essential.
- With n events and u keys, counting uses expected O(n) dictionary work and O(u) retained counts.
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.