Trie Data Structure Implementation | Dataford Interview Questions

Your question is Trie Data Structure Implementation. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Quantcast may need to index keyword and prefix signals efficiently. Implement a trie with insert, search, and startsWith operations.

Create a Trie class with these methods:

insert(word): Add a lowercase word to the trie.
search(word): Return True only when the complete word has been inserted.
startsWith(prefix): Return True when at least one inserted word begins with prefix.

For automated evaluation, implement process_trie_operations(operations). Each operation is a dictionary with op equal to insert, search, or startsWith, and a word field. The function must return results only for search and startsWith operations, in their original order.

Formal Specification

Input: A list of operation dictionaries, where each dictionary has op: str and word: str.
Output: A list of booleans produced by search and startsWith operations.
Words contain only lowercase English letters and are nonempty.

Constraints

1 <= len(operations) <= 10^4
1 <= len(word) <= 100
Words contain only lowercase English letters
At most 5 * 10^3 distinct words are inserted
Operations are processed in order

Function Signature

def process_trie_operations(operations):