Geek asks and answers

Backup for autocomplete

This is an interview question: design a distributed server for autocomplete.

I would answer this as follows:

AutoFill is a dictionary search for a given suffix. The dictionary should probably be organized as a trie. The dictionary is built from the most common queries, but this is another story.

Now I assume that the dictionary often does not change (for example, once a day, and not every millisecond). Thus, we can simply replicate the dictionary on several servers that process automatic requests (for example, using load balancing and circular policy).

We should also think of a dictionary, but this is another story.

Does it make sense? Am I missing something?

+5
source share
2 answers

Sounds like the right question. The idea of ​​trie is really nice and helps you find one log(n). The frequency of change depends on the information, so I won’t indicate the exact time, but I would configure it dynamically. Suppose you change once a day, it would be nice how much the tree has changed. And you can give a border (e.g. 10%). If the border is exceeded, you can update the trie more often. It also depends on how important it is to upgrade, because in most cases it is not. The idea of ​​load balancing is also good.

+1
source

More articles:


All Articles