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

Interviewers often ask the same structure with different framing or Staff+ extensions — recognize the archetype:

"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.

The framework

Clarify constraints → correct end-to-end solution → narrate complexity and tests → offer a Staff+ extension (concurrency, API contract, or failure mode) without turning a coding round into distributed system design. See Approach ladder and Staff+ deep dive below.

Where this actually gets asked

Classic heap/hash medium. Staff+ extension: streaming / approximate (Count-Min + heap) when N does not fit in memory — mention without implementing a full sketch 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

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

Approach ladder

Step	Idea
Brute	Count + sort unique — O(u log u)
Correct	Count + size-k heap — O(n log k)
Staff+	Stream: Count-Min Sketch + heap; error bounds

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,2,2,3], k=2 → [1,2]
All unique, k=1 → any one
k equals unique count → all keys

Staff+ deep dive

Topic	Talking point
Why heap not full sort	k << u
Stream	Sketch trades accuracy for memory — state error bound
Distributed	Local top-k + merge is approximate

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.

00-staff-plus-coding-bar.md