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...
Dunzo Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter