Skip to main content

18. Implement Trie (Prefix Tree)

mediumAsked at Electronic Arts

Build a trie supporting insert, search, and startsWith operations, a data structure EA uses in autocomplete for in-game chat and matchmaking search.

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

Problem

Implement a Trie class with insert(word), search(word), and startsWith(prefix) methods. insert adds a word to the trie, search returns true if word is in the trie, and startsWith returns true if any word in the trie starts with the given prefix.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters
  • At most 3 * 10^4 calls total to insert, search, and startsWith

Examples

Example 1

Input
insert("apple"); search("apple")
Output
true

Example 2

Input
search("app"); startsWith("app")
Output
false, true

Approaches

1. Nested objects as nodes

Use plain JS objects as trie nodes with a special end-marker key.

Time
O(m) per operation
Space
O(m*n)
class Trie {
  constructor() { this.root = {}; }
  insert(word) {
    let node = this.root;
    for (const c of word) node = node[c] = node[c] || {};
    node['#'] = true;
  }
  _find(str) {
    let node = this.root;
    for (const c of str) { if (!node[c]) return null; node = node[c]; }
    return node;
  }
  search(word) { const n = this._find(word); return !!(n && n['#']); }
  startsWith(prefix) { return this._find(prefix) !== null; }
}

Tradeoff:

2. Array-indexed TrieNode class

Use a TrieNode class with a 26-slot children array for O(1) character lookup. This is the canonical form EA interviewers expect for production-quality trie implementations.

Time
O(m) per operation
Space
O(m*26)
class TrieNode {
  constructor() { this.children = new Array(26).fill(null); this.end = false; }
}
class Trie {
  constructor() { this.root = new TrieNode(); }
  insert(word) {
    let node = this.root;
    for (const c of word) {
      const i = c.charCodeAt(0) - 97;
      if (!node.children[i]) node.children[i] = new TrieNode();
      node = node.children[i];
    }
    node.end = true;
  }
  _traverse(str) {
    let node = this.root;
    for (const c of str) {
      const i = c.charCodeAt(0) - 97;
      if (!node.children[i]) return null;
      node = node.children[i];
    }
    return node;
  }
  search(word) { const n = this._traverse(word); return !!(n && n.end); }
  startsWith(prefix) { return this._traverse(prefix) !== null; }
}

Tradeoff:

Electronic Arts-specific tips

EA interviews cover game development data structures, pathfinding (A*, BFS on grids), spatial algorithms, and simulation problems. Grid/matrix manipulation and BFS on 2D arrays are very common.

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 Electronic Arts interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →