Top k frequent words: heap or buckets

Top k frequent words asks for the k words that occur most often in a list, most frequent first, with a rule for words that occur equally often. It takes two steps: count every word with a hash map in one pass, then pick the k best (word, count) pairs, the top-k pattern of the previous lesson applied to counts. The tie rule is where answers go wrong. When equal counts are broken alphabetically, the order compares counts first and words second, and the picking step must follow exactly that order.

The problem: the most searched station codes

1. NDLS, SBC, NDLS, HWH, SBC, NDLS, MAS with k = 2 gives [NDLS, SBC]: three searches, then two.
2. SBC, MAS, HWH, MAS, SBC, HWH with k = 2 gives [HWH, MAS]: every code was searched twice, so alphabetical order alone decides, and SBC is left out.
3. BCT with k = 1 gives [BCT].

The brute force: one scan of the log per code

For each distinct code, scan the whole log and count it. Then sort the codes by count, highest first and alphabetically among equal counts, and return the first k. It is plainly right, so it can judge faster code, but its scans cost O(n · d) for n searches and d distinct codes. At 10⁶ searches and 10⁴ codes that is 10¹⁰ log entries read, about 100 seconds of C++ at 10⁸ simple steps a second.

# The brute force for the k most searched station codes: count each distinct code by scanning the whole log, then
# sort the distinct codes by count, highest first, and alphabetically among equal counts. The last line works out how
# many log entries those scans would read on a synthetic log of 200,000 searches over about 2,000 codes.
import random
import string


def most_searched_by_scanning(log, k):
    counts = []
    for code in sorted(set(log)):
        seen = 0
        for entry in log:  # one full scan of the log per distinct code
            if entry == code:
                seen += 1
        counts.append((code, seen))
    counts.sort(key=lambda pair: (-pair[1], pair[0]))  # higher count first, then alphabetical
    return [code for code, _ in counts[:k]]


print(most_searched_by_scanning(["NDLS", "SBC", "NDLS", "HWH", "SBC", "NDLS", "MAS"], 2))
print(most_searched_by_scanning(["SBC", "MAS", "HWH", "MAS", "SBC", "HWH"], 2))
print(most_searched_by_scanning(["BCT"], 1))

rng = random.Random(9)
codes = ["".join(rng.choices(string.ascii_uppercase, k=4)) for _ in range(2_000)]
log = [rng.choice(codes) for _ in range(200_000)]
distinct = len(set(log))
print(f"{len(log):,} searches of {distinct:,} codes: one scan per code would read {len(log) * distinct:,} log entries")

['NDLS', 'SBC']
['HWH', 'MAS']
['BCT']
200,000 searches of 1,996 codes: one scan per code would read 399,200,000 log entries

On the synthetic log of 200,000 searches, one scan per code would read 399,200,000 entries, about 2,000 times the length of the log itself.

What to notice

The scans count each code separately, and one pass with a hash map from code to count does it for all of them, as in the lesson on frequency maps. After counting, the question is a top-k over d (code, count) pairs, ordered by count first and then alphabetically. Three ways pick those pairs:

• Count and sort sorts all d pairs by that order and keeps the first k, in O(d log d) time.
• A size-k heap keeps the k best pairs, with the worst of them on top, in O(d log k) time.
• Buckets by count list the codes of each count in an array indexed by count, then walk it from the top.

Counting in one pass, then a top-k over the pairs Pro: opens with a Pro, Premium or Ultimate pass