Typeahead with a top-k trie.

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):

1. 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.
2. 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_rows holds (day, query, searches, successes) tuples; day and today are datetime.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) and score += weight * (searches + 2 * successes).
• Leave out queries with fewer than min_users distinct users and queries in blocked (a set of normalised queries).

Typeahead(k):

Rules the tests check:

• A trailing space means "this word is finished": "nike " must not suggest "nikon". The given normalize() keeps one trailing space; your trie simply treats it as a character.
• suggest must not walk the subtree under the prefix. Keep each node's top-k list ready at build time.

In JavaScript and TypeScript it's scoreQueries(dailyRows, users, today, blocked, { halfLife = 14, minUsers = 20 } = {}), returning a Map of query → score. A row is an array [day, query, searches, successes], users is a Map, blocked a Set, and D(y, m, d) gives a UTC-midnight Date, so (today - day) / 86_400_000 is the age in days. new Typeahead(k) has build(scores) (a Map) and suggest(prefix) (an array). "Alphabetical" means plain string order (a < b), as in Python, not localeCompare.