Code lab · World 07 · Designing a Search System
Typeahead with a top-k trie.
Score queries from daily logs with a half-life and a distinct-user floor, then build a trie that keeps its top k at every node so a keystroke is one walk.
Saving also stores the Python runtime (~13.5 MB, once for every lab) so this lab runs with no internet.
A keystroke has about 100 ms end to end, so typeahead can't rank every query under "s" while the user waits. Day 4 moves the work to build time (sections 2.2 and 3.2):
- Score every query from the last 90 days of logs, with older days counting less (a half-life) and queries that too few people typed left out.
- Build a trie where every node keeps its own top-k list, so serving is a walk down the prefix and nothing else.
Implement a function and a class.
score_queries(daily_rows, users, today, blocked, half_life=14, min_users=20) returns {query: score}:
daily_rowsholds(day, query, searches, successes)tuples;dayandtodayaredatetime.date.- Normalise every query with the given
normalize()first, so "Samsung S24" and "samsung s24" are one suggestion.users(query → distinct users over 90 days) is keyed by the normalised query. weight = 0.5 ** (age_days / half_life)andscore += weight * (searches + 2 * successes).- Leave out queries with fewer than
min_usersdistinct users and queries inblocked(a set of normalised queries).
Typeahead(k):
| Method | Does |
|---|---|
build(scores) |
builds the index from {query: score}. Calling it again replaces the old index (a new snapshot) |
suggest(prefix) |
the top k queries starting with normalize(prefix), best score first, ties in alphabetical order. [] for an empty or unknown prefix |
Rules the tests check:
- A trailing space means "this word is finished":
"nike "must not suggest"nikon". The givennormalize()keeps one trailing space; your trie simply treats it as a character. suggestmust not walk the subtree under the prefix. Keep each node's top-k list ready at build time.
Python 3.14 loads on first run (~6.5 MB once)14
Loading the editor…
⌘/Ctrl + Enternot run yet · 8 s limit
press Run tests
Write your code, then run 3 example tests and 10 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and Python restarts, your code stays.