1# Trie Prefix Insert (Practice 4392): Scan
2
3Interviewers love trie prefix insert because it checks whether you can state the invariant before coding. Here is a compact rehearsal note.
4
5## Approach
6
7Nested dicts; mark end of word.
8
9```python
10class Trie:
11 def __init__(self):
12 self.root = {}
13 def insert(self, word):
14 node = self.root
15 for c in word:
16 node = node.setdefault(c, {})
17 node['#'] = True
18 def starts_with(self, prefix):
19 node = self.root
20 for c in prefix:
21 if c not in node: return False
22 node = node[c]
23 return True
24```
25
26## Complexity
27
28Linear in the dominant input size for the scan; heap/tree variants add a log factor.
29
30## Interview pitfalls
31
32State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode.
33
34## Practicing out loud
35
36Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see [https://www.linkjob.ai/](https://www.linkjob.ai/).
Created: Sat, 07 Nov 2026 22:31:04 +0000
Expires: Never