{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Implement Trie – Solution & Complexity

Interview solutions
/
Implement Trie

1. Recognize the Pattern

The key pattern is: Trie edges share prefixes across inserted words. Identify the state and invariant before coding.

2. Build the Algorithm

Advance one state transition at a time. Mark or update state before exploring dependent work.

3. Check Edge Cases

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

4. Solution and Complexity

Time: O(total characters). Space: O(total inserted characters).

def trie_operations(operations: list[str], words: list[str]) -> list[int]:
    root, answer = {}, []
    for operation, word in zip(operations, words):
        node = root
        if operation == "insert":
            for char in word: node = node.setdefault(char, {})
            node["#"] = {}
        else:
            for char in word:
                if char not in node: node = None; break
                node = node[char]
            answer.append(int(node is not None and (operation == "startsWith" or "#" in node)))
    return answer

FAQ

See also

Practice Implement Trie online (run code in the browser)Design Add and Search Words solution (medium)Find Median from Data Stream solution (hard)LRU Cache solution (medium)Two Sum solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?