Coding interviews
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());
Reveal answer and reasoning
The output lines, in order, are “b:2,a:2”; “zero:0”. 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.
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.
What a strong answer covers
- Exact output: b:2,a:2 | zero:0
- b first appears at zero, a at one and c at two.
- 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.