Trie autocomplete engine

Before any traversal, settle on the shape of a single TrieNode. The classic representation stores children as a fixed 26-slot array; the practical one uses a Map<string, TrieNode> (or a plain object) so the alphabet is open and memory scales with the actual character set, not the worst-case one. Each node needs three things: its children, a boolean that marks it as the terminus of a valid word, and the weight associated with that word (zero or absent when the node is not a terminus). The weight lives on the terminal node, not on the edge leading to it, because a prefix shares edges with many words and you cannot record all their weights on one edge. Choosing the wrong representation here forces a full rewrite in the next milestone, so reason through memory layout explicitly: a 26-slot array wastes 26 × pointer_size for every interior node even when only one child is present, which is fine at thousands of words but painful at millions. Document your choice and its trade-off before writing the class.

Implement the three simplest operations and get their complexity guarantees exactly right. insert(word, weight) walks from the root, creating nodes as needed, then marks the final node as a terminus and records its weight. has(word) walks the same path and returns true only if the last node exists and is marked as a terminus — returning true for a stored prefix but not a full word is the classic off-by-one bug here. startsWith(prefix) is identical to has but stops at the prefix node and returns true if that node exists at all, regardless of isEnd — this is the operation that makes tries efficient for autocomplete. All three are O(k) where k is the length of the input string; a recursive implementation is fine but an iterative one avoids call-stack pressure for long strings. Weight update semantics: if insert is called twice on the same word, overwrite the weight rather than accumulating it — the test suite asserts this.

Implement the subtree traversal that autocomplete is built on: given a prefix, navigate to the prefix node, then run a depth-first search from that node to collect every terminus with its word and weight. This is an O(prefix + subtree_size) operation — the subtree can be large (every word that shares the prefix), so the DFS must not allocate per-node structures beyond the recursion stack or a small queue; just accumulate (word, weight) pairs. Building the candidate word as you recurse is a standard trick: pass the accumulated string down the DFS rather than reconstructing it from the path. A missing prefix (no node for the last character) must return an empty collector, not throw — this is the case autocomplete sees on every keypress before the user has typed a recognized prefix. The output of this step is an unsorted array of all matching (word, weight) pairs; ranking happens in the next milestone.

Turn the unsorted candidate list from the previous milestone into a ranked, capped result. Sort the collected (word, weight) pairs by weight descending, and when weights are equal, by word lexicographically ascending — this tie-breaking rule is what makes autocomplete output predictable across runs and test-able with exact assertions. Take only the first k pairs and return their words as a string array. The naive approach — collect all, sort all, slice — is correct and fine for thousands of words. At senior depth you should recognize when a min-heap of size k beats the sort: if the subtree has N words, collecting all then sorting is O(N log N); maintaining a k-size heap during the DFS is O(N log k) and avoids materializing the full candidate list, which matters when k << N. Implement the naive sort first, then state the heap alternative as a comment rather than premature-optimizing.

Make the trie respond correctly to weight changes and deletions without rebuilding. Calling insert on an already-stored word must overwrite its weight in place (the node already exists, just update its weight field), and the change must immediately be reflected in the next autocomplete call without any cache invalidation step — because there is no cache; the DFS recomputes rankings on each call. Deletion (if you choose to implement it) is trickier: you must clear the isEnd flag and zero the weight, then optionally prune leaf nodes that have no valid-word descendants to save memory, but pruning is not required for correctness. The subtle bug to avoid is stale aggregate state: some trie implementations cache a 'max weight in subtree' on interior nodes to prune DFS early; if you do that, a weight update must propagate the new maximum up the ancestor chain. Decide upfront whether you want that optimization and what consistency invariant you commit to maintaining.

Benchmark your implementation against a flat Map alternative and articulate when one beats the other. A flat Map<string, number> (word → weight) supports insert and has in O(k) hash time, autocomplete in O(N × k) scan-all time, where N is the total word count. For small dictionaries the flat Map often wins on memory because a trie allocates one node per character, not one entry per word. The trie wins when prefix queries are frequent and the dictionary is large: O(prefix + results) beats O(N) for autocomplete when N >> results. Measure peak node count after inserting a realistic word list (e.g. 5 000 English words), compute approximate memory per node (Map entry ≈ 64 bytes on V8, node with Map children ≈ 96–128 bytes), and write a comment stating the crossover point — the word count and query pattern at which the trie starts paying for itself in query speed vs memory overhead. This is the kind of analysis a senior engineer does before choosing a data structure in production.