Engineering practice · 30 MIN

Rank frequent events with a bounded heap

Choose a data structure according to the requested output size.

Count events, then keep the best k candidates. A bounded heap is useful when k is much smaller than the number of distinct events. Python heapq.nsmallest accepts a key function; negative frequency sorts higher counts first, and the word breaks ties. The implementation may choose sorting when k is large. The exercise’s result must be deterministic.

Treat the function as a small service: define a contract, maintain an invariant, and test the boundaries.

Read the example

from collections import Counter
print(Counter(["a", "b", "a"])["a"])

2

Your challenge

Input {words:list[str],k:nonnegative integer}. Return up to k unique words by descending frequency, breaking ties alphabetically.

Solution cost: O(n + u log k) when 1 < k < u; O(n + u log u) when sorting all u unique words. String comparisons also depend on word length. time · O(u + k), excluding input. space

Common trap

Taking the first k items from Counter does not rank by frequency.

Further reading: Python heapq