Prefix Tree (Trie) Simulatormedium

Prefix Tree (Trie) Simulator

medium Python for AI 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Build and query a prefix tree supporting dictionary insertion, exact lookup, and prefix matching.

Related Skills

Task

Implement simulate_trie(operations): simulate a Trie tree. Support operations insert, search (returns boolean indicating exact word match), and starts_with (returns boolean indicating if any inserted word starts with the prefix). Return list of booleans resulting from search and starts_with calls.

Function Signature

simulate_trie(operations: list[dict]) -> list[bool]

Examples

Example 1: Standard Trie Operations
Input: operations = [{'op': 'insert', 'word': 'apple'}, {'op': 'search', 'word': 'apple'}, {'op': 'search', 'word': 'app'}, {'op': 'starts_with', 'word': 'app'}, {'op': 'insert', 'word': 'app'}, {'op': 'search', 'word': 'app'}]
Output: [True, False, True, True]

Example 2: Prefix Exists But Not Word
Input: operations = [{'op': 'insert', 'word': 'neural'}, {'op': 'starts_with', 'word': 'neu'}, {'op': 'search', 'word': 'neu'}]
Output: [True, False]

Constraints

Libraries are allowed; a plain-Python solution earns 10 bonus points.
Search and starts_with operate in O(k) time where k is word length.
Words consist of lowercase alphabetical characters.

Python3Saved ✓

def simulate_trie(operations: list[dict]) -> list[bool]:

"""Simulate a Trie prefix tree with operations:

{'op': 'insert', 'word': w}, {'op': 'search', 'word': w}, {'op': 'starts_with', 'word': w}.

Return list of boolean results for search and starts_with operations."""

# Your implementation here

pass

Case 1: Standard Trie Operations

Input: operations = [{'op': 'insert', 'word': 'apple'}, {'op': 'search', 'word': 'apple'}, {'op': 'search', 'word': 'app'}, {'op': 'starts_with', 'word': 'app'}, {'op': 'insert', 'word': 'app'}, {'op': 'search', 'word': 'app'}]

Expected: [True, False, True, True]

Case 2: Prefix Exists But Not Word

Input: operations = [{'op': 'insert', 'word': 'neural'}, {'op': 'starts_with', 'word': 'neu'}, {'op': 'search', 'word': 'neu'}]

Expected: [True, False]