## Scenario Design a search service for a collection of status posts. Each status has a stable ID, text, a creation time, and an active-or-deleted state. A user submits a Boolean expression over normalized search terms, and the service returns matching active statuses. The required operators are `AND` and `OR`. Your design should cover query parsing, indexing, evaluation, updates, pagination, and scaling. No traffic volume, ranking formula, or freshness target is given; identify the decisions that depend on those missing facts and then present a reasonable baseline whose assumptions are explicit. For examples, assume `AND` has higher precedence than `OR` and parentheses may override precedence: ```text robot AND delivery robot OR autonomy AND safety (robot OR autonomy) AND safety ``` Do not add phrase search, negation, fuzzy matching, or personalized ranking to the core design unless you label it as a possible extension. ### Constraints & Assumptions - Term matching uses the same documented normalization during ingestion and querying. - Deleted statuses must stop appearing in new results. - A successful status create, edit, or delete must also durably record the corresponding indexing intent. A crash between acknowledging the source write and publishing an index event must not be able to lose that change permanently. - The indexing path must tolerate duplicate delivery, delayed replay, and events arriving out of version order. - A result page must not repeat an item or skip an item merely because several query branches matched it. - The Boolean expression has bounded length and nesting depth so parsing and evaluation cannot consume unbounded resources. - The baseline can order matches by `(creation_time descending, status_id descending)`; a different ranking policy can replace it after clarification. - It is acceptable to state a measurable indexing-lag target as an assumption, but do not claim that the source supplied one. ### Clarifying Questions to Ask - What exactly is a status post, and which fields are searchable: body text only or additional fields? - How should tokenization, case, punctuation, stemming, and languages be handled? - Are parentheses required, and is the precedence rule `AND` before `OR`? - Is search ranked by recency, relevance, or another signal, and must pagination be stable across index updates? - What are the write rate, searchable corpus size, peak query rate, and common term frequencies? - How soon after creation, editing, or deletion must a status become visible or disappear? - Can the source store atomically write an outbox row with the status change, or does it expose a durable commit log suitable for change-data capture? - Are access-control filters required, and if so, must they be enforced before a result ID leaves the search tier? - What query-size and result-window limits protect the service from very broad expressions? ```hint Give the expression a real representation Tokenize and parse the query into an abstract syntax tree. Evaluation can then map a term to a posting list, `AND` to intersection, and `OR` to deduplicating union. ``` ```hint Start intersections with the selective term For an `AND` node, evaluating the smallest estimated posting list first reduces the number of candidate IDs carried into later intersections. ``` ### What a Strong Answer Covers - A precise grammar or parser strategy with syntax validation, precedence, parentheses, and limits on expression complexity. - One normalization pipeline shared by status ingestion and query terms so the same token maps to the same index key. - An inverted index from term to posting data, plus a status store used to retrieve current records and verify active state. - Correct Boolean execution: posting-list intersection for `AND`, deduplicating union for `OR`, and a plan for ordering and stable cursor pagination. - Creation, edit, and deletion flows that atomically preserve index-update intent through an outbox or equivalent durable change log, plus idempotent replay and out-of-order version handling. - An explicit freshness model and protection against stale deleted results. - Selectivity estimates, result caps, timeouts, and observability for broad or expensive expressions. - A scaling path that explains what is sharded, how partial results are merged, where replicas and caches help, and which consistency trade-offs follow. - A clear boundary between the required AND/OR service and optional features that were not stated. ### Follow-up Questions 1. How would you evaluate `A AND (B OR C)` without materializing every match for `B OR C` first? 2. What changes if deletion must be reflected immediately but new statuses may appear after a short delay? 3. How would a very common term affect memory, latency, caching, and query planning? 4. How would you preserve pagination correctness while new matching statuses are continuously added? 5. Where would access-control filtering live if users are not allowed to discover every indexed status?