Autocomplete Service with Tight Constraints

Design and implement an autocomplete service that processes a large, dynamic dictionary of words and provides real-time suggestions under strict performance and memory constraints.

Inputs

• A dictionary of up to 5,000,000 UTF-8 words. Words may contain accents and hyphens.
• Each word has an associated integer popularity score, which can change hourly.
• A real-time stream of keystrokes forming a prefix p.

Outputs

• After each keystroke, the service must return the top 5 suggestions that start with the current prefix p.
• Tie-breaking rules for suggestions: higher popularity score first, then lexicographical order.
• If fewer than 5 exact-prefix matches exist, backfill the remaining slots with suggestions that have an edit-distance of 1 from the prefix p.

Constraints

• Latency: 99th-percentile latency for queries must be less than 20 ms.
• Throughput: Support 5,000 queries per second (QPS).
• Memory: Total memory budget for the service must be less than or equal to 300 MB.
• Updates: Support approximately 1,000 inserts/deletes per second to the word dictionary.
• Matching: Case-insensitive matching with Unicode normalization (e.g., 'cafe' should match 'café').

Additional Considerations

Candidates should be prepared to discuss:

• The choice of data structure(s) (e.g., compressed trie, ternary search tree, DAWG, sorted arrays + binary search) and the rationale behind it.
• Strategies for maintaining per-prefix top-5 suggestions without excessive memory usage (e.g., small heaps, shared postings, lazy enumeration).
• Approaches for supporting dynamic updates and concurrent reads/writes with correctness guarantees.
• Methods for paginating beyond the initial 5 suggestions while preserving stable ordering.
• Time and space complexities of the proposed solution.
• Stress-test strategies and failure mitigations.
• Edge cases such as very long shared prefixes, non-ASCII input, and empty prefixes.