Implement streaming autocomplete under tight memory

Q: Implement streaming autocomplete under tight memory

This is a Coding & Algorithms interview question from Etsy for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Build an autocomplete service: Input: a list of up to 5,000,000 UTF-8 words (may include accents and hyphens), each with an integer popularity score that can change hourly; and a real-time stream of keystrokes forming a prefix p. Output: after each keystroke, return the top 5 suggestions that start with p, tie-breaking by higher popularity then lexicographic order. Constraints: 99th-percentile latency < 20 ms at 5,000 QPS; memory budget ≤ 300 MB; support ~1,000 inserts/deletes per second; case-insensitive matching with Unicode normalization (e.g., 'cafe' should match 'café'); if fewer than 5 exact-prefix matches exist, backfill with edit-distance-1 suggestions. Questions: Which data structure(s) would you choose (e.g., compressed trie, ternary search tree, DAWG, or sorted arrays + binary search) and why? How would you maintain per-prefix top-5 without exploding memory (e.g., small heaps, shared postings, or lazy enumeration)? How will you support dynamic updates and concurrent reads/writes with correctness guarantees? How do you paginate beyond 5 while preserving stable ordering? Provide time/space complexities and stress-test strategies. Discuss edge cases (very long shared prefixes, non-ASCII input, empty prefixes) and failure mitigations.

Implement streaming autocomplete under tight memory

Comments (0)