Design and implement a Live News Feed System.

News providers publish articles under topics such as sports, tech, finance and many other topics. Users can subscribe to topics they care about, receive near real-time notifications when new articles are published for those topics, and fetch a personalized feed.

Functional Requirements

• News providers publish content.
• Each article belongs to one or more topics.
• Users subscribe or unsubscribe from one or more topics.
• When a new article is published, subscribed users receive notifications.
  Each user may receive at max one notification for an article even when it is subscribed to multiple topics which the article contains.
• Users can fetch a personalized feed based on their current subscriptions.
• The system should be extensible for future features such as ranking, filtering, muting topics, and pagination.

Important Notes

• All data should be stored in memory.
• All IDs and names are case-sensitive.
• Unsubscribing removes only future notifications; past notifications already delivered remain available until fetched.
• Feed ordering should be deterministic.
• When multiple articles have the same publish timestamp, order them by lexicographically smaller articleId first.
• Personalized feed should contain only articles published after the user subscribed and whose atleast one topic is currently subscribed by the user at the time of fetching the feed.
• Notifications should contain only articles published after the user subscribed to that topic.
  If a user unsubcribes from a topic then past queued notifications for that topic are not affected and they will be delivered.

Constructor

LiveNewsFeed(List<String> existingUserIds, List<String> existingTopicIds)

• Each item in existingTopicids or existingUserIds is non-blank and globally unique.
• existingTopicIds.size()>0
• existingUserIds.size()>0

Method Signatures

boolean subscribeUnsubscribeTopic(String userId, String topicId, boolean subscribe, int currentTime)

• if subcribe = true then subscribes the given user to the given topic else unsubscribes.
• If system was already in desired state then nothing is updated and false is returned.
• Returns true if the subscribe/unsubscribe operation is performed successfully
• Returns false if the user or topic does not exist.
• currentTime is number of minutes elapsed since 1 Jan 1970, it is monotonically increasing (non-decreasing).

boolean publishArticle(String articleId, String title, List<String> topics, int currentTime)

• Publishes a new article under the given topic.
• Returns true if the article is published successfully.
• Returns false if articleId already exists, any element in topics does not exist, currentTime is negative or input is invalid.
• Publishing an article should enqueue notifications for all users currently subscribed to that topic.
• currentTime is number of minutes elapsed since 1 Jan 1970, it is monotonically increasing (non-decreasing).

List<String> getPersonalizedFeed(String userId)

• Returns the personalized feed for the given user.
• An article appears in the personalized feed if there exists at least one topic in that article such that the user was subscribed to that topic at publish time and is still subscribed to that topic at feed fetch time.
• Each article must be returned as a string because object outputs should be represented in string form.
• Use the format "articleId | title | currentTime".
• Order by currentTime descending; if tied, order by lexicographically smaller articleId first.
• If the user does not exist, return an empty list.

List<String> getNotifications(String userId)

• Returns and clears all pending notifications for the given user.
• Each notification must be returned as a string.
• Use the format "articleId | title | currentTime".
• Order by delivery sequence, which for this problem matches article publish order.
• If the user does not exist, return an empty list.

Constraints

• 1 ≤ userId.length(), topicId.length(), articleId.length() ≤ 10
• 0 ≤ title.length() ≤ 100
• All ids and title contains only characters from a-z, A-Z and 0-9, title also contains space character.
• currentTime is monotonically increasing (non decreasing) across all method calls.
• 0 ≤ currentTime ≤ 10^8
• At most 10^4 users
• At most 10^3 topics
• At most 10^5 articles
• Total number of method calls will not exceed 2 * 10^5
• All operations should be efficient enough for an in-memory interview setting.

Examples

Example 1

Example 2

Example 3