Topic-Based News Subscription Service: Design and Implementation

Context

Design and implement an in-memory service responsible for managing news subscribers and delivering relevant news items on demand. Timestamps are integers, consistently applied across all operations (e.g., milliseconds for sliding-window rate limiting, or seconds if consistent). The service must strictly enforce the following criteria for news delivery: relevance, freshness, deduplication, specific ordering, and per-subscriber sliding-window rate limits.

API to Implement (class NewsProvider)

AddSubscription(subscriberId, minInterest, maxNewsPerSecond, topics) -> bool

Creates or updates a subscriber's configuration. Returns true on success, false on invalid input or if any constraints are violated.

RemoveSubscription(subscriberId) -> bool

Removes an existing subscriber. Returns false if the subscriberId does not exist.

NewsReceived(newsId, timestamp, interest, topics) -> bool

Ingests a new news item, including its unique ID, timestamp, an interest score, and associated topics. Returns false if newsId already exists, otherwise true.

Publish(nowTimestamp, maxAge) -> dict[int, list[int]]

At the given nowTimestamp, this method iterates through all subscribers and returns a dictionary where keys are subscriberIds and values are lists of newsIds to be delivered to that subscriber. Delivery must adhere to the following rules:

Publish Rules

1. Eligibility: A news item is delivered only if its news.interest score is greater than or equal to the subscriber.minInterest threshold.
2. Topic Filter: A news item is delivered only if its news.topics set has at least one topic in common with the subscriber.topics set.
3. Freshness: A news item is delivered only if its news.timestamp falls within the window [nowTimestamp - maxAge, nowTimestamp].
4. Rate Limiting: Each subscriber can receive at most maxNewsPerSecond items within any rolling 1-second window.
5. De-duplication: A specific newsId must not be delivered to the same subscriber more than once.
6. Ordering: News items for a subscriber must be ordered by:
   • Higher interest first.
   • If interest scores are tied, older timestamp first (ascending).
   • If timestamps are also tied, smaller newsId first (ascending).

Deliverables

The solution should include:

• Specification of data structures for: managing subscriptions, storing news items, tracking delivered news per subscriber, and maintaining per-subscriber sliding-window counters for rate limiting.
• Description of algorithms for: efficient filtering, sliding-window rate limiting, de-duplication, and multi-key sorting under high throughput.
• Analysis of time and space complexity for each API operation and the Publish method.
• Discussion of concurrency, idempotency, and persistence considerations.
• An explanation of how the system would scale to millions of users and a large, continuous news stream, covering aspects like partitioning, sharding, backpressure mechanisms, batching strategies, and fault tolerance.