Skip to main content

22. Implement Trie (Prefix Tree)

mediumAsked at Roblox

Build a prefix tree supporting insert, search, and startsWith — Roblox applies tries for autocomplete in the asset catalog, fast chat-filter prefix matching, and resolving shortened asset-name queries across millions of game items.

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

Problem

Implement a Trie class with the following methods: insert(word) inserts the string into the trie; search(word) returns true if the exact word exists; startsWith(prefix) returns true if any word in the trie has the given prefix.

Constraints

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

Examples

Example 1

Input
Trie(); insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")
Output
[null, null, true, false, true, null, true]

Approaches

1. Brute force — Set for exact search, linear scan for prefix

Store all words in a Set for O(1) exact lookup. For startsWith, iterate every stored word checking String.startsWith — O(n*L) per prefix query.

Time
O(n*L) per startsWith
Space
O(n*L)
class Trie {
  constructor() {
    this.words = new Set();
  }

  insert(word) {
    this.words.add(word);
  }

  search(word) {
    return this.words.has(word);
  }

  startsWith(prefix) {
    for (const w of this.words) {
      if (w.startsWith(prefix)) return true;
    }
    return false;
  }
}

Tradeoff:

2. Optimal — trie node with children map

Each node holds a children map and an isEnd flag. Insert and lookup traverse the path character by character in O(L) time, with prefix queries stopping as soon as the prefix path exists.

Time
O(L) per operation
Space
O(total characters inserted)
class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  _traverse(str) {
    let node = this.root;
    for (const ch of str) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }

  search(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }
}

Tradeoff:

Roblox-specific tips

Roblox interviewers ask about tries because the asset catalog and UGC search have real prefix-query SLAs. They appreciate candidates who mention the space trade-off: a 26-element array per node (faster) vs. a Map (lower memory for sparse alphabets). For Roblox's multilingual chat system, a Map wins because emoji and non-ASCII characters make fixed arrays impractical.

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

Practice these live with InterviewChamp.AI →