Implement Trie with without recursion

Question

Implement a Trie data structure that supports get and put operations in O(log n) time.

Codemia · Accepted Answer

The problem requires implementing a Trie (prefix tree) data structure to efficiently support `put` and `get` operations in O(log n) time complexity. A Trie is particularly suitable for this task because it allows for efficient insertion and retrieval of strings, leveraging the common prefixes of the strings stored. The Trie structure uses a tree where each node represents a character of a string. The key challenge here is implementing the Trie without recursion, which suggests we will use an iterative approach to manage the node traversal.

We will implement the Trie using a class structure that includes an inner class for the TrieNode. Each node will store a dictionary to represent its children and a boolean flag to indicate if it is the end of a word. The operations will be: 1. **Put**: For each character in the input string, check if the character exists in the current node's children dictionary. If it does not, create a new TrieNode and add it to the dictionary. Move to the next character node. After processing all characters, mark the last node as the end of a word. 2. **Get**: For each character in the string, traverse through the Trie by checking if the character exists in the current node's children. If we reach the end of the string and the last node indicates the end of a word, return `True`; otherwise, return `False`. For example, for the input strings 'cat' and 'cater', the Trie will allow for efficient storage and retrieval of these words.

Here is the Python implementation of the Trie:
```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

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

def put(self, word: str) -> None:
        current_node = self.root
        for char in word:
            if char not in current_node.children:
                current_node.children[char] = TrieNode()
            current_node = current_node.children[char]
        current_node.is_end_of_word = True

def get(self, word: str) -> bool:
        current_node = self.root
        for char in word:
            if char not in current_node.children:
                return False
            current_node = current_node.children[char]
        return current_node.is_end_of_word
```

The time complexity for both the `put` and `get` operations is O(m), where m is the length of the word being inserted or searched. Given that the Trie is structured as a tree with nodes corresponding to characters, this is efficient. The space complexity is O(n * m) in the worst case, where n is the number of words and m is the average length of the words, as each node could potentially lead to a new character being stored.

1. **Empty String**: We should handle the case where the input string is empty. In `put`, we should still mark the root as the end of a word. In `get`, we should return `True`. 2. **Repeated Inserts**: Inserting the same word multiple times should not create duplicate nodes. The implementation naturally handles this by checking for existing children. 3. **Long Words**: We should ensure that the implementation does not run into performance issues with very long words, which could impact time complexity if not handled correctly.

Implement Trie with without recursion

Lyft

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Lyft 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