Define stable top-K ties before optimizing

Clarify the observable contract

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.

Walk through the verified program

b first appears at zero, a at one and c at two. All three finish with count two, so their first positions decide the tie. Taking two returns b:2,a:2 and excludes c despite its equal score. The separate zero case yields zero items. The dictionary stores First once and preserves it when incrementing Count.

Preserving old.First on every count update is essential. Replacing it with the latest occurrence would move b behind another tied key and implement a last-seen policy instead. The output therefore tests more than counts: it tests whether the metadata used for ties survives repeated events.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;

string[] events = { "b", "a", "c", "a", "b", "c", "d" };
var counts = new Dictionary<string,(int Count,int First)>(StringComparer.Ordinal);
for(int i=0;i<events.Length;i++) { string key=events[i]; counts[key]=counts.TryGetValue(key,out var old) ? (old.Count+1,old.First) : (1,i); }
int k=2;
var top=counts.OrderByDescending(x=>x.Value.Count).ThenBy(x=>x.Value.First).Take(k).Select(x=>x.Key+":"+x.Value.Count);
Console.WriteLine(string.Join(",",top));
Console.WriteLine("zero:" + counts.OrderByDescending(x=>x.Value.Count).Take(0).Count());

Account for time, storage and allocations

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.

Review assumptions and likely defects

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 stable library sort preserves source order only for equal comparison keys. Here the explicit first-position comparison is the meaningful rule; relying on how the dictionary happens to enumerate would obscure it. Distributed input also needs a shared ordering token before first seen has an unambiguous cross-producer meaning.

Practice one: discriminate edge cases

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.

Use three tied candidates with k equal to two so the boundary forces a decision. Testing only k equal to the number of keys cannot detect a wrong tie victim. Also include a higher-frequency late key so the primary count rule demonstrably overrides first occurrence.

Practice two: defend an extension

Design a streaming or distributed ranking requirement. Decide whether first seen means local arrival, a globally assigned sequence number or a timestamp with another tie breaker. Explain why merging partial counts alone cannot recover a global first-occurrence policy.

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.

Evaluate correctness and interview reasoning

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.