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. ```hint Do the work at write time A query should never have to open a post it will not return. Ask what you could precompute when a post is published so that a query starts from the keyword rather than from the posts. ``` #### 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. ```hint Let the short list drive Picture each keyword's matches as an ordered list of post IDs. Think about how to combine two such lists in one pass, and which list should drive the work when one is short and the other covers a large share of all posts. ``` #### 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. ```hint Count once, rank cheaply Decide where the count of a keyword in a post is recorded so that a query never re-reads post text. Then work out how many candidates each machine must send back for the system to return the top 10. ``` #### 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 ### What a Strong Answer Covers - Clarifies keyword semantics, matching rules, freshness and scale before designing - A complete write path and read path, with illustrative estimates of index size and query fan-out - Correct required and excluded semantics, evaluated before results are paginated - Frequency ranking with efficient top-result selection and stable pagination - Failure handling (a lagging indexer, a slow or dead machine) and the metrics that would reveal each problem ### Follow-up Questions - Users want phrase search ("apple pie" as consecutive words). What must the index store in addition? - A keyword that appears in a large share of all posts is required or excluded. How do you keep the query fast? - A post is deleted but the index has not caught up yet. How do you make sure it never appears in results? - Some posts are visible only to the author's connections. Where in your design is that enforced?