Search Suggestions System

This is autocomplete, the problem tries were made for. The user types one character at a time, and after each one the box must show a short list of matching names. The trie idea — walk one edge per character — fits perfectly, and one extra field on each node makes each answer instant.

The problem

You are given a list of product names and a word the user types, one character at a time. After each character, return up to three product names that start with the text typed so far. If more than three match, return the three that come first alphabetically. Return one list per character typed.

Example. Products: bandana, bank, banana, basket, band, bangle, bar. The user types bank.

• After b → ["banana", "band", "bandana"]. All seven match; these are the first three alphabetically.
• After ba → ["banana", "band", "bandana"].
• After ban → ["banana", "band", "bandana"]. bangle and bank also match but sort later.
• After bank → ["bank"]. Only one product starts with bank.

Had the user typed bans, the last list would be []: nothing starts with bans.

Constraints. Up to 10^5 products, 1 to 30 lowercase letters each. The typed word has 1 to 30 letters.

Clarifying questions

• Can product names repeat? Assume they are distinct. (If not, both solutions below would list a repeat twice; dedupe first if that is wrong.)
• "Alphabetical" means plain string order? Yes: band before bandana, because a prefix sorts first.
• Once nothing matches, do later characters still get a list? Yes, an empty one.
• Is the product list fixed, and are there many users? Yes. Build once, answer many times.

Approach 1: the simple way

For each typed prefix, filter all products and sort the matches.

1def suggestions_brute(products: list[str], typed: str, k: int = 3) -> list[list[str]]:2    """For every prefix, filter all products and sort the matches."""3    result = []4    for i in range(1, len(typed) + 1):5        prefix = typed[:i]6        matches = sorted(p for p in products if p.startswith(prefix))7        result.append(matches[:k])8    return result

For a typed word of length T and n products, each keystroke scans all n names and sorts up to n matches: O(T × n × (T + log n)) character work. With 10^5 products and 30 keystrokes, that is 3 × 10^6 prefix checks, plus sorting up to 10^5 names on the first keystroke alone. And it repeats all of it for every user. The early keystrokes are the worst: b matches a large share of the list, and the code sorts all of them to keep three.

The key insight

Two observations. First, the three answers for a prefix are the first three products, in sorted order, whose path passes through that prefix's node. Second, those answers never change: the product list is fixed.

So compute them once, at build time. Insert the products in sorted order. As each product walks down the trie, it appends itself to every node it passes — but only if that node holds fewer than three names. Because products arrive alphabetically, the first three to pass through a node are exactly its three smallest matches. A query is then a walk of one edge per keystroke, reading the stored list at each node.

Approach 2: a trie with the top three stored on each node

1class SuggestNode:2    """Trie node that also keeps the first k words passing through it."""34    def __init__(self) -> None:5        self.children: dict[str, SuggestNode] = {}6        self.top: list[str] = []789def suggestions_trie(products: list[str], typed: str, k: int = 3) -> list[list[str]]:10    """Build once in sorted order; each node remembers its first k words."""11    root = SuggestNode()12    for product in sorted(products):13        node = root14        for ch in product:15            node = node.children.setdefault(ch, SuggestNode())16            if len(node.top) < k:17                node.top.append(product)         # sorted insert order = alphabetical18    result: list[list[str]] = []19    node: SuggestNode | None = root20    for ch in typed:21        node = node.children.get(ch) if node else None22        result.append(list(node.top) if node else [])23    return result

Step by step:

1. Sort the products once: banana, band, bandana, bangle, bank, bar, basket.
2. Insert each one. At every node on its path, append the name if the node's list is not full.
3. For the query, walk one edge per typed character and record that node's list.
4. Once an edge is missing, node becomes None and every later answer is [].

Dry run. Here are the lists on the nodes the query bank visits, after all seven inserts:

The query walks b → a → n → k and returns [["banana", "band", "bandana"], ["banana", "band", "bandana"], ["banana", "band", "bandana"], ["bank"]], matching the example.

Complexity. Building costs O(n log n) string comparisons for the sort, plus O(S) for the inserts, where S is the total length of all products. Each query keystroke costs O(1) to step plus O(k) to copy the list, so a whole query costs O(T × k). Space is O(S) nodes, plus up to k names per node — the names are shared references, not copies. The build runs once; every later user pays only O(T × k).

Approach 3: sort and binary search

There is a leaner option. Sort the products once. For each prefix, binary-search for the first product that is not less than the prefix. All matches are contiguous from there, so check the next three.

1from bisect import bisect_left23def suggestions_bisect(products: list[str], typed: str, k: int = 3) -> list[list[str]]:4    """Sort once; binary-search where each prefix would start."""5    products = sorted(products)6    result = []7    start = 08    for i in range(1, len(typed) + 1):9        prefix = typed[:i]10        start = bisect_left(products, prefix, start)11        result.append([p for p in products[start:start + k] if p.startswith(prefix)])12    return result

Passing start as the lower bound is safe: a longer prefix can only begin at or after the shorter one's position. Each keystroke costs O(T × log n) for the string comparisons in the binary search, and the extra space is only the sorted list.

Which to use? Binary search uses far less memory and less code, and is a fine answer. The trie wins when the per-keystroke cost must not depend on n at all, or when you also need counts, fuzzy matching or deletions per prefix. Offer both and let the interviewer choose.

Edge cases

• A prefix that matches nothing (bans) → [], and every later keystroke is [] too.
• Fewer than three matches → return what exists (["bank"]).
• A product equal to the typed prefix (band while typing band) → it is included and sorts before bandana.
• Unsorted input → the trie only works because inserts happen in sorted order. Sorting is part of the algorithm, not a tidy-up.

Follow-ups

• "Rank by popularity, not alphabet." Store the top k by score on each node. Inserting in score order keeps the same build; if scores change live, each node needs a small heap, and updates cost O(L × log k).
• "Tolerate one typo." Search the trie with a DFS that allows one substitution, like the wildcard search, then merge results.
• "The list is too big for memory." Keep only the top-k lists for short prefixes (the first 3–4 characters) in memory, and fall back to the sorted list on disk for longer ones.