Pick the Data Structure for Each Scenario

Problem

For each scenario below, name the data structure you would use, give the cost of the operations the scenario cares about, and name the most tempting alternative and why it loses. Assume in-memory, single machine, Python or Java standard library unless stated.

1. A spell checker must answer "is this word in the dictionary?" for 500,000 words, tens of thousands of times per second. Memory is not tight.
2. An autocomplete box must return all dictionary words that start with the typed prefix, in order.
3. A task scheduler must repeatedly hand out the task with the earliest deadline, while new tasks with arbitrary deadlines keep arriving.
4. A cache must evict the least recently used entry when full, and every get or put must be O(1).
5. A ticker must report the median of all prices seen so far after each new price.
6. A text editor must support insert and delete at the cursor, and moving the cursor anywhere, on a document of millions of characters.
7. A log analyzer must count distinct user IDs in a stream of a billion events using a few kilobytes of memory, tolerating 2% error.
8. A leaderboard must support "update player score" and "what is this player's rank?" for a million players, both frequently.
9. A network service must check whether a request's IP is in a blocklist of 10 million CIDR ranges.
10. A build system must order compilation so every module is compiled after its dependencies, and detect cycles.

Examples

• Scenario 1 answered well: "A hash set. Membership is O(1) expected. A sorted array with binary search would be O(log n) and more compact, but we said memory is fine and we need raw lookup speed. A trie would give prefix queries we do not need."
• Scenario 1 answered badly: "A trie, because it is for words." The structure fits the data type but not the access pattern, and the access pattern is what was asked.

Hints

1. Start from the operations and their frequencies, not from the data. Write the two or three operations that dominate, then find the structure whose cheap operations are exactly those.
2. Every good answer contains the word "because" and at least one rejected alternative.
3. When two operations pull in different directions (fast lookup and fast ordered iteration, say), the answer is often two structures kept in sync.