← All mock interviewsHints used: 0

Implement Trie (Prefix Tree) Mock Interview

  1. ✓Problem→
  2. 2Clarifying Questions→
  3. 3Constraints→
  4. 4Brute Force→
  5. 5Complexity Analysis→
  6. 6Pattern Recognition→
  7. 7Optimized Solution→
  8. 8Implementation→
  9. 9Testing→
  10. 10Follow-Up→
  11. 11Evaluation
Problem

Design a data structure Trie supporting three operations: insert(word) adds a word, search(word) returns true if the exact word was previously inserted, and startsWith(prefix) returns true if any inserted word begins with prefix. All strings consist of lowercase English letters. The structure will receive up to 3·10^4 mixed operations.

Constraints
  • 1 ≤ word.length, prefix.length ≤ 2000
  • total operations ≤ 3·10^4
  • lowercase a–z only
Example
in: insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")
out: true, false, true, true

Clarify

Before choosing anything: what would you ask the interviewer? What assumptions are you making? (Duplicates? Empty input? Value ranges? What to return when there is no answer?)