News · New this week
Search autocomplete: the Flipkart system design answer
Flipkart's suggestions don't come from searching on every keystroke. A 150 ms wait, a cache and a sorted prefix index do the work.
If an interviewer asks how Flipkart suggests searches before you finish typing, the tempting answer is that every letter goes to the server. It doesn't. The answer has three parts, and each one is there to avoid a fresh search.
The phone waits first
Most people assume every letter hits Flipkart. It doesn't. Your phone waits 150 milliseconds and only then asks for suggestions.
That wait is the first step in the flow, before anything reaches the cache or the index. Say the number in the interview. "A short pause" is vague, and 150 ms is something the interviewer can reason about.
The cache answers popular starts
When the phone does ask, the request meets a cache first. A cache is a ready copy kept close, so no fresh search is needed. Think of a chaiwala who remembers your usual and has it ready before you finish ordering.
The cache holds ready copies of the top starts, meaning the beginnings of searches that many people type. When your typed start is one of those, the cache can answer from the copy it already has.
The prefix index handles a miss
If the cache doesn't have the start you typed, the request goes to a prefix index. This is a list sorted by first letters, like dictionary tabs. Each typed start has its own tab, so the system goes to the matching tab instead of searching a pile of unsorted queries.
Each tab keeps five matches. They're ranked by search count, with the most searched first. So when you type a few letters, you get the five queries that have been searched most often for that beginning.
That's the whole design in one line. Autocomplete is a cache over a sorted list, ranked by popularity.
How to use this in an interview
Walk the request in order. The phone waits 150 ms, the cache answers if it can, and the prefix index returns the top 5 by search count if it can't. Name the reason for each step. The cache is a ready copy, so no fresh search is needed. The prefix index is sorted by first letters, so each typed start has its own tab.
The reel ends on a question you should have an answer to. Would you rank suggestions by popularity or personalise them? The design above ranks by search count, so start there and say why you'd keep it or change it.
Next time you sketch a search box, draw the three boxes in order and say what each one does. If you've ever called the server on every keystroke, start by adding the 150 ms wait.
