News subscriptions with rate limits

Build NewsProvider, which stores news items and subscriptions and decides, each time it publishes, which subscriber gets which item. All timestamps and ages are integers in milliseconds.

Operations

• add_subscription(sub_id: int, min_interest: int, max_per_second: int, topics: list[str]) -> bool: create a subscription, or update an existing one (new threshold, rate and topics; what it has already received, and when, is kept). Return False and change nothing if max_per_second < 1 or topics is empty.
• remove_subscription(sub_id: int) -> bool: False if it doesn't exist. Removing forgets its history, so re-adding the same id later starts fresh.
• news_received(news_id: int, timestamp: int, interest: int, topics: list[str]) -> bool: store an item. False if news_id was ever used before. News may arrive out of timestamp order.
• publish(timestamp: int, max_age: int) -> dict[int, list[int]]: decide the deliveries at timestamp (see below) and return {news_id: [sub_id, ...]} with each list sorted ascending, leaving out items nobody receives. Publish timestamps must be strictly increasing: a call whose timestamp isn't greater than the last successful publish returns {} and does nothing.

Who gets what at publish(T, max_age)

An item is a candidate for a subscriber when all of these hold:

1. T - max_age <= item.timestamp <= T (items from the future aren't out yet);
2. the item and the subscription share at least one topic;
3. item.interest >= min_interest;
4. the subscriber has never received this item.

Rate limit: a subscriber may receive at most max_per_second items in any one-second window. Concretely, let recent be how many items it received in earlier publishes at times p with T - p < 1000. At T it can receive at most max_per_second - recent more (none if that is <= 0).

When a subscriber has more candidates than allowance, it gets the best ones: highest interest first, then oldest timestamp, then highest news_id. A candidate that loses out can still be delivered at a later publish if it is still young enough.

Scale: tens of thousands of stored items and thousands of publishes, each with a short max_age. Scanning every item ever received on every publish is too slow; keep items ordered by timestamp and look only at the eligible window, and index subscriptions by topic.

p = NewsProvider()
p.add_subscription(1, 5, 2, ["tech"])
p.add_subscription(2, 0, 1, ["tech", "oil"])
p.news_received(100, 1000, 7, ["tech"])
p.news_received(101, 1500, 9, ["oil", "tech"])
p.news_received(102, 1600, 3, ["oil"])
p.publish(2000, 5000)   # {100: [1], 101: [1, 2]}   (sub 2 may take one: 101 has higher interest)
p.publish(2500, 5000)   # {}   (sub 2 already used its one-per-second at 2000)
p.publish(3000, 5000)   # {100: [2]}   (window has passed; 100 beats 102 on interest)
p.publish(3100, 1000)   # {}   (102 at 1600 is older than 3100 - 1000)