{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Implement Trie – Solution & Complexity

Interview solutions
/
Implement Trie

Solution Walkthrough

  1. Step 1: Recognize the Pattern

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

  2. Step 2: Build the Algorithm

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

  3. Step 3: Check Edge Cases

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

  4. Step 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)Min Stack solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?