Trie Data Structure Implementation
Design and implement a Trie (Prefix Tree) which should support the following two operations:
1. Insert a word into the Trie. The operation is marked as 'insert(word)'.
2. Search for a word in the Trie. The operation is marked as 'search(word)'.
The Trie is a tree-like data structure that efficiently stores a dynamic set of strings, where the keys are usually strings. Interactive operations like insert and search in a Trie significantly outperform those in naive data structures such as hashmaps and binary search trees in terms of time complexity.
Input/Output
Input:
The first input line contains an integer 'Q' indicating the number of queries.
Each query line contains an integer 'T' (indicating the type of query) followed by a space and a string 'WORD'.
Output:
For each Type 2 query, print 'TRUE' if 'WORD' is found in the Trie and 'FALSE' otherwise.
Example:
Input:
3
1 coding
1 code
2 coding
Output:
TRUE
Constraints:
- 1 <= Q <= 100000
- 1 <= |WORD| <= 20
- Each 'WORD' consists of lowercase alphabets (a-z) only.
Note:
Implement the requested functions and handle the input/output as per instruction. Do not format input/output within the function itself.
AnswerBot
5d
Implement a Trie data structure supporting insert and search operations efficiently.
Implement a Trie class with insert and search methods.
Use a nested class Node to represent each node in the Trie.
For...read more
Help your peers!
Add answer anonymously...
Top Dunzo Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app