Design Prefix Autocomplete

A practice problem in the escalating-screen format. Time phase one to 15 minutes; don't open an escalation until the previous one is green.

Phase 1 — the prompt

A gallery's search box suggests project names as the user types. Build the index behind it.

Method	Behavior
addApp(name: string): void	Add a name to the index
suggest(prefix: string): string[]	Every indexed name starting with prefix, sorted alphabetically

Rules:

• Case-insensitive matching, original casing returned. Typing "cr" finds "CRM Tracker", and the result reads "CRM Tracker".
• An empty prefix returns everything.
• A prefix nobody matches returns an empty array.
• Adding the same name twice does not duplicate.

Naive is allowed — encouraged — in phase 1. Scanning every name per query passes every test above:

class Autocomplete {
  private names = new Map<string, string>(); // lowercased -> original casing

  addApp(name: string): void {
    this.names.set(name.toLowerCase(), name);
  }

  suggest(prefix: string): string[] {
    const p = prefix.toLowerCase();
    return [...this.names.entries()]
      .filter(([key]) => key.startsWith(p))
      .map(([, original]) => original)
      .sort();
  }
}

The graded move is saying it out loud: "this is O(n) per keystroke and I'm choosing it deliberately — I'll replace the scan when the requirements force it." Starting naive with named intent beats starting clever and finishing nothing. Note the map already encodes the casing rule: lowercased key for matching, original string as the value.

Escalation 1 — 50,000 names, fired on every keystroke

suggest runs on every character typed, against the whole corpus. Make it not depend on the total number of indexed names — only on the prefix length and the number of results.

This requirement has one name: a trie. Walk one node per prefix character (O(p), independent of corpus size), then collect the subtree.

class TrieNode {
  children = new Map<string, TrieNode>();
  original: string | null = null; // set ⇒ a complete name ends here
}

class Autocomplete {
  private root = new TrieNode();

  addApp(name: string): void {
    let node = this.root;
    for (const ch of name.toLowerCase()) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.original = name; // re-adding overwrites: no duplicates, free
  }

  suggest(prefix: string): string[] {
    let node = this.root;
    for (const ch of prefix.toLowerCase()) {
      const next = node.children.get(ch);
      if (!next) return [];                 // dead prefix: nobody matches
      node = next;
    }
    const out: string[] = [];
    const collect = (n: TrieNode): void => {
      if (n.original !== null) out.push(n.original);
      // Map preserves insertion order, not alphabetical — sort keys per level
      for (const key of [...n.children.keys()].sort()) collect(n.children.get(key)!);
    };
    collect(node);
    return out;
  }
}

Walking children in sorted key order makes the output alphabetical by construction — no final sort over the results.

The memory sentence most candidates skip, and interviewers wait for: a trie trades memory for query speed — one node per character of every unique prefix, each carrying a Map. For 50k names that's fine; for millions you'd name compressed tries (radix trees) as the follow-up. Cost on insert: O(length). Cost on query: O(p + results). Say all three numbers.

Escalation 2 — the best match, not every match

Every name now carries a popularity score: addApp(name, score). Add topSuggestions(prefix, k) — at most k names, highest score first, ties alphabetical. Collecting every match and then sorting defeats the point: a prefix like "a" might match 20,000 names and the user wants 5.

The escalation is aimed straight at the lazy answer. Two defensible responses:

• Collect + heap: walk the subtree but keep only a size-k min-heap — O(matches log k) instead of O(matches log matches). Honest, simple, still walks the subtree.
• Precompute per node: each trie node caches its subtree's top-k (names + scores), maintained on insert along the walked path. Query becomes O(p + k) — reads are free, writes pay O(depth × k). This is what real search boxes do, and it's the answer that shows you know reads dominate writes by orders of magnitude here.

Name both, pick the second, defend the write cost. Score updates (re-adding with a new score) are the wrinkle: the cached top-k along the old path may hold a stale score, which is why real systems version entries or rebuild lazily — saying that sentence is the senior move.

Escalation 3 — matching a word in the middle

Users type "tracker" and expect "CRM Tracker". Make matching work on a prefix of any word in the name. A name still appears once even if two of its words match.

Index every word-start suffix: "CRM Tracker" gets inserted under "crm tracker" and "tracker", both pointing at the same original. Deduplication is the whole difficulty — decide where it lives before typing. Cleanest: collect into a Set keyed by the original name (or its id), then order. Memory multiplies by the average word count; say so.

Escalation 4 — deletion

Add removeApp(name). A removed name never appears again; re-adding works; and the structure must not leak — removing every name that shared a prefix must not leave that prefix behind as permanent overhead.

Two layers, and they're different difficulties:

• Correct: walk to the terminal node, clear original. Done — the name can never be emitted again. Ten seconds.
• Leak-free: prune nodes that are now childless and non-terminal, walking back up the path. Needs parent pointers or a recursive delete that reports "I'm now empty."

Then the judgment call, which is the actual question: would you ship the pruning version, or the simple one plus periodic compaction? Both are defensible — tombstones-plus-compaction is how real systems (Lucene, LSM trees) handle deletion, and knowing that is worth more than the pruning code. Have a reason.

What's being scored

• Choosing naive first on purpose, with the upgrade path named.
• The trie as a response to a stated requirement, not premature cleverness.
• The memory trade-off sentence, unprompted.
• Escalation 2's real lesson: when reads outnumber writes 1000:1, move work to the write path.
• Deletion as a policy decision, not just code.