Katkat
Back

Build Prefix Lookup with a Trie

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests implementation of a Trie (prefix tree) data structure to support word insertion, exact word search, prefix existence checks, and lexicographical autocomplete suggestions with a capacity limit.

Problem Statement

Design a prefix lookup system, PrefixVault, that stores a dictionary of words and supports fast retrieval based on common prefixes. Your class should implement the following methods:

  • __init__(): Initializes the trie data structure.

  • insert(word: str) -> None: Adds a word to the dictionary. If the word already exists, the state remains valid without storing duplicate entries.

  • has_word(word: str) -> bool: Returns True if the exact word is present in the dictionary, and False otherwise.

  • has_prefix(prefix: str) -> bool: Returns True if there is any word in the dictionary that starts with the given prefix, and False otherwise.

  • autocomplete(prefix: str, max_results: int) -> list[str]: Returns a list of up to max_results words in the dictionary that start with prefix, ordered in lexicographical (alphabetical) order. If fewer than max_results words match, return all matches. If no words match or `max_results None: pass

    def has_word(self, word: str) -> bool: pass

    def has_prefix(self, prefix: str) -> bool: pass

    def autocomplete(self, prefix: str, max_results: int) -> list[str]: pass


## Examples

### Example 1

```python
vault = PrefixVault()
vault.insert("apple")
vault.insert("app")
vault.insert("application")
vault.insert("apt")
vault.insert("banana")

vault.has_word("app")         # returns True
vault.has_word("appl")        # returns False
vault.has_prefix("appl")      # returns True ("apple", "application")
vault.has_prefix("bat")       # returns False

vault.autocomplete("app", 2)  # returns ["app", "apple"]
vault.autocomplete("app", 5)  # returns ["app", "apple", "application"]
vault.autocomplete("z", 3)    # returns []

Constraints

  • 1 <= len(word), len(prefix) <= 100
  • word and prefix consist only of lowercase English letters ('a' - 'z').
  • 0 <= max_results <= 100
  • At most 2 * 10^4 total calls will be made across all methods.

Edge Cases to Consider

  • Prefix itself is an exact word in the trie.
  • Duplicate calls to insert with the same word.
  • autocomplete where max_results == 0 or exceeds the total count of matches.
  • Prefix does not match any node in the trie.

Hints

Hint 1

Model each node in the Trie with a map or array of children nodes (keyed by character) and a boolean flag indicating whether the node marks the end of a valid word.

Hint 2

For autocomplete, first traverse down the Trie along the characters of the prefix; if the prefix path does not exist, return an empty list immediately.

Hint 3

From the end node of the prefix, perform a depth-first search visiting child branches in alphabetical order ('a' through 'z') to naturally collect words in lexicographical order, stopping as soon as the result list reaches max_results.

Follow-up questions

  • How would you optimize `autocomplete` if each word had an associated popularity score and queries needed the top-k highest-scoring words instead of alphabetical order?
  • How would you adapt the internal node representation to support memory efficiency when handling unicode strings or large, sparse alphabets?
  • If the trie becomes too large to fit in memory on a single machine, how would you partition or distribute the data across multiple servers?