Trie for Search Constraints | Dataford Interview Questions

TikTok search infrastructure needs fast exact-keyword and prefix checks for user queries. Implement a Trie that supports initial word insertion and a sequence of dynamic operations.

Formal Specification

Implement trie_operations(words, operations):

words is a list of lowercase strings inserted before any operation.
Each operation is a two-element list: ['insert', word], ['search', word], or ['startsWith', prefix].
Return a list containing one Boolean result for every search or startsWith operation, in their original order. Insert operations produce no result.
search returns True only when the complete word was inserted.
startsWith returns True when at least one inserted word begins with the given prefix.

Constraints

0 <= len(words), len(operations) <= 10^5
Every string contains only lowercase English letters
Each string has length at most 100
Duplicate insertions are allowed
The empty prefix is valid

Function Signature

def trie_operations(words, operations):

Your question is Trie for Search Constraints. Start with the requirements in the Question tab.

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

Problem