Implement Trie with O(1) space

Question

Implement a Trie data structure that supports insert, search, and delete operations with O(1) space complexity for each operation. Your implementation should handle strings of lowercase English letters and should return a boolean indicating the success of search and delete operations. Ensure that the Trie can efficiently manage a dynamic set of strings while maintaining the specified space constraints.

Codemia · Accepted Answer

The problem requires us to implement a Trie data structure that supports insert, search, and delete operations while maintaining O(1) space complexity for each operation. The Trie is a tree-like structure that efficiently stores strings, allowing operations to be performed based on the characters in the strings. The challenge here is to achieve O(1) space complexity, which suggests a unique approach to manage the Trie nodes. Given that we are only dealing with lowercase English letters (26 characters), we can utilize a fixed-size array for child nodes instead of a dynamic structure, which allows us to achieve O(1) space usage for each character in the nodes.

1. **Node Structure**: Create a `TrieNode` class that contains a fixed-size array of size 26 (for each letter of the alphabet) to represent child nodes and a boolean flag to indicate the end of a word.
2. **Insert Operation**: For each character in the string, calculate its index in the child array (using `ord(char) - ord('a')`). If the corresponding child node is `None`, create a new `TrieNode`. Set the end flag to `True` when the last character of the string is inserted.
3. **Search Operation**: Traverse the Trie using the same index calculation. If you reach the end of the word and the end flag is `True`, return `True`; otherwise, return `False`.
4. **Delete Operation**: To delete a word, traverse to the last character and set its end flag to `False`. If the node has no children, remove the node by potentially backtracking if necessary.

**Example**: For the word 'cat', on insertion, create nodes for 'c', 'a', and 't'. Searching for 'cat' will follow the path and return `True`. Deleting 'cat' will clear the end flag at 't'.

```python
class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end_of_word = False

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

def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            index = ord(char) - ord('a')
            if not node.children[index]:
                node.children[index] = TrieNode()
            node = node.children[index]
        node.is_end_of_word = True

def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            index = ord(char) - ord('a')
            if not node.children[index]:
                return False
            node = node.children[index]
        return node.is_end_of_word

def delete(self, word: str) -> bool:
        return self._delete_helper(self.root, word, 0)

def _delete_helper(self, node: TrieNode, word: str, depth: int) -> bool:
        if depth == len(word):
            if not node.is_end_of_word:
                return False  # word not found
            node.is_end_of_word = False
            return not any(node.children)
        index = ord(word[depth]) - ord('a')
        if not node.children[index]:
            return False  # word not found
        can_delete = self._delete_helper(node.children[index], word, depth + 1)
        if can_delete:
            node.children[index] = None
            return not node.is_end_of_word and not any(node.children)
        return False
```

The time complexity for all operations (insert, search, delete) is O(L), where L is the length of the string being processed. Since we are only traversing through the string and using a fixed-size array of size 26, the space complexity for the Trie structure is O(1) in terms of the operations, as we are not using additional data structures proportional to the size of the input but rather a fixed number of nodes. However, the total space used by the Trie could grow with the number of unique words inserted.

1. **Empty Strings**: Inserting an empty string should work and set the root's end flag to True. Searching for an empty string should return True, while deleting it should also properly reset the end flag.
2. **Duplicate Inserts**: Inserting the same word multiple times should not create additional nodes; the structure should remain the same.
3. **Searching Non-existent Words**: Searching for words not present in the Trie should return False regardless of their length.
4. **Deleting Non-existent Words**: Attempting to delete a word that doesn't exist should not affect the Trie structure and should return False.

Implement Trie with O(1) space

Tesla

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

Tesla 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