Design a search service for short plain-text status posts. It must ingest new statuses and answer Boolean queries containing terms joined by `AND` and `OR`. Relevance ranking is out of scope; the result is the matching status IDs in a deterministic order. ### Constraints & Assumptions - Define tokenization and normalization consistently for both indexing and querying. - New statuses should become searchable through an asynchronous indexing pipeline with an explicit freshness contract. - Posting the same event again must not duplicate index entries. - The index may eventually exceed one machine, so the design must compare term-based and document-based partitioning. ### Clarifying Questions to Ask - Are parentheses, precedence, phrase search, negation, stemming, or stop words required? - Are statuses editable or deletable, and how quickly must those changes affect search? - Is ordering by status ID or creation time sufficient when ranking is excluded? - What are the write rate, query rate, retention period, and acceptable indexing delay? ```hint Treat a posting list as a sorted set An inverted index maps each normalized term to ordered status IDs, making `AND` an intersection and `OR` a union. ``` ### What a Strong Answer Covers - The write, tokenization, normalization, indexing, and query-parsing paths. - Efficient sorted posting-list intersection and union, including deduplication and deterministic output. - Near-real-time immutable segments or buffered updates, deletion handling, idempotency, and index recovery. - Term versus document sharding, scatter-gather costs, hot terms, caching, replication, and observability. ### Follow-up Questions - How would skip pointers or block metadata accelerate an `AND` query over very different posting-list sizes? - What happens to a multi-term query when postings are sharded by term? - How would you rebuild the index without making recently published statuses disappear?