Design a Simple Search Engine

The Problem

Your engineering team maintains a knowledge base of 50,000 internal documents. Engineers search for solutions dozens of times a day, but the current implementation runs a naive String.contains() scan across every document for every query. At 50,000 documents, each search takes 3-5 seconds, and boolean queries like "circuit breaker AND retry NOT timeout" are not supported at all.

An inverted index solves the core performance problem. Instead of scanning every document, you build a map from each term to the list of documents containing that term. A search for "retry" becomes a single map lookup returning document IDs in microseconds. Boolean queries become set operations: AND is intersection, OR is union, NOT is difference.

Design the core classes for an in-memory search engine that supports document indexing, inverted index construction, pluggable ranking strategies, boolean query evaluation, and paginated result retrieval.

Requirements

Clarifying Questions

Before jumping into class design, ask questions to turn the vague prompt into a concrete specification. Cover four areas: core behavior, ranking, query language, and boundaries.

You: "What does a document look like? Does it have a title, body, and metadata, or just raw text?"

Interviewer: "Each document has an ID, a title, and a body. No additional metadata for now."

Simple model. A Document record with three fields keeps things clean.

You: "How should we rank search results? By relevance, recency, or just presence?"

Interviewer: "Relevance by default using TF-IDF. But we want the flexibility to swap in other algorithms like BM25 or simple frequency count."

That signals Strategy pattern for ranking. The default implementation computes TF-IDF scores, but the interface stays open for alternatives.

You: "Do we need to support boolean queries like AND, OR, NOT?"

Interviewer: "Yes. Users should be able to combine terms with AND, OR, and NOT. For example, 'cache AND invalidation NOT stale'."

Boolean operators mean we need a query tree. Composite pattern fits: each query node is either a leaf (single term) or a composite (AND/OR/NOT combining child nodes).

You: "Should tokenization be configurable? Some teams might want stop-word removal or stemming."

Interviewer: "Yes. Default tokenization is lowercase plus whitespace splitting. But make it pluggable so we can add stop-word removal or stemming later."

Another Strategy. Tokenization is a pipeline step that varies independently from ranking.

You: "How should we handle pagination? Do callers specify page size and page number?"

Interviewer: "Yes. Return a page of results with the total count so callers can build pagination controls."

A SearchResult object wrapping a page of ranked results with metadata.

You: "Should the system handle concurrent reads and writes? Can indexing happen while searches are running?"

Interviewer: "Yes. Documents get indexed continuously while searches execute. Thread safety is required."

ReadWriteLock on the index. Reads (searches) can run concurrently, but writes (indexing) acquire an exclusive lock.

You: "Do we need phrase queries like 'circuit breaker' as an exact phrase?"

Interviewer: "Not in the core scope. But design the posting list so positional data is available for future phrase support."

Good boundary. We store term positions in each posting so phrase queries become a natural extension.

You: "Is there a limit on document size or total document count?"

Interviewer: "No hard limit. Assume in-memory is sufficient. Optimize for fast lookup, not storage efficiency."

Final Requirements

Functional Requirements:

1. Index documents by tokenizing their title and body into an inverted index.
2. Search for documents matching a single term, returning ranked results.
3. Support boolean queries (AND, OR, NOT) combining multiple terms.
4. Rank results using a pluggable strategy (TF-IDF by default).
5. Tokenize text using a pluggable strategy (lowercase + whitespace split by default).
6. Return paginated results with total count.
7. Store term positions in postings for future phrase query support.

Non-Functional Requirements:

1. Thread-safe for concurrent indexing and searching.
2. Sub-millisecond single-term lookups via inverted index.
3. Extensible for new ranking algorithms and tokenizers without modifying existing code.

Out of Scope:

• Persistence or database integration
• Phrase queries (positional data stored but not queried)
• Fuzzy matching or typo correction
• UI rendering or API endpoints
• Distributed indexing or sharding

30-Second Design Summary

SearchEngine orchestrates a pluggable Tokenizer, an InvertedIndex, a boolean Query tree, and a RankingStrategy. The index maps normalized terms to postings containing document IDs, frequencies, and positions. Indexing updates postings; searching evaluates the query into candidate IDs, scores those candidates, and returns a paginated SearchResult. The design keeps indexing, query semantics, and ranking independent so each can evolve without a monolithic engine.

5-Minute Walkthrough

1. Set the scope. The core covers single-term and boolean search, tokenization, TF-IDF-style ranking, pagination, and positional postings. Persistence, phrase querying, fuzzy matching, and distributed indexing are extensions.
2. Build the index. Tokenize title/body text, normalize terms, count occurrences and positions per document, and update the posting lists. Store enough document metadata to reconstruct results.
3. Evaluate a query. A term query reads one posting list; AND, OR, and NOT combine child result sets through the Composite query contract. Keep set operations separate from scoring.
4. Rank and page. Score matching documents using the injected ranker, sort deterministically with a tie-breaker, compute total count, and slice the requested page. Pagination should not change membership or privacy semantics.
5. Extend without rewiring. New tokenizers, rankers, query nodes, filters, or persistent index implementations can sit behind current interfaces. Positional data is retained so phrase support does not require redesigning the posting model.

Example Inputs and Outputs

Scenario 1: Single-term search with ranking

• Input: Index three documents. Doc 1: "retry mechanisms in distributed systems". Doc 2: "retry and circuit breaker patterns". Doc 3: "caching strategies for performance". Search for "retry".
• Expected: search("retry") returns Doc 1 and Doc 2, ranked by TF-IDF score. Doc 3 is excluded because it does not contain "retry".
• Why: Validates inverted index lookup and ranking.

Scenario 2: Boolean AND query

• Input: Same three documents. Search for "retry AND patterns".
• Expected: Only Doc 2 is returned (contains both "retry" and "patterns"). Doc 1 has "retry" but not "patterns". Doc 3 has neither.
• Why: Validates posting list intersection for AND queries.

Scenario 3: Boolean NOT query

• Input: Same three documents. Search for "retry NOT circuit".
• Expected: Only Doc 1 is returned. Doc 2 has "retry" but also contains "circuit", so NOT excludes it.
• Why: Validates posting list difference for NOT queries.

Try It Yourself

---

Step 1: Identify Core Entities

Start by asking: what are the main "things" in this problem? Look for nouns in the requirements. You will find documents, an index, tokens, queries, rankings, and results. Each one maps to a class with a single clear responsibility.

A common mistake is lumping the index, tokenizer, and ranker into one giant SearchEngine class. Good design means each class has one job. The engine orchestrates, the index stores postings, the tokenizer splits text, and the ranker scores results.

Notice that Posting is separate from InvertedIndex. A posting captures per-document term metadata (frequency, positions), while the index manages the mapping from terms to posting lists. Merging them would violate SRP because the index handles lookups while postings hold statistics.

Step 2: Define Relationships and Class Design

SearchEngine

The orchestrator. It coordinates indexing and searching but delegates all real work to collaborators.

Deriving state from requirements: