Katkat
Back

Implement trie-based autocomplete

PinterestMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to implement a space-efficient Trie data structure capable of storing strings along with associated weights to return top-k suggestions for a given prefix.

Problem Statement

Design an autocomplete system that stores a set of strings, each with an associated integer weight (e.g., popularity). Implement a class AutocompleteSystem that provides efficient prefix searching.

Requirements

  1. add_word(word: str, weight: int): Insert a word with a specific weight into the data structure.
  2. search(prefix: str, k: int) -> List[str]: Return the top k words that start with the given prefix, ordered by weight in descending order. If two words have the same weight, order them lexicographically.

Constraints

  • Total number of characters across all words is at most 10^6.
  • k will be a positive integer.
  • If fewer than k words match the prefix, return all matching words.

Example

# Initialize
auto = AutocompleteSystem()
auto.add_word("apple", 10)
auto.add_word("apply", 15)
auto.add_word("app", 5)
auto.add_word("bat", 20)

# Search
auto.search("app", 2)
# Output: ["apply", "apple"]
# Explanation: "apply" (15) and "apple" (10) are the top 2.

Edge Cases

  • Searching for a prefix that does not exist in the trie.
  • k being larger than the number of words matching the prefix.
  • Adding a word that already exists (update its weight).

Hints

Hint 1

Use a Trie node structure where each node stores a list or heap of the top-k words passing through that node.

Hint 2

During insertion, update the path of nodes corresponding to the word to reflect the new potential 'top' candidates.

Hint 3

Consider how to handle updates to weights efficiently without re-scanning the entire subtree.

Follow-up questions

  • How would you optimize the memory footprint if the Trie becomes too large to fit in RAM?
  • What changes are needed if the weights are dynamic (e.g., popularity changes based on real-time user clicks)?
  • How would you implement a fuzzy search that returns results even if the user makes a minor typo in the prefix?