Top-K Most Frequent Search Terms

Difficulty: Easy · Topics: hash-map, heap, counting · Asked at: Google, Amazon, Bloomberg

Problem

Given a list of raw search queries, normalise each term (lowercase, strip surrounding whitespace, ignore empty strings) and return the k most frequent terms as (term, count) tuples, sorted by count descending and then alphabetically for ties.

Examples

top_k_terms(["Spark", "kafka ", "spark", "", "Delta", "KAFKA", "spark"], 2)
→ [("spark", 3), ("kafka", 2)]

Constraints

• Up to 10⁷ queries; vocabulary may be large.
• k ≥ 1; if fewer than k distinct terms exist, return all.

Starter code

def top_k_terms(queries: list[str], k: int) -> list[tuple[str, int]]:
    pass

Hints

Solution

from collections import Counter
import heapq

def top_k_terms(queries: list[str], k: int) -> list[tuple[str, int]]:
    counts = Counter(t for t in (q.strip().lower() for q in queries) if t)
    return heapq.nsmallest(k, counts.items(), key=lambda kv: (-kv[1], kv[0]))

Tests

Your solution should pass these:

assert top_k_terms(["Spark", "kafka ", "spark", "", "Delta", "KAFKA", "spark"], 2) == [("spark", 3), ("kafka", 2)]
assert top_k_terms(["b", "a", "c", "b", "a"], 2) == [("a", 2), ("b", 2)]
assert top_k_terms([], 3) == []
assert top_k_terms(["x"], 5) == [("x", 1)]

Explanation

Counting is O(n). Selecting top-k with a heap is O(m log k) for m distinct terms, better than sorting all terms (O(m log m)) when k ≪ m. Counter.most_common(k) also uses a heap but breaks ties by insertion order, which isn’t what the spec asks.

Follow-up questions