Implement autocomplete with top-K suggestions
Overview
This question evaluates knowledge of data structures and algorithms for real-time autocomplete systems, including prefix indexing, frequency-based ranking and considerations for case-insensitivity and Unicode, as well as update, deletion, and streaming semantics.
Implement an autocomplete component that, given a history of query strings with frequencies, returns the top K suggestions for an input prefix in real time. Support updates when a query is entered again (frequency increases) and insertion of new queries. Specify tie-breaking (e.g., higher frequency, then lexicographic), case-insensitivity and Unicode handling, and limits on K. Describe and implement the core data structures (e.g., trie with per-node top-K min-heaps or balanced trees), and analyze time/space complexity for insert, update, and query. Discuss how to handle deletions, streaming updates, and large-scale memory usage.