Autocomplete Search

Autocomplete or word completion is a feature in which an application predicts the rest of a word a user is typing. In graphical user interfaces, users can typically press the tab key to accept a suggestion or the down arrow key to accept one of several. Autocomplete is involved in many search features on various platforms like Facebook, Instagram, Google search, etc. If you are asked to design any one of these platforms, the interviewer might discuss autocomplete feature alongside other features of the platform asked to design.

If you are asked to design facebook, some time of the interview can be spent on designing a search box for Facebook which may include designing autocomplete features, especially for a Facebook use case which involves keeping user’s friends, mutual connections in mind while giving suggestions in the typeahead.

Step 1: Use Case Discussion

• Interviewee: What should be the scale of search queries for our service?
• Interviewer: Let’s expect 4 billion queries per day .


• Interviewee: How many suggestions are to be provided for each query?
• Interviewer: Let’s expect 7 autocomplete suggestions.


• Interviewee: Is it supposed to be real-time? I.e. Let's say if currently there is an India vs Pakistan match going on, then should our autocomplete include this as a suggestion in the typeahead if searching “India vs Australia” is a trending query?
• Interviewer: Yes, we would like to have it as a real-time service.


• Interviewee: On what basis should we rank our suggestions?
• Interviewer: Lets rank based on the number of times the given query has been searched by our users. i.e frequency.

From this initial discussion we get our requirements as follows:

• Our system can expect 4 billion queries per day.
• We need 7 autocomplete suggestions for each character we enter in the search box
• It must be a real-time service. If a search query is trending, we must add it to our database, so that we can include it in our autocomplete suggestions.