Design autocomplete with Trie
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Design and implement an autocomplete service using a prefix tree (Trie). Support operations insert(word, weight), update(word, newWeight), delete(word), and topK(prefix, k) that returns the k highest-weight words sharing the prefix, breaking ties lexicographically. Assume lowercase English letters. Explain the data structures you maintain at each node to make topK efficient, analyze time and space complexity for each operation, and discuss trade-offs (e.g., storing heaps/lists at nodes vs. computing on demand). Dry-run your solution on: insert('cat',
5), insert('car',
3), insert('cart',
8), insert('dog',
2), topK('ca',
2), update('car',
9), topK('ca',
2), delete('cart'), topK('ca',
2).
Quick Answer: This question evaluates understanding of Trie-based string indexing, augmented per-node metadata for efficient prefix queries, and algorithmic analysis of insert, update, delete, and topK operations including their time and space complexity.