Lenpaste

About

Docs

Settings

plaintext, LF
 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