Rank frequent events with a bounded heap
Input {words:list[str],k:nonnegative integer}. Return up to k unique words by descending frequency, breaking ties alphabetically.
Examples
Frequency: {"words":["b","a","b","c","a","b"],"k":2} → ["b","a"]Tie: {"words":["z","a","m"],"k":2} → ["a","m"]Compare approaches
Baseline approach
Sort all unique words even when the requested result is small. It is simple and often appropriate when k is large.
Time: O(n + u log u), excluding string comparison lengths · Space: O(u + k)
from collections import Counter
def solve(input):
counts = Counter(input["words"])
return sorted(counts, key=lambda word: (-counts[word], word))[:input["k"]]Refined approach
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.
Time: 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. · Space: O(u + k), excluding input.
from collections import Counter
from heapq import nsmallest
def solve(input):
counts = Counter(input["words"])
return nsmallest(input["k"], counts, key=lambda word: (-counts[word], word))Common traps
- Taking the first k items from Counter does not rank by frequency.