Grokking the System Design Interview

0% completed

​

Designing Typeahead Suggestion

1. What is Typeahead Suggestion?

Typeahead suggestions enable users to search for known and frequently searched terms. As the user types into the search box, it tries to predict the query based on the characters the user has entered and gives a list of suggestions to complete the query. Typeahead suggestions help the user to articulate their search queries better. It’s not about speeding up the search process but rather about guiding the users and lending them a helping hand in constructing their search query.

Try it yourself

Before looking at the solution, try designing it:

.....

.....

.....

Like the course? Get enrolled and start learning!
C

CQ

· 4 years ago

Why can't we use hash table of prefixes to achieve the same thing (instead of using trie)? We can have a word hash table storing (word, count) and a prefix hash table storing (prefix, top 10 reference to (word, count)). Each time we need to do an update, we first do a word table update. Let's say we have (CAPTAIN, 10) becoming (CAPTAIN, 11) Then we just enumerate all the prefixes of this word (for example, for CAPTAIN, we enumerate C, CA, CAP, CAPT ..) and then check if (CAPTAIN, 11) made to top 10. If yes, replace that row of the prefix table When we query, we just fetch one single row from prefix table. We can do batch offline update & partitioning similarly (probly even easier this way) and the rows that we need for prefix table is about the same as the node of tries.

Show 1 reply
J

Junaid Effendi

· 4 years ago

Isn't this true for all types of partitioning?

""" Partitioning based on the maximum capacity can still lead us to hotspots, e.g., if there are a lot of queries for terms starting with ‘cap’, the server holding it will have a high load compared to others. """

Even with hash, cap will produce same hash thus same server so hotspot can still occur?

Show 1 reply
J

Jessie

· 3 years ago

I'm just curious why this system design would go through the process of building up and storing trees over and over vs using an existing implementation of a graph based database? The only thing I can really come up with is maybe some added efficiency by having data in memory and the access time of a db being potentially a bit slower, but it seems like they might also have some built in efficiencies that you may not be able to, or knowledgeable enough to recreate.

J

jerrytansk

· 10 days ago

instead of dealing with tries and serialization and deserialization into a file format for persistence on disk and all that, why don't we just drop in a elasticsearch cluster. It supports prefix based queries and takes care of all these problems for you, at scale. The drawback is the additional complexity it requires, but any production system at scale would require a system as complex as elasticsearch anyway.