Skip to main content

20. Implement Trie (Prefix Tree)

mediumAsked at Activision

Build a trie supporting insert, search, and startsWith — Activision uses this to gauge prefix-tree fluency before chat-moderation banned-word lookup questions.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement a Trie class supporting insert(word), search(word) returning whether the exact word exists, and startsWith(prefix) returning whether any inserted word starts with the prefix.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • Words consist of lowercase letters
  • Up to 3 * 10^4 calls

Examples

Example 1

Input
ops=["Trie","insert","search","search","startsWith","insert","search"], args=[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
Output
[null,null,true,false,true,null,true]

Example 2

Input
insert("hello"); search("helloworld")
Output
false

Approaches

1. HashSet of words

Store words in set; iterate keys for startsWith.

Time
O(n) startsWith
Space
O(total chars)
// set lookup is O(1) for search, but startsWith degrades to O(n)

Tradeoff:

2. Trie nodes with children map

Each node holds child map and isEnd flag; walk character by character for each op.

Time
O(len) per op
Space
O(total chars)
class Trie {
  constructor() { this.root = {}; }
  insert(w) {
    let n = this.root;
    for (const c of w) n = n[c] ||= {};
    n.end = true;
  }
  _walk(w) {
    let n = this.root;
    for (const c of w) {
      if (!n[c]) return null;
      n = n[c];
    }
    return n;
  }
  search(w) { const n = this._walk(w); return !!(n && n.end); }
  startsWith(p) { return !!this._walk(p); }
}

Tradeoff:

Activision-specific tips

Activision wants you to surface the prefix-search shape explicitly — same structure they use for live chat-moderation banned-word matching with autocomplete fallback.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Implement Trie (Prefix Tree) and other Activision interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →