Top-K frequent elements (stream-aware)

Expected question

"Given an array of integers, return the k most frequent elements. Order among ties can be arbitrary unless specified."

Variant forms

• "Find top-K frequent elements — heap vs bucket sort."
• "What if the input is a stream too large to store?"
• "Return elements sorted by frequency descending."
• "Top-K frequent words in a document (string keys)."
• "How do you handle ties stably?"
• "Approximate top-K with Count-Min / heavy hitters for a stream."
• "Complexity when k ≈ n vs k ≪ n?"
• "Extend to sliding-window top-K over the last N events."

The question, as it might actually be asked

Given an array of integers, return the k most frequent elements. Order among ties can be arbitrary unless specified.

How you'd talk while coding

I'd ask: does the whole array fit? Tie-break rules? Is k ≪ unique count? Stream version? Brute is count + sort uniques. Correct is Counter + size-k heap — O(n log k). I'd say why not full sort when k is small. Tests: [1,1,1,2,2,3], k=2 → [1,2]; all unique k=1; k equals unique count. Staff+ stop line: "If N doesn't fit, Count-Min + heap with an explicit error bound. Local top-k merge across shards is approximate — I won't build a real-time analytics platform in this round."

Where this actually gets asked

Classic heap/hash medium. Staff+ extension is streaming / approximate when N doesn't fit — mention the sketch, don't implement one unless asked.

Problem

Given an array of integers, return the k most frequent elements. Order among ties can be arbitrary unless specified.

Clarifying questions you should ask first

1. Can entire array fit in memory?
2. Tie-breaking rules?
3. k relative to unique count?
4. Online/stream version needed?

Approach ladder

Reference solution (Python)

from __future__ import annotations
from collections import Counter
import heapq

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    if k <= 0:
        return []
    counts = Counter(nums)
    # nsmallest on (-freq) via heapq.nlargest on freq
    return [x for x, _ in heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])]

Complexity: O(n + u log k) time; O(u) space.

Verbal tests to narrate

1. [1,1,1,2,2,3], k=2 → [1,2]
2. All unique, k=1 → any one
3. k equals unique count → all keys

Staff+ deep dive

What not to discuss

• Building a real-time analytics platform before the heap solution works
• Ignoring memory assumption

What's expected at each level

• Mid-level: Counter + sort.
• Senior: Heap solution + complexity.
• Staff+: Streaming/approximate trade-off with clear error talk.
• Principal: Relates to real metrics pipelines and cardinality limits.

Follow-up questions to expect

• "Exact top-k when cardinality is huge?" — Exact needs O(u) memory. Sketches need explicit error bounds — say the bound, don't hand-wave.
• "Tie-breaking?" — I'd declare a deterministic policy and test it.
• "Distributed top-k?" — Local top-k merge is approximate unless we define the aggregation contract.
• "When to stop?" — Exact heap/buckets + tests + one bounded-memory note.

Related

• 00-staff-plus-coding-bar.md