You need search autocomplete that works offline: 500,000 candidate words, and on every keystroke you return the top 10 within 16ms. How do you design the data structure?
A Trie finds the prefix in O(length), and each node stores the top k candidates of its subtree ahead of time so a query answers in O(length + k). Updates come as a server-built snapshot that replaces the whole thing.
CS fundamentals and algorithmsShort answerBasics
You're building name search over a list of 10,000 contacts. How do linear search and…
#trie #search
iOS system designShort answerBasics
Design the search screen of a music app: autocomplete while typing, a results list, and…
#autocomplete #search
CS fundamentals and algorithmsShort answerBasics
Your app writes a network log file. Each line has the format userID(4 digits) pageName…
#top-k
ArchitectureMultiple choiceAdvanced
In this Coordinator implementation, LoginCoordinator stays in memory after the login flow…
#memory