Build Prefix Lookup with a Trie

Question

Design and implement a prefix lookup system using a Trie data structure.

Codemia · Accepted Answer

To build a prefix lookup system, we need a data structure that allows us to efficiently insert and search for strings based on their prefixes. A Trie is ideal for this purpose as it stores characters in a tree-like structure, where each node represents a character in a string.

The Trie will consist of nodes where each node contains a map of children nodes and a boolean flag to indicate the end of a word. The main operations we will implement are `insert` to add words and `search` to find words based on a prefix. We will also implement a method to retrieve all words that start with a given prefix.

Here is a basic implementation of the Trie in Python:

```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

def search(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True  # Prefix found
```
This implementation allows us to insert and check for prefixes efficiently.

The time complexity for both the `insert` and `search` operations is O(m), where m is the length of the word or prefix. The space complexity is O(n * m) in the worst case, where n is the number of words inserted into the Trie.

While Tries are efficient for prefix lookups, they can consume a lot of memory, especially if the character set is large. To optimize memory usage, we could implement a compressed Trie or use a more compact representation for the nodes. Additionally, for very large datasets, we might consider using a database or other storage solutions to handle persistence.

Build Prefix Lookup with a Trie

Google

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string