Explain how you would design and implement a trie (prefix tree) data structure that supports inserting a word, searching for an exact word, and checking if any word starts with a given prefix.
For example, after inserting "apple": search("apple") returns true, search("app") returns false, startsWith("app") returns true.
Explain the design of the data structure, how each operation works, and state the time and space complexity.
How to approach it
- Hint 1
Think about what each node in the trie needs to store: links to children and whether it marks the end of a word.
- Hint 2
Each node has up to 26 children (for lowercase English letters) and a boolean flag for end-of-word.
- Hint 3
Insert traverses or creates nodes for each character. Search traverses and checks the end flag. StartsWith traverses without checking the end flag.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.