CodeLudo 🔥 Daily Guides

Pick the Structure: Ten Requirements, and Nobody Tells You the Answer

✓ numbers produced by the code on this page · Published 2026-08-20

Sixteen pages in this collection take one structure apart each. That is the right way to learn them and the wrong way to finish, because the skill none of them practises is the one every real task begins with.

You are handed a requirement. It never names the structure.

Someone who can explain a trie perfectly and still reaches for a hash map when asked to build autocomplete has learned the pages, not the subject. So this one runs the other way round.

Ten jobs

Four candidates each. The wrong options are not filler — each is the one somebody reaches for out of habit, and the explanation says why it tempts and where it breaks.

Pick the structure you are handed a requirement, never a structure

Every other page in this collection takes one structure apart. This one starts from the other end, which is where real work starts: you are handed a requirement, and it never names the structure.

10 jobs — autocomplete over a million words, deduplicating a ten-billion-item stream, always taking the smallest pending task, range queries on a billion rows sitting on disk, tracking which accounts have been merged. Four candidates each, and the wrong ones are not silly: each is the answer somebody reaches for by habit.

Two of them are traps this collection has already measured — sorted keys arriving into a plain search tree, and a nightly scan meeting a cache. Every answer links to the page with the program that proves it.

Two of these are traps this collection has already measured. Every answer links to the page with the program that proves it.

Three of them, costed

Choosing wrong is not a style error. Here is what it costs on three of the ten.

python 
from itertools import product
import math

WORDS = ["".join(p) for p in product("abcdert", repeat=4)]      # 2,401 four-letter words
PREFIX = "car"


def trie_prefix_cost(words, prefix):
    """Walk the prefix, then collect the subtree. Cost = nodes touched."""
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = True
    node, steps = root, 0
    for ch in prefix:
        if ch not in node:
            return steps, 0
        node, steps = node[ch], steps + 1
    matches = 0
    stack = [node]
    while stack:
        cur = stack.pop()
        for ch, child in cur.items():
            if ch == "$":
                matches += 1
            else:
                steps += 1
                stack.append(child)
    return steps, matches


def hash_prefix_cost(words, prefix):
    """A hash table scatters keys, so prefix search has to examine every one."""
    return len(words), sum(1 for w in words if w.startswith(prefix))


def repeated_min_cost(n, take):
    """Take the smallest `take` times: re-sorting each time versus a heap."""
    resort = take * math.ceil(n * math.log2(n))          # n log n per round
    heap = math.ceil(n) + take * math.ceil(math.log2(n))  # build once, then log n per pop
    return resort, heap


def membership_bytes(n, avg_len, bits_per_item):
    """Storing the strings, versus storing only a bit pattern about them."""
    return n * avg_len, math.ceil(n * bits_per_item / 8)


t_steps, t_hits = trie_prefix_cost(WORDS, PREFIX)
h_steps, h_hits = hash_prefix_cost(WORDS, PREFIX)
print(f"1. all completions of {PREFIX!r} among {len(WORDS):,} words   (trie vs hash table)")
print(f"   trie       {t_steps:>10,} nodes touched   {t_hits} matches")
print(f"   hash table {h_steps:>10,} keys scanned    {h_hits} matches")
print()

resort, heap = repeated_min_cost(100_000, 20)
print(f"2. take the smallest item 20 times from 100,000   (re-sort vs heap)")
print(f"   re-sort each time {resort:>12,} operations")
print(f"   heap              {heap:>12,} operations")
print()

exact, bloom = membership_bytes(10_000_000, 24, 10)
print(f"3. have I seen this before, for 10,000,000 items   (store them vs Bloom filter)")
print(f"   store the strings {exact:>12,} bytes")
print(f"   bloom filter      {bloom:>12,} bytes at 10 bits each")
Output 
1. all completions of 'car' among 2,401 words   (trie vs hash table)
   trie               10 nodes touched   7 matches
   hash table      2,401 keys scanned    7 matches

2. take the smallest item 20 times from 100,000   (re-sort vs heap)
   re-sort each time   33,219,300 operations
   heap                   100,340 operations

3. have I seen this before, for 10,000,000 items   (store them vs Bloom filter)
   store the strings  240,000,000 bytes
   bloom filter        12,500,000 bytes at 10 bits each

Same seven matches, 10 nodes against 2,401 keys. Same twenty items taken, 100,340 operations against 33 million. Same question answered, 12.5 MB against 240.

None of those gaps comes from one structure being faster in general. Each comes from the structure matching the shape of the question: a trie keeps related keys adjacent, a heap keeps only the promise you needed, a Bloom filter stores a fact about the data instead of the data.

The question that decides it

Almost every choice in this collection comes down to one thing: what are you going to ask, over and over?

And the second question, which the traps are about: what order does the data arrive in, and can you control it? Sorted input ruins a plain search tree and a naive quicksort pivot alike; a scan longer than a cache empties it for nothing. None of those shows up in a complexity table, and all of them show up in production.

What this page simplifies