Search Autocomplete
medium · trie
Brief-reported interview attribution (unverified): Microsoft, Google
How to approach an LLD roundRequirements
- 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 alphabeticalRules. 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
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter