Grokking the System Design Interview
Vote

0% completed

​

Designing Typeahead Suggestion

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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.

A

Anonymous

· 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
A

Anonymous

· 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

Reading Progress

0%

Vote for new content