Design Keyword Search over Posts with Exclusions and Frequency Ranking

Design the search backend for posts on a social platform. A user types one or more keywords and gets back the posts that match, best matches first. Describe the end-to-end flow (how a new or edited post becomes searchable and how a query is answered), then go deep on the three areas the interviewer focused on: finding the posts that contain a keyword quickly, excluding keywords, and ranking results by keyword frequency.

Constraints and Clarifications

• Search is over the text of posts. A query is a set of keywords; some must appear and, from Part 2 on, some must not.
• Results are ordered by how often the query keywords appear in each post (Part 3).
• Not given: the number of posts, the posting and query rates, how quickly a new post must become searchable, and the latency target. Ask, or state your assumptions.

Clarifying Questions

• Is a keyword a single word, or can a query contain a phrase that must appear as consecutive words?
• How is text matched: is it case-insensitive, do other word forms match ("apples" for "apple"), and how are punctuation and hashtags treated?
• When a query has several keywords to include, must a post contain all of them or any of them?
• How soon after a post is published, edited or deleted must search reflect the change?
• Must results respect who is allowed to see each post?

Part 1 — Finding the posts that contain a keyword

Given a keyword, how does the system determine quickly which posts contain it, without reading every post? Explain how this structure is built and kept up to date as posts are created, edited and deleted, and how it is split across machines.

What This Part Should Cover

• Text normalization, applied identically to posts and to queries
• The lookup structure, what each entry stores, and roughly how large it is
• The write path for new, edited and deleted posts, and how fresh results are
• Partitioning across machines and how one query is answered across them

Part 2 — Excluding keywords

Support queries such as "posts that contain apple but not banana", and in general several required keywords combined with several excluded ones.

Clarifying Questions for this Part

• Is a query made only of excluded keywords allowed, such as every post except those mentioning banana?
• Does excluding banana also exclude posts that say "bananas"?

What This Part Should Cover

• How required and excluded keywords are evaluated, and in what order
• The cost when an excluded keyword is very common
• Where exclusion runs relative to pagination and partitioning, so pages are neither short nor wrong
• Edge cases: unknown keywords, a keyword both required and excluded, exclusion-only queries

Part 3 — Ranking by keyword frequency

When returning results, order the posts by how often the query keywords appear in them, and return the results a page at a time.

Clarifying Questions for this Part

• Should a long post that repeats a keyword many times outrank a short post that is mostly about it?
• With several keywords, how are their counts combined, and how are ties ordered?

What This Part Should Cover

• Where frequencies are stored and how a score is computed for multi-keyword queries
• Selecting the top results without sorting every match, and merging them across machines
• Stable pagination
• Weaknesses of raw counts (long posts, keyword stuffing, common words) and an improvement