Implement Trie (Prefix Tree)

🎯

Implement Trie (Prefix Tree)

mediumTRIEAmazonGoogleFacebook

Imagine you are building a search autocomplete feature that suggests words as you type. Efficiently storing and querying prefixes is key to a smooth user experience.

💡 This problem introduces the Trie data structure, which is a tree-like structure used to store strings efficiently by sharing common prefixes. Beginners often struggle because it requires understanding how to represent nodes and manage children dynamically, unlike arrays or linked lists.

📋

Problem Statement

Design a data structure that supports the following operations: insert a word, search for a word, and check if any word starts with a given prefix. Implement the Trie class with methods insert(word), search(word), and startsWith(prefix).

1 ≤ total number of calls to insert, search, and startsWith ≤ 10^5All inputs consist of lowercase English letters a-z1 ≤ length of word or prefix ≤ 2000

💡

Example

Input"insert('apple'), search('apple'), search('app'), startsWith('app'), insert('app'), search('app')"

Outputnull, true, false, true, null, true

After inserting 'apple', searching 'apple' returns true. Searching 'app' returns false because 'app' was not inserted as a word. startsWith('app') returns true because 'apple' starts with 'app'. After inserting 'app', searching 'app' returns true.

• search for empty string → false (empty strings are not inserted)
• startsWith empty string → true (every word starts with empty prefix)
• insert duplicate words → no error, trie structure remains valid
• search for prefix that is a full word → true if inserted, false otherwise

⚠️

Common Mistakes

Not marking isEnd flag after insertion

Search returns false for words that were inserted

✅ Set isEnd = True on the last node after inserting a word

Using fixed-size arrays but indexing incorrectly (e.g., off-by-one)

Index errors or wrong children accessed, causing wrong search results or crashes

✅ Always map characters to indices by subtracting 'a' and ensure indices are 0-25

Confusing startsWith with search and requiring isEnd flag for startsWith

startsWith returns false even if prefix exists

✅ For startsWith, only check if traversal succeeds, do not check isEnd

Not handling empty strings or empty prefixes properly

Unexpected false or true results, or runtime errors

✅ Decide on behavior for empty inputs and handle them explicitly

Using recursion for insert/search leading to stack overflow on long words

Runtime errors on deep recursion

✅ Use iterative loops for traversal instead of recursion

🧠

Brute Force (Using List of Words)

💡 This approach uses a simple list to store all inserted words and checks search and prefix queries by scanning the list. It is straightforward but inefficient, helping beginners understand the problem before optimizing.

Intuition

Store all words in a list. For search, check if the word is in the list. For startsWith, check if any word in the list starts with the prefix.

Algorithm

1. Initialize an empty list to store words.
2. To insert a word, append it to the list.
3. To search a word, iterate over the list and check for equality.
4. To check startsWith, iterate over the list and check if any word starts with the prefix.

💡 This algorithm is easy to implement but inefficient because it scans all words for every query, which is slow for large inputs.

</>

Code

class Trie:
    def __init__(self):
        self.words = []

    def insert(self, word: str) -> None:
        self.words.append(word)

    def search(self, word: str) -> bool:
        for w in self.words:
            if w == word:
                return True
        return False

    def startsWith(self, prefix: str) -> bool:
        for w in self.words:
            if w.startswith(prefix):
                return True
        return False

# Driver code
trie = Trie()
trie.insert('apple')
print(trie.search('apple'))  # True
print(trie.search('app'))    # False
print(trie.startsWith('app')) # True
trie.insert('app')
print(trie.search('app'))    # True

Line Notes

self.words = []Initialize storage for all inserted words

self.words.append(word)Add new word to the list

for w in self.words:Scan all words to find a match

if w == word:Check exact word equality for search

if w.startswith(prefix):Check prefix match for startsWith

import java.util.*;

class Trie {
    private List<String> words;

    public Trie() {
        words = new ArrayList<>();
    }

    public void insert(String word) {
        words.add(word);
    }

    public boolean search(String word) {
        for (String w : words) {
            if (w.equals(word)) {
                return true;
            }
        }
        return false;
    }

    public boolean startsWith(String prefix) {
        for (String w : words) {
            if (w.startsWith(prefix)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple")); // true
        System.out.println(trie.search("app"));   // false
        System.out.println(trie.startsWith("app")); // true
        trie.insert("app");
        System.out.println(trie.search("app"));   // true
    }
}

Line Notes

words = new ArrayList<>();Initialize list to store words

words.add(word);Add word to list on insert

for (String w : words)Iterate all words for search and prefix checks

if (w.equals(word))Check exact word equality

if (w.startsWith(prefix))Check if word starts with prefix

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Trie {
    vector<string> words;
public:
    Trie() {}

    void insert(string word) {
        words.push_back(word);
    }

    bool search(string word) {
        for (auto &w : words) {
            if (w == word) return true;
        }
        return false;
    }

    bool startsWith(string prefix) {
        for (auto &w : words) {
            if (w.compare(0, prefix.size(), prefix) == 0) return true;
        }
        return false;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    cout << boolalpha << trie.search("apple") << endl; // true
    cout << trie.search("app") << endl; // false
    cout << trie.startsWith("app") << endl; // true
    trie.insert("app");
    cout << trie.search("app") << endl; // true
    return 0;
}

Line Notes

vector<string> words;Store all inserted words in a vector

words.push_back(word);Add word to vector on insert

for (auto &w : words)Loop over all words for search and prefix

if (w == word)Check exact word equality

w.compare(0, prefix.size(), prefix) == 0Check if word starts with prefix

class Trie {
    constructor() {
        this.words = [];
    }

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

    search(word) {
        for (const w of this.words) {
            if (w === word) return true;
        }
        return false;
    }

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

// Driver code
const trie = new Trie();
trie.insert('apple');
console.log(trie.search('apple')); // true
console.log(trie.search('app'));   // false
console.log(trie.startsWith('app')); // true
trie.insert('app');
console.log(trie.search('app'));   // true

Line Notes

this.words = []Initialize array to hold all words

this.words.push(word)Add word to array on insert

for (const w of this.words)Iterate all words for search and prefix

if (w === word)Check exact word equality

if (w.startsWith(prefix))Check if word starts with prefix

⏱

Complexity

TimeO(n * m) per query, where n is number of words and m is length of word/prefix

SpaceO(n * m) to store all words explicitly

Each search or startsWith scans all stored words, checking equality or prefix match, leading to linear time in number of words and length.

💡 For 100,000 words each of length 10, a single search could do up to 1 million character comparisons, which is very slow.

Interview Verdict: Accepted but inefficient; not suitable for large inputs

This approach works but is too slow for large datasets, motivating the need for a more efficient Trie structure.

🧠

Trie Using Fixed-Size Array for Children

💡 This approach implements a Trie node with a fixed array of size 26 for each lowercase English letter, improving search and insert to O(m) time where m is word length. It introduces the core Trie concept.

Intuition

Each node has an array of 26 children pointers, one for each letter. Insert and search traverse nodes corresponding to each character. Mark nodes where words end.

Algorithm

1. Define a TrieNode class with an array of 26 children and a boolean isEnd flag.
2. Initialize root as an empty TrieNode.
3. To insert, traverse the Trie creating nodes for characters if missing, mark last node's isEnd true.
4. To search, traverse nodes for each character; return true if last node's isEnd is true.
5. To startsWith, traverse nodes for prefix; return true if traversal succeeds.

💡 This algorithm efficiently shares prefixes and avoids redundant storage, making queries fast and memory usage reasonable.

</>

Code

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def _charToIndex(self, ch):
        return ord(ch) - ord('a')

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            idx = self._charToIndex(ch)
            if not node.children[idx]:
                node.children[idx] = TrieNode()
            node = node.children[idx]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            idx = self._charToIndex(ch)
            if not node.children[idx]:
                return False
            node = node.children[idx]
        return node.isEnd

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            idx = self._charToIndex(ch)
            if not node.children[idx]:
                return False
            node = node.children[idx]
        return True

# Driver code
trie = Trie()
trie.insert('apple')
print(trie.search('apple'))  # True
print(trie.search('app'))    # False
print(trie.startsWith('app')) # True
trie.insert('app')
print(trie.search('app'))    # True

Line Notes

self.children = [None] * 26Initialize fixed array for 26 lowercase letters

self.isEnd = FalseFlag to mark end of a valid word

idx = self._charToIndex(ch)Convert character to index 0-25

if not node.children[idx]Create new node if path does not exist

node.isEnd = TrueMark current node as end of inserted word

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    private int charToIndex(char ch) {
        return ch - 'a';
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int idx = charToIndex(ch);
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int idx = charToIndex(ch);
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            int idx = charToIndex(ch);
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple")); // true
        System.out.println(trie.search("app"));   // false
        System.out.println(trie.startsWith("app")); // true
        trie.insert("app");
        System.out.println(trie.search("app"));   // true
    }
}

Line Notes

TrieNode[] children = new TrieNode[26];Fixed array for children nodes representing letters

boolean isEnd = false;Marks if node ends a valid word

int idx = charToIndex(ch);Map character to array index

if (node.children[idx] == null)Create child node if missing

node.isEnd = true;Mark end of word after insertion

#include <iostream>
#include <string>
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
        isEnd = false;
    }
};

class Trie {
    TrieNode* root;
    int charToIndex(char ch) {
        return ch - 'a';
    }
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = charToIndex(ch);
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = charToIndex(ch);
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return node->isEnd;
    }

    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            int idx = charToIndex(ch);
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    cout << boolalpha << trie.search("apple") << endl; // true
    cout << trie.search("app") << endl; // false
    cout << trie.startsWith("app") << endl; // true
    trie.insert("app");
    cout << trie.search("app") << endl; // true
    return 0;
}

Line Notes

TrieNode* children[26];Array of pointers for each letter child

isEnd = false;Flag to mark end of word

int idx = charToIndex(ch);Convert char to index 0-25

if (!node->children[idx])Create new node if child missing

node->isEnd = true;Mark node as end of inserted word

class TrieNode {
    constructor() {
        this.children = new Array(26).fill(null);
        this.isEnd = false;
    }
}

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

    _charToIndex(ch) {
        return ch.charCodeAt(0) - 'a'.charCodeAt(0);
    }

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

    search(word) {
        let node = this.root;
        for (const ch of word) {
            const idx = this._charToIndex(ch);
            if (!node.children[idx]) return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }

    startsWith(prefix) {
        let node = this.root;
        for (const ch of prefix) {
            const idx = this._charToIndex(ch);
            if (!node.children[idx]) return false;
            node = node.children[idx];
        }
        return true;
    }
}

// Driver code
const trie = new Trie();
trie.insert('apple');
console.log(trie.search('apple')); // true
console.log(trie.search('app'));   // false
console.log(trie.startsWith('app')); // true
trie.insert('app');
console.log(trie.search('app'));   // true

Line Notes

this.children = new Array(26).fill(null);Initialize fixed-size array for children

this.isEnd = false;Flag to mark end of word

const idx = this._charToIndex(ch);Map character to index 0-25

if (!node.children[idx])Create new node if child missing

node.isEnd = true;Mark node as end of inserted word

⏱

Complexity

TimeO(m) per insert/search/startsWith, where m is length of word or prefix

SpaceO(n * m) in worst case for n words of length m due to node creation

Each operation traverses at most m nodes, constant time per character. Space grows with unique prefixes stored.

💡 For words of length 10, each operation takes roughly 10 steps, which is very efficient compared to scanning all words.

Interview Verdict: Accepted and efficient for interview use

This is the standard Trie implementation expected in interviews for prefix-based queries.

🧠

Trie Using Hash Map for Children (Dynamic Alphabet Support)

💡 This approach uses a hash map/dictionary for children instead of fixed arrays, allowing support for larger or dynamic alphabets and potentially saving space when nodes have few children.

Intuition

Each node stores a map from character to child node. Insert and search traverse the map entries. This is more flexible but slightly slower than fixed arrays.

Algorithm

1. Define a TrieNode class with a dictionary/map for children and an isEnd flag.
2. Initialize root as an empty TrieNode.
3. To insert, for each character, add a new node in the map if missing, then move to that node.
4. Mark the last node's isEnd as true after insertion.
5. To search or startsWith, traverse the map for each character; return accordingly.

💡 This algorithm trades off some speed for flexibility and memory efficiency when the alphabet is large or sparse.

</>

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.isEnd

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

# Driver code
trie = Trie()
trie.insert('apple')
print(trie.search('apple'))  # True
print(trie.search('app'))    # False
print(trie.startsWith('app')) # True
trie.insert('app')
print(trie.search('app'))    # True

Line Notes

self.children = {}Use dictionary to store children dynamically

if ch not in node.childrenCheck if child node exists for character

node.children[ch] = TrieNode()Create new child node if missing

node.isEnd = TrueMark node as end of word after insertion

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) return false;
            node = node.children.get(ch);
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (!node.children.containsKey(ch)) return false;
            node = node.children.get(ch);
        }
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple")); // true
        System.out.println(trie.search("app"));   // false
        System.out.println(trie.startsWith("app")); // true
        trie.insert("app");
        System.out.println(trie.search("app"));   // true
    }
}

Line Notes

Map<Character, TrieNode> children = new HashMap<>();Use HashMap for dynamic children storage

node.children.putIfAbsent(ch, new TrieNode());Add child node if missing

node.children.get(ch);Retrieve child node for character

node.isEnd = true;Mark end of word after insertion

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEnd;
    TrieNode() : isEnd(false) {}
};

class Trie {
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) return false;
            node = node->children[ch];
        }
        return node->isEnd;
    }

    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            if (node->children.find(ch) == node->children.end()) return false;
            node = node->children[ch];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    cout << boolalpha << trie.search("apple") << endl; // true
    cout << trie.search("app") << endl; // false
    cout << trie.startsWith("app") << endl; // true
    trie.insert("app");
    cout << trie.search("app") << endl; // true
    return 0;
}

Line Notes

unordered_map<char, TrieNode*> children;Use hash map for children to save space

if (node->children.find(ch) == node->children.end())Check if child exists

node->children[ch] = new TrieNode();Create new child node if missing

node->isEnd = true;Mark node as end of word

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEnd = false;
    }
}

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

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

    search(word) {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) return false;
            node = node.children.get(ch);
        }
        return node.isEnd;
    }

    startsWith(prefix) {
        let node = this.root;
        for (const ch of prefix) {
            if (!node.children.has(ch)) return false;
            node = node.children.get(ch);
        }
        return true;
    }
}

// Driver code
const trie = new Trie();
trie.insert('apple');
console.log(trie.search('apple')); // true
console.log(trie.search('app'));   // false
console.log(trie.startsWith('app')); // true
trie.insert('app');
console.log(trie.search('app'));   // true

Line Notes

this.children = new Map();Use Map for dynamic children storage

if (!node.children.has(ch))Check if child node exists

node.children.set(ch, new TrieNode());Create new child node if missing

node.isEnd = true;Mark node as end of word after insertion

⏱

Complexity

TimeO(m) per insert/search/startsWith, where m is length of word or prefix

SpaceO(n * m) in worst case, but can be more space efficient than fixed arrays if alphabet is large

Operations traverse nodes for each character. Using maps reduces space when nodes have few children but may add slight overhead.

💡 For large alphabets or sparse tries, this approach saves memory by not allocating large arrays for every node.

Interview Verdict: Accepted and flexible; good for large or dynamic alphabets

This approach is preferred when the alphabet is large or unknown, trading a bit of speed for memory efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 (fixed-size array Trie) is the best balance of speed and simplicity to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (List of Words)	O(n * m) per query	O(n * m)	No	N/A	Mention only - never code
2. Trie with Fixed-Size Array	O(m) per query	O(n * m)	No	Yes	Code this in 95% of interviews
3. Trie with Hash Map Children	O(m) per query (slightly slower)	O(n * m) but more space efficient for large alphabets	No	Yes	Use when alphabet is large or unknown

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying requirements, then explain the brute force approach to show understanding. Progress to efficient Trie implementations, and finally discuss tradeoffs and edge cases.

How to Present

Step 1: Clarify the problem and confirm input constraints.Step 2: Describe the brute force approach using a list to store words.Step 3: Introduce the Trie data structure with fixed-size arrays for children.Step 4: Explain how to implement insert, search, and startsWith efficiently.Step 5: Optionally discuss using hash maps for children to handle dynamic alphabets.Step 6: Write clean, tested code and discuss edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewers check your understanding of Trie structure, ability to implement node-based trees, handle edge cases, and optimize for time and space.

Common Follow-ups

• How would you modify the Trie to support deletion of words? → Use reference counts or lazy deletion flags.
• How to optimize space if the alphabet is large? → Use hash maps or compressed tries (Radix trees).

💡 These follow-ups test your ability to extend the basic Trie and optimize for real-world constraints.

🔍

Pattern Recognition

When to Use

1) Need to store many strings efficiently, 2) Queries involve prefix matching, 3) Fast insert/search required, 4) Alphabet is fixed or known

Signature Phrases

search for a wordstarts with a prefixinsert words efficiently

NOT This Pattern When

Problems that require substring search or suffix trees are different patterns.

Similar Problems

Add and Search Word - Data structure design - extends Trie with wildcard supportImplement Magic Dictionary - uses Trie for approximate matching

Practice

1. Consider the following Python code snippet implementing the optimal approach to count pairs with XOR less than a limit using a bitwise trie. Given the input nums = [1, 4, 2], and limit = 3, what is the final return value of countPairsLessThan(nums, limit)?

easy

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Trace insertions and queries for nums=[1,4,2], limit=3

   Initially, trie is empty. For num=1, query returns 0 (no previous numbers), then insert 1. For num=4, query counts pairs with XOR<3 with 1, which is 1 (1^4=5>3, so 0), then insert 4. For num=2, query counts pairs with XOR<3 with {1,4}. 2^1=3 (not less than 3), 2^4=6>3, so 0. Total count is 0+0+0=0, but careful: the code counts pairs less than limit, so XOR<3 means XOR<3, not <=3.

2. Step 2: Adjust for less than limit (3) meaning XOR values 0,1,2

   Pairs: (1,4)=5>3 no, (1,2)=3 not less than 3 no, (4,2)=6 no. So count is 0. But code counts pairs as we insert, so final result is 0.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Code counts pairs with XOR < limit, result is 0 for limit=3 [OK]

Hint: XOR less than limit excludes pairs equal to limit [OK]

Common Mistakes:

• Counting pairs with XOR <= limit instead of < limit
• Off-by-one in bit traversal
• Miscounting pairs before insertion

2. You are building a feature that, given a list of product names and a search query typed character-by-character, returns up to three lexicographically smallest products starting with the current prefix after each character is typed. Which algorithmic approach best guarantees efficient retrieval of these suggestions for every prefix?

easy

A. Build a trie from the sorted product list and store up to three suggestions at each node to retrieve suggestions efficiently.

B. Use a brute force approach that filters and sorts the entire product list for each prefix typed.

C. Apply dynamic programming to precompute all possible prefix matches and their top suggestions.

D. Use a greedy algorithm that picks the first three products starting with the prefix without sorting.

Solution

1. Step 1: Understand the problem requirements

   The problem requires returning up to three lexicographically smallest products for every prefix of the search word efficiently.

2. Step 2: Evaluate algorithmic approaches

   Brute force filtering and sorting for each prefix is inefficient. Dynamic programming is not suitable for prefix-based retrieval. A greedy approach without sorting fails lex order requirements. Building a trie with stored top 3 suggestions at each node allows O(m) retrieval where m is prefix length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie with stored suggestions matches problem constraints and efficiency [OK]

Hint: Trie with stored suggestions enables fast prefix queries [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing DP with prefix search
• Ignoring lexicographic order in greedy approach

3. Consider the following Python code implementing the optimal StreamChecker. Given the words ["cd", "f", "kl"], what is the return value of the query sequence: query('a'), query('b'), query('c'), query('d')? Specifically, what does query('d') return?

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in reversed(word):
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

sc = StreamChecker(["cd", "f", "kl"])
print(sc.query('a'))
print(sc.query('b'))
print(sc.query('c'))
print(sc.query('d'))

easy

A. False

B. True

C. Raises an exception

D. None

Solution

1. Step 1: Trace the stream buffer after queries

   After queries 'a', 'b', 'c', 'd', the stream buffer contains ['a','b','c','d'], but max_len=2, so oldest letters are popped. After 'c', stream=['b','c'], after 'd', stream=['c','d'].

2. Step 2: Traverse trie with reversed stream

   For query('d'), reversed stream is ['d','c']. Trie has reversed words: 'dc' for 'cd'. Traversing 'd' then 'c' hits is_word=True at 'c' node, so returns True. However, the query sequence is query('a'), query('b'), query('c'), query('d'). The query('c') returns False because 'c' alone is not a word. The query('d') returns True because 'cd' is in the dictionary and the stream buffer contains ['c','d'].

3. Step 3: Check query('d') return value

   Since the query('d') returns True, the correct answer is True.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Stream buffer limited to max word length matches 'cd' suffix [OK]

Hint: Stream buffer limited to max word length [OK]

Common Mistakes:

• Not limiting stream buffer size
• Not reversing words in trie
• Returning false too early

4. The following code attempts to implement the optimal StreamChecker. Identify the single line that contains a subtle bug that can cause incorrect results or inefficiency.

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in word:  # Bug here: words not reversed
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

medium

A. Line: for ch in word:

B. Line: if len(self.stream) > self.max_len:

C. Line: for ch in reversed(self.stream):

D. Line: if node.is_word:

Solution

1. Step 1: Identify how trie is built

   The code inserts words in forward order instead of reversed order, which breaks suffix matching logic.

2. Step 2: Understand impact on query

   Query traverses reversed stream, expecting reversed trie. Since trie is built forward, traversal fails to find matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reversing words during trie build is essential for suffix queries [OK]

Hint: Trie must be built with reversed words for suffix matching [OK]

Common Mistakes:

• Not reversing words when building trie
• Not limiting stream buffer
• Returning false too early

5. Suppose the problem is modified so that pairs can be counted multiple times if elements are reused (i.e., pairs (i, j) with i and j possibly equal). Which modification to the bitwise trie approach correctly handles this scenario?

hard

A. Modify the query function to include the current number in the trie before querying to count pairs with itself.

B. No change needed; the existing approach already counts pairs with reuse.

C. Insert all numbers into the trie first, then for each number query the trie for counts less than limit, allowing reuse.

D. Use a frequency map instead of a trie since reuse breaks trie assumptions.

Solution

1. Step 1: Understand reuse means pairs can include the same element twice

   Counting pairs with i == j means the current number must be considered in queries.

2. Step 2: Modify insertion and query order

   Insert the current number into the trie before querying so it can pair with itself and others, enabling reuse counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inserting before querying allows counting pairs including the current element [OK]

Hint: Insert before query to count pairs with reuse [OK]

Common Mistakes:

• Assuming no change needed
• Inserting after query (misses self pairs)
• Switching to frequency map unnecessarily