Implement Trie
Implement Trie Data Structure to support these operations:

insert(word) - To insert a string "word" in Trie search(word) - To check if string "word" is present in Trie or not. startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".

Three type of queries denote these operations:

Type 1: To insert a string "word" in Trie. 1 word Type 2: To check if the string "word" is present in Trie or not. 2 word Type 3: To check if there is any string in the Trie that starts with the given prefix string "word". 3 word

Input format :

The first line contains an Integer 'Q' which denotes the number of queries to be run. Then next 'Q' lines denote each query: The first and only line of each query contains the type of query and a string "word" separated by a single space.

Output format :

For each query of Type 2 print the string "true" if string "word" is present in Trie or "false" otherwise. For each query of Type 3 print the string "true" if there is any string in the Trie that starts with the given prefix string "word" or "false" otherwise. Output for every query will be printed in a separate line.

Note:

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Constraints :

1

Question

Implement Trie

Implement Trie Data Structure to support these operations:

insert(word) - To insert a string "word" in Trie
search(word) - To check if string "word" is present in Trie or not.
startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".

Three type of queries denote these operations:

Type 1: To insert a string "word" in Trie.
1 word

Type 2: To check if the string "word" is present in Trie or not.
2 word

Type 3: To check if there is any string in the Trie that starts with the given prefix string "word".
3 word

Input format :

The first line contains an Integer 'Q' which denotes the number of queries to be run. Then next 'Q' lines denote each query:

The first and only line of each query contains the type of query and a string "word" separated by a single space.

Output format :

For each query of Type 2 print the string "true" if string "word" is present in Trie or "false" otherwise.
For each query of Type 3 print the string "true" if there is any string in the Trie that starts with the given prefix string "word" or "false" otherwise.

Output for every query will be printed in a separate line.

Note:

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Constraints :

1 <= Q <= 5*10^4
1 <= W <= 10

Where 'Q' is the number of queries, and 'W' is the length of the "word".
All input of "word" will consist of only lowercase letters a-z.

Accepted Answer

Hashmap/Dictionary Approach

Firstly we have defined the node class of Trie having members:

child - storing the address of child nodes (hashmap of character number and address of Trie Node)
isEnd - a bool variable for marking this node as an end of some word.

Then we have defined our Trie Class having members:

root - The root node for whole Trie, every word starts from this node.
insert(word) - To insert a string "word" in Trie
search(word) - To check if string "word" is present in Trie or not.
startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".

Definition of insert(word):

Initialize the current node with the root node of Trie.
Iterate over the word from left to right and if there is no node present for the next character of the word then create a new node and store it in child member of the previous character’s node.
Keep updating the current node to the corresponding node for the next character of the word.
Finally, when we reached the end of the word, mark the isEnd member of the current node to true as it will denote the word is present or not.

Definition of search(word):

Initialize the current node with the root node of Trie.
Iterate over the word from left to right and if there is no node present for the next character of the word then return false as the word is not present in the Trie.
Keep updating the current node to the corresponding node for the next character of the word.
Finally, when we reached the end of the word, return the isEnd bool variable of the current node as it will denote the word is present or not.

Definition of startsWith(word):

Initialize the current node with the root node of Trie.
Iterate over the word from left to right and if there is no node present for the next character of the word then return false as the no word is present in the Trie with this word as a Prefix.
Keep updating the current node to the corresponding node for the next character of the word.
Finally, when we reached the end of the word, return true as some word must be present in the Trie as we are able to cover the whole prefix word.

Space Complexity: O(1)Explanation:

O(N*W) where N is the number of words inserted and W is the average length of words.

As we are making nodes of each character of a node so at max we can have all unique sequence of the words. This hashmap approach of storing child is more space-efficient than an array for storing child as we will only store the address for the nodes present in the Trie.

Time Complexity: O(1)Explanation:

O(N*W) (insert - O(W), search - O(W), startsWith - O(W))

where N is the number of queries and W is the average length of words.

For all the operations we are iterating over the word and checking in hashmap for the next character of the word so that’s an O(1) operation on average so Overall Time Complexity for insert, search, startsWith is O(W).

Accepted Answer

Array Approach

Firstly we have defined the node class of Trie having members:

child - storing the address of child nodes (Array of the address of Trie Nodes with size 26 initialized with NULL)
isEnd - a bool variable for marking this node as an end of some word.

Then we have defined our Trie Class having members:

root - The root node for whole Trie, every word starts from this node.
insert(word) - To insert a string "word" in Trie
search(word) - To check if string "word" is present in Trie or not.
startsWith(word) - To check if there is any string in the Trie that starts with the given prefix string "word".

Definition of insert(word):

Initialize the current node with the root node of Trie.
Iterate over the word from left to right and if there is NULL in the address of the node for the next character of the word then create a new node and store the address in child member of the previous character’s node.
Keep updating the current node to the corresponding node for the next character of the word.
Finally, when we reached the end of the word, mark the isEnd member of the current node to true as it will denote the word is present or not.

Definition of search(word):

Initialize the current node with the root node of Trie.
Iterate over the word from left to right and if there is NULL in the address of the node for the next character of the word then return false as the word is not present in the Trie.
Keep updating the current node to the corresponding node for the next character of the word.
Finally, when we reached the end of the word, return the isEnd bool variable of the current node as it will denote the word is present or not.

Definition of startsWith(word):

Initialize the current node with the root node of Trie.
Iterate over the word from left to right and if there is NULL in the address of the node for the next character of the word then return false as the no word is present in the Trie with this word as a Prefix.
Keep updating the current node to the corresponding node for the next character of the word.
Finally, when we reached the end of the word, return true as some word must be present in the Trie as we are able to cover the whole prefix word.

Space Complexity: O(1)Explanation:

O(N*W) where N is the number of words inserted and W is the average length of words.

As we are making nodes of each character of a node so at max we can have all unique sequence of the words. So overall space can be at max 26*N*W, so Overall Space Complexity is O(N*W)

Time Complexity: O(1)Explanation:

O(N*W) (insert - O(W), search - O(W), startsWith - O(W))

where N is the number of queries and W is the average length of words.

For all the operations we are iterating over the word and checking in the array for the next character of the word so Overall Time Complexity for insert, search, startsWith is O(W).

This array approach of storing child is more time-efficient than hashmap for storing child as the constant factor of O(1) in hashmaps is more costly.

Implement Trie Data Structure to support these operations:

Three type of queries denote these operations:

Input format :

Output format :

Note:

Constraints :

Top Samsung Frontend Developer Intern interview questions & answers

Popular interview questions of Frontend Developer Intern