Let's implement a Trie (also known as a prefix tree) with a few specific functionalities. A Trie is a tree-like data structure used for efficient retrieval of strings. Each node in the Trie represents a character, and the path from the root to a node forms a prefix or a complete word.
Your task is to implement a Trie
class with the following methods:
Trie()
: Initializes the Trie object.insert(word: str)
: Inserts the string word
into the Trie. If the word is already present, increment the count of that word.countWordsEqualTo(word: str) -> int
: Returns the number of times the string word
is present in the Trie.countWordsStartingWith(prefix: str) -> int
: Returns the number of strings in the Trie that start with the given prefix
.erase(word: str)
: Decrements the count of the string word
in the Trie. If the count reaches zero, effectively remove the word. If the word does not exist, nothing happens.For example:
Trie trie = new Trie();
trie.insert("apple");
trie.insert("apple");
trie.countWordsEqualTo("apple"); // Returns 2
trie.countWordsStartingWith("app"); // Returns 2
trie.insert("app");
trie.countWordsStartingWith("app"); // Returns 3
trie.erase("apple");
trie.countWordsEqualTo("apple"); // Returns 1
trie.countWordsStartingWith("app"); // Returns 2
trie.erase("apple");
trie.countWordsEqualTo("apple"); // Returns 0
trie.erase("apple"); // does nothing as apple's count is already 0
Consider edge cases such as inserting an empty string, searching for a non-existent word or prefix, and erasing a word that is not in the Trie.
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The goal is to build a system to store words so we can quickly find out how many words start with a particular sequence of letters, and how many times a specific word was inserted. A brute force approach directly uses the words themselves for these operations, without any special structure.
Here's how the algorithm would work step-by-step:
class Trie:
def __init__(self):
self.word_list = []
def insert(self, word: str) -> None:
# Simply append the word to our word list.
self.word_list.append(word)
def countWordsEqualTo(self, word: str) -> int:
word_count = 0
# Iterate to count exact matches.
for existing_word in self.word_list:
if existing_word == word:
word_count += 1
return word_count
def countWordsStartingWith(self, prefix: str) -> int:
prefix_count = 0
# We need to check all stored words.
for existing_word in self.word_list:
# Check if word starts with prefix.
if existing_word.startswith(prefix):
prefix_count += 1
return prefix_count
def erase(self, word: str) -> None:
#Remove the first occurrence of the word.
if word in self.word_list:
self.word_list.remove(word)
We'll use a special tree-like structure to store words. This structure helps us quickly find words with the same starting parts and also keep track of how many times a word was added or if it's a real word.
Here's how the algorithm would work step-by-step:
class TrieNode:
def __init__(self):
self.children = {}
self.word_count = 0
self.prefix_count = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(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.prefix_count += 1
# Mark the end of the word and increase its count
current_node.word_count += 1
def countWordsEqualTo(self, word: str) -> int:
current_node = self.root
for char in word:
if char not in current_node.children:
return 0
current_node = current_node.children[char]
# Return the number of times the word was inserted
return current_node.word_count
def countWordsStartingWith(self, prefix: str) -> int:
current_node = self.root
for char in prefix:
if char not in current_node.children:
return 0
current_node = current_node.children[char]
# Return the number of words starting with the prefix
return current_node.prefix_count
def erase(self, word: str) -> None:
current_node = self.root
for char in word:
if char not in current_node.children:
return
current_node = current_node.children[char]
current_node.prefix_count -= 1
# Only decrement if word exists
if current_node.word_count > 0:
current_node.word_count -= 1
Case | How to Handle |
---|---|
Null or empty word inserted. | Treat as a valid insertion (empty word has its own presence) or raise IllegalArgumentException based on requirements. |
Inserting the same word multiple times. | Increment the count of the word at the terminal node to reflect its multiple occurrences. |
Searching for an empty prefix. | Return the total number of words in the trie (count of root node occurrences) which will effectively give words starting with empty prefix. |
Erasing a word that doesn't exist. | Do nothing or raise an exception; ensure no underflow of counts at Trie nodes, and count does not dip below 0. |
Erasing a word with count > 1. | Decrement the count of the word at the terminal node; also update the count in the path (prefix words). |
Very long words are inserted, impacting memory usage. | Consider limiting the maximum word length or switching to a more memory-efficient Trie implementation if memory becomes a bottleneck (e.g., compressed trie). |
Inserting words with non-alphabetic characters (e.g., numbers, symbols). | Define a character set (alphabet) and handle characters outside that set, possibly raising an error or mapping them to a default character. |
Large number of insert/delete operations potentially leading to integer overflow of word counts. | Use a larger integer type (e.g., long) to store word counts to prevent overflow, and consider handling potential maximum count limits. |