Search Autocomplete

medium · trie

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

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.

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'))

Starter code

class _TrieNode:

    def __init__(self):
        """Initialize the state described in the problem."""
        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 compiler