Search Autocomplete

medium · trie

Brief-reported interview attribution (unverified): Microsoft, Google

How to approach an LLD round

Requirements

  • Functional: add a term with a weight, remove it, suggest the top-k matches for a prefix (weight desc, ties alphabetical).
  • Non-functional: a re-add updates the weight; suggestion must be fast for a long prefix (trie lookup, not a scan); the ranking rule must be separate from the trie.
  • Out of scope: fuzzy matching, typo tolerance, persistence.

Statement

Design a search autocomplete system. add(term, weight) inserts a term with a popularity weight (adding an existing term updates its weight). suggest(prefix, k=5) returns up to k terms starting with the prefix, ordered by weight descending, ties broken alphabetically. Matching is case-sensitive. remove(term) removes a term (returns False if it was not stored).

class Autocomplete:
    def __init__(self):
    def add(self, term, weight):
    def remove(self, term):
        # -> True if the term was stored, False otherwise
    def suggest(self, prefix, k=5):
        # -> list of terms, weight desc, ties alphabetical

Rules. Updating a term's weight must change its position in later suggestions. Removing a term removes it from suggestions but must not disturb other terms that share its prefix. suggest with a prefix that matches nothing returns [].

Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.

Class design (SOLID)

TrieNode (children + terms; SRP). Trie (insert/remove/collect below a prefix; SRP). Autocomplete owns the ranking (weight desc, alpha tie-break; SRP). No pattern is forced; the split (structure vs ranking) is the point.

Public demo

# Public demo: run after implementing the class API above.
a = Autocomplete()
for term, weight in [('apple', 10), ('app', 5), ('application', 8), ('banana', 3), ('band', 7)]:
    a.add(term, weight)
print(a.suggest('app'))
print(a.suggest('app', k=2))
print(a.suggest('ban'))
print(a.suggest('xyz'))

Reference solution and hidden tests

Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.

Concurrency

Read-heavy: many suggest calls and few add/remove. A single lock around mutations is enough; in production, a read-write lock (many concurrent suggests, one writer) scales better. The reference is single-threaded; the lock is described here.

Trade-offs & extensions

The trie is fast per prefix but holds a node per character — memory grows with the term set. Extending: a compressed trie (radix tree) and a RankingStrategy (popularity vs recency).

Starter code

class TrieNode:

    def __init__(self):
        """Initialize the state described in the problem."""
        pass

class Trie:

    def __init__(self):
        """Initialize the state described in the problem."""
        pass

    def insert(self, term, weight):
        """Implement the return value and rules in the API contract."""
        pass

    def remove(self, term):
        """-> True if the term was stored, False otherwise"""
        pass

    def collect(self, prefix):
        """Implement the return value and rules in the API contract."""
        pass

class Autocomplete:

    def __init__(self):
        """Initialize the state described in the problem."""
        pass

    def add(self, term, weight):
        """Implement the return value and rules in the API contract."""
        pass

    def remove(self, term):
        """-> True if the term was stored, False otherwise"""
        pass

    def suggest(self, prefix, k=5):
        """-> list of terms, weight desc, ties alphabetical"""
        pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

4 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. Rubber DuckCharacter joke · No posting date

    Quack. (Translation: have you tried printing it?)

  2. RecruiterCharacter joke · No posting date

    We loved your energy. We went with the candidate whose code compiled.

  3. TryGetValueCharacter joke · No posting date

    My solution passed all the tests. All zero of them. I forgot to run them.

  4. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.