Search & Indexing

Finding pages and answering queries at web scale: crawling the graph politely, building the index offline, and serving prefix and keyword lookups in milliseconds.

Explainers

• Design Search Autocomplete — The suggestions that drop down as you type — built from zero. A trie (a tree keyed by letters) with the top few completions pre-computed and cached at every node, so a keystroke is answered by reading a list, not by searching; why a live database query per keystroke dies at ~20× the search rate; the offline pipeline that turns query logs into a fresh trie snapshot; the sub-100 ms serving path; sharding by prefix and the fix for the uneven letters; and the failure sweep whose quietest box is a trending query that stays invisible for a week.
• Design a Web Crawler — The bulk downloader behind a search engine — built from zero. Why naive breadth-first crawling is rude, and how the URL frontier makes it polite: front queues that prioritise (by PageRank, traffic, freshness) feeding back queues that enforce one host per queue, one worker, a delay between fetches. Plus robots.txt and its cache, the two dedup structures (a bloom filter of seen URLs, a hash of seen content), DNS caching and the blocking-resolver trap, spider-trap defenses, and a freshness strategy — with a live frontier you can flood from one host to watch politeness throttle it while the others proceed.