299. Design Twitter
Build a miniature in-memory Twitter as a class Twitter with four operations:
post_tweet(user_id, tweet_id)— the user publishes a tweet with the given id. Every call happens at a strictly later moment than the one before it, so no two tweets are ever tied on recency.get_news_feed(user_id)— return a list of at most the 10 most recent tweet ids visible to this user, newest first. A user sees their own tweets plus the tweets of everyone they currently follow.follow(follower_id, followee_id)— the follower starts following the followee.unfollow(follower_id, followee_id)— the follower stops following the followee (a no-op if they never followed them).
Users spring into existence the first time an operation mentions them. A user always sees their own tweets — even after unfollow(u, u) — and following yourself must not duplicate your posts in the feed.
Example 1:
Input: post_tweet(1,5) · get_news_feed(1) · follow(1,2) · post_tweet(2,6) · get_news_feed(1) · unfollow(1,2) · get_news_feed(1)
Output: feeds: [5], [6, 5], [5]
Explanation: User 1 posts tweet 5 and sees [5]. After following user 2, who then posts tweet 6, user 1's feed is [6, 5] — tweet 6 is newer. Unfollowing user 2 removes tweet 6, leaving [5].
Example 2:
Input: post_tweet(2,101) … post_tweet(2,112) · get_news_feed(2)
Output: [112, 111, 110, 109, 108, 107, 106, 105, 104, 103]
Explanation: User 2 posted twelve tweets, but a feed is capped at the 10 most recent — the oldest two (101 and 102) fall off.
Constraints:
- 1 ≤ q ≤ 3 * 10⁴ operations
- 1 ≤ userId, tweetId ≤ 10⁵
- All tweet ids in a feed are distinct; each post happens at a strictly later time than the previous one.
- A feed returns at most 10 tweet ids, newest first.
Hints:
Recency is global, not per user: stamp every tweet with a counter that increments on each post. A feed is then "the 10 largest stamps among the tweets of me + my followees".
Store per-user tweet lists (already sorted by time, since you append). Merging the newest items of several sorted lists is a classic job for a max-heap: push each source's latest tweet, pop the newest, then push that source's previous tweet.
Follows change constantly — keep them in a hash map from user to a set of followees so follow/unfollow are O(1), and remember to include the user themselves when building the feed (dedupe self-follows with the set union).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: post_tweet(1,5) · feed(1) · follow(1,2) · post_tweet(2,6) · feed(1) · unfollow(1,2) · feed(1)
Expected output: feeds: [5], [6, 5], [5]