Skip to main content

355. Design Twitter

medium

Design a simplified Twitter with postTweet, getNewsFeed (10 most recent across followees), follow, and unfollow. A k-way-merge heap problem disguised as a system design warm-up.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user's news feed. Implement the Twitter class: Twitter() initializes the object; void postTweet(int userId, int tweetId) composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId. List<Integer> getNewsFeed(int userId) retrieves the 10 most recent tweet IDs in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user themselves. Tweets must be ordered from most recent to least recent. void follow(int followerId, int followeeId) the user with ID followerId started following the user with ID followeeId. void unfollow(int followerId, int followeeId) the user with ID followerId started unfollowing the user with ID followeeId.

Constraints

  • 1 <= userId, followerId, followeeId <= 500
  • 0 <= tweetId <= 10^4
  • All the tweets have unique IDs.
  • At most 3 * 10^4 calls will be made to postTweet, getNewsFeed, follow, and unfollow.

Examples

Example 1

Input
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
Output
[null, null, [5], null, null, [6, 5], null, [5]]

Explanation: Twitter twitter = new Twitter(); twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5). twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5]. return [5]. twitter.follow(1, 2); // User 1 follows user 2. twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6). twitter.getNewsFeed(1); // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5. twitter.unfollow(1, 2); // User 1 unfollows user 2. twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Store each user's tweets as a list of (timestamp, tweetId) appended in order — a per-user newest-first linked list is even handier.

Hint 2

getNewsFeed across N followees is a k-way merge problem: each followee's tweet list is already in time order.

Hint 3

Push the most recent tweet of each followee (plus the user themselves) into a max-heap keyed on timestamp. Pop the top, push the next tweet from that user's list, repeat 10 times.

Solution approach

Reveal approach

Maintain a global monotonic timestamp. Store each user's tweets as a list of (timestamp, tweetId) in chronological order; store each user's followees in a hash set. postTweet: append (++clock, tweetId) to the user's list. follow/unfollow: hash-set add/remove (a user should always implicitly 'follow' themselves for the feed). getNewsFeed: for each followee (including the user), push (timestamp, tweetId, listIndex, userId) of their newest tweet into a max-heap. Pop the top, append its tweetId to the result, then push that user's next-newest tweet (if any) back into the heap. Stop after 10 pops or when the heap is empty. O(F log F + 10 log F) per feed call where F is the followee count. Variants: cap each user's stored tweets at the most recent 10 (you'll never serve older ones in their own feed); push the cap higher if other users follow them.

Complexity

Time
O(F log F + 10 log F) per getNewsFeed
Space
O(U + T) total

Related patterns

  • heap
  • k-way-merge
  • design
  • hash-map
  • linked-list

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Design Twitter and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →