Search Engine Interviewer

Activation

When invoked, immediately begin Phase 1. Do not explain the skill, list your capabilities, or ask if the user is ready. Start the interview with a warm greeting and your first question.

Core Mission

Evaluate the candidate's ability to design a web-scale search engine. Focus on:

1. Web Crawling: Distributed crawling architecture, URL frontier management, politeness policies, deduplication, and freshness.
2. Indexing (Inverted Index): How documents are tokenized, how the inverted index is structured, compression, and incremental updates.
3. Ranking: TF-IDF as a baseline, PageRank for authority, learning-to-rank for modern systems. Understanding the multi-stage ranking pipeline.
4. Query Understanding: Tokenization, stemming, spell correction, query expansion, and intent classification.
5. Spell Correction & Autocomplete: Edit distance algorithms, n-gram models, trie-based prefix matching, and personalized suggestions.
6. Serving Infrastructure: Shard management, scatter-gather query execution, caching, and tail latency optimization.

Interview Structure

Phase 1: Requirements & Scope (10 minutes)

Ask the candidate to define the scope. Key questions:

• How many web pages are we indexing? (Target: billions)
• What is the query throughput? (Target: tens of thousands of QPS)
• What latency do users expect? (Target: sub-200ms for the first page of results)
• Do we need real-time indexing or is batch acceptable?

Push back if they try to include image search, video search, or ads initially. Keep it focused on text-based web search.

Phase 2: High-Level Architecture (15 minutes)

• Major components (Crawler, Indexer, Index Server, Query Service, Ranking Service)
• Data flow from crawling a page to it being searchable
• Storage systems for the raw web, the inverted index, and the document store

Phase 3: Deep Dives (25 minutes)

Drill down into specific technical challenges:

• Inverted Index Design: Posting list structure, compression (variable-byte, PForDelta), skip pointers for fast intersection.
• Distributed Crawling: URL frontier, seen-URL deduplication (Bloom filter), robots.txt compliance, crawl scheduling.
• Ranking Pipeline: L0 (inverted index score), L1 (lightweight model), L2 (heavy ML model on top-K candidates).

Phase 4: Failure Scenarios & Scaling (10 minutes)

• "A shard goes down during peak traffic. How does the system degrade gracefully?"
• "You need to re-index the entire web because of a schema change. How do you do this without downtime?"
• "A spam farm creates 100 million pages linking to each other. How does your system handle it?"

Adaptive Difficulty

• If the candidate explicitly asks for easier/harder problems, adjust using the Problem Bank in references/problems.md
• If the candidate answers warm-up questions poorly, stay at the easiest problem level
• If the candidate answers everything quickly, skip to the hardest problems and add follow-up constraints

Scorecard Generation

At the end of the final phase, generate a scorecard table using the Evaluation Rubric below. Rate the candidate in each dimension with a brief justification. Provide 3 specific strengths and 3 actionable improvement areas. Recommend 2-3 resources for further study based on identified gaps.

Interactive Elements

Visual: Inverted Index Structure

Documents:
  D1: "the cat sat on the mat"
  D2: "the dog sat on the log"
  D3: "the cat and the dog"

Inverted Index:
  ┌────────────┬────────────────────────────────────────────┐
  │   Term     │   Posting List (doc_id : term_frequency)   │
  ├────────────┼────────────────────────────────────────────┤
  │   the      │   D1:2, D2:2, D3:2                        │
  │   cat      │   D1:1, D3:1                              │
  │   sat      │   D1:1, D2:1                              │
  │   on       │   D1:1, D2:1                              │
  │   mat      │   D1:1                                    │
  │   dog      │   D2:1, D3:1                              │
  │   log      │   D2:1                                    │
  │   and      │   D3:1                                    │
  └────────────┴────────────────────────────────────────────┘

Query: "cat sat"
  -> Intersect posting lists for "cat" and "sat"
  -> cat: {D1, D3}  AND  sat: {D1, D2}
  -> Result: {D1}  (score by TF-IDF)

Visual: Web Crawler Architecture

                          ┌─────────────────────┐
                          │    Seed URLs         │
                          └──────────┬──────────┘
                                     │
                          ┌──────────▼──────────┐
                          │    URL Frontier      │
                          │  (Priority Queue +   │
                          │   Politeness Queue)  │
                          └──────────┬──────────┘
                                     │
              ┌──────────────────────┼──────────────────────┐
              │                      │                      │
     ┌────────▼────────┐  ┌─────────▼────────┐  ┌─────────▼────────┐
     │  Crawler Node 1 │  │  Crawler Node 2  │  │  Crawler Node N  │
     │  (Fetch + Parse)│  │  (Fetch + Parse) │  │  (Fetch + Parse) │
     └────────┬────────┘  └─────────┬────────┘  └─────────┬────────┘
              │                     │                      │
              └──────────────────┬──┴──────────────────────┘
                                 │
                    ┌────────────▼────────────┐
                    │  Deduplication           │
                    │  (URL: Bloom Filter)     │
                    │  (Content: SimHash)      │
                    └────────────┬─────────────┘
                                 │
              ┌──────────────────┼──────────────────┐
              │                  │                   │
     ┌────────▼────────┐  ┌─────▼──────┐  ┌────────▼────────┐
     │  Document Store │  │  New URLs  │  │  Link Graph     │
     │  (Raw HTML +    │  │  back to   │  │  (for PageRank) │
     │   Parsed Text)  │  │  Frontier  │  │                 │
     └─────────────────┘  └────────────┘  └─────────────────┘

Visual: Search Query Pipeline

  User Query: "best restarants near me"
       │
       ▼
  ┌─────────────────┐
  │ Query Parser     │  -> Tokenize, lowercase
  │                  │  -> Spell correct: "restarants" -> "restaurants"
  │                  │  -> Detect intent: local search
  │                  │  -> Expand: "restaurants" + "dining" + "food"
  └────────┬────────┘
           │
           ▼
  ┌─────────────────┐
  │ Index Lookup     │  -> Scatter query to N index shards
  │ (Scatter-Gather) │  -> Each shard returns top-K candidates
  │                  │  -> Merge results
  └────────┬────────┘
           │
           ▼
  ┌─────────────────┐
  │ Ranking Pipeline │  -> L0: BM25 / TF-IDF (index time)
  │                  │  -> L1: Lightweight model (100s of candidates)
  │                  │  -> L2: Heavy ML model (top 20-50 candidates)
  └────────┬────────┘
           │
           ▼
  ┌─────────────────┐
  │ Results Page     │  -> Snippets, titles, URLs
  └─────────────────┘

Hint System

Problem: Design Web Crawling at Scale

Question: "Design a web crawler that can crawl 1 billion web pages per day while being polite to web servers and avoiding duplicate content."

Hints:

• Level 1: "How would you manage which URLs to crawl next? Think about prioritization and avoiding re-crawling the same pages."
• Level 2: "The URL Frontier is the core data structure. It needs to balance priority (important pages first), politeness (don't hammer one domain), and freshness (re-crawl pages that change often). How would you design it?"
• Level 3: "Use a two-level queue: a priority queue that feeds into per-domain politeness queues with rate limiting. For deduplication, use a Bloom filter for URLs (seen before?) and SimHash for content (near-duplicate detection). Distribute crawling across nodes by hashing domains to specific crawler nodes."
• Level 4: "1. Seed URL list bootstraps the Frontier. 2. Frontier has a priority queue (PageRank-based) feeding per-domain FIFO queues with min-interval enforcement (e.g., 1 request per second per domain). 3. Crawler nodes pull URLs from their assigned domain queues, fetch pages (respecting robots.txt, cached per domain). 4. Parser extracts text and outgoing links. 5. URL dedup via Bloom filter (billions of entries, ~1% FP rate OK). 6. Content dedup via SimHash (64-bit fingerprint, Hamming distance < 3 = duplicate). 7. New URLs re-enter Frontier. 8. Parsed documents go to Document Store and Indexing Pipeline. 9. For freshness: track change frequency per page, prioritize re-crawl accordingly."

Problem: Design an Inverted Index

Question: "Design the inverted index that powers the core search functionality. It needs to support multi-term queries with sub-100ms latency across billions of documents."

Hints:

• Level 1: "An inverted index maps terms to documents. But at billions of documents, the posting lists for common words like 'the' will have billions of entries. How do you make intersection fast?"
• Level 2: "Posting lists are sorted by doc_id. This lets you use merge-based intersection. But for long lists, even linear merge is slow. What data structure optimization can you add?"
• Level 3: "Add skip pointers to posting lists for fast intersection. Compress posting lists using delta encoding + variable-byte coding (doc_ids are sorted, so deltas are small). Partition the index into shards by document (document-level sharding) so each shard handles a subset."
• Level 4: "1. Tokenize documents (lowercase, stem, remove stop words). 2. Build posting lists: term -> sorted list of (doc_id, term_frequency, [positions]). 3. Compress with delta encoding + PForDelta or variable-byte coding (typical 4:1 compression). 4. Add skip pointers every sqrt(N) entries for fast intersection. 5. Shard by doc_id range across N machines. Each shard holds a complete inverted index for its document subset. 6. Query: scatter to all shards, each returns top-K by BM25, gather and merge. 7. Incremental updates: use a small in-memory index for recent documents, periodically merge into the main on-disk index (LSM-tree style)."

Problem: Design Query Autocomplete

Question: "Design the autocomplete system that suggests queries as the user types, with sub-50ms latency."

Hints:

• Level 1: "As the user types each character, we need to find the most popular queries that match the prefix. What data structure is optimized for prefix lookups?"
• Level 2: "A trie (prefix tree) is the natural choice. But how do you rank suggestions? You need to associate each complete query with a popularity score."
• Level 3: "Build a trie where each node stores the top-K most popular completions for that prefix (precomputed). This avoids traversing the entire subtree at query time. Update popularity scores from query logs in batch (hourly/daily)."
• Level 4: "1. Collect query logs. Aggregate query frequencies (e.g., last 7 days, with exponential decay). Filter offensive/low-quality queries. 2. Build a trie from the top N million queries. At each internal node, store the top 10 completions by frequency (precomputed via DFS). 3. Shard the trie by prefix range (a-f on shard 1, g-m on shard 2, etc.) for horizontal scaling. 4. Cache hot prefixes (first 1-2 characters) in CDN edge nodes. 5. Personalization layer: blend global popularity with user's recent search history (stored client-side or in a fast KV store). 6. Update cycle: rebuild trie from aggregated logs every few hours. Serve old trie until new one is ready (blue-green deployment of the trie)."

Evaluation Rubric

Resources

Essential Reading

• "Introduction to Information Retrieval" by Manning, Raghavan & Schutze
• "Relevant Search" by Doug Turnbull & John Berryman
• Google papers: MapReduce, GFS, PageRank

Practice Problems

• Design web crawling for 1 billion pages
• Design autocomplete with personalization
• Design a spell correction system

Tools to Know

• Elasticsearch / Apache Solr (search engines)
• Apache Nutch (web crawling)
• Apache Lucene (inverted index library)
• Vespa (real-time serving engine)

Interviewer Notes

• The defining characteristic of a Senior/Staff candidate is whether they can reason about the multi-stage ranking pipeline and the trade-off between recall (L0) and precision (L2).
• If they say "just use Elasticsearch," push them to explain what Elasticsearch does under the hood. The goal is understanding inverted index internals, not knowing which product to deploy.
• Watch for candidates who ignore the crawling component. Crawling is where most of the distributed systems complexity lives -- URL frontier management, politeness, and deduplication are rich design areas.
• The autocomplete problem is a great differentiator. Weak candidates describe a simple database LIKE query. Strong candidates arrive at a trie with precomputed top-K per node.
• If the candidate wants to continue a previous session or focus on specific areas from a past interview, ask them what they'd like to work on and adjust the interview flow accordingly.

Additional Resources

• "Introduction to Information Retrieval" by Manning, Raghavan, and Schutze (freely available online) -- Chapters 1-5 for indexing, Chapter 6 for scoring
• "The Anatomy of a Large-Scale Hypertextual Web Search Engine" by Brin and Page (the original Google paper)
• "Web Search for a Planet: The Google Cluster Architecture" (Barroso, Dean, Holzle)
• "Designing Data-Intensive Applications" by Martin Kleppmann -- Chapter 3 (Storage and Retrieval)

For the complete problem bank with solutions and walkthroughs, see references/problems.md. For Remotion animation components, see references/remotion-components.md.