Coding Interview PatternsDesign Twitter
MediumCustom Data Structures

Design Twitter

Explanation & Solution

Practice Problem

Description

Design a simplified version of Twitter where users can post tweets, follow/unfollow others, and see the most recent tweets in their news feed.

Implement a function that processes an array of operations and an array of arguments:

  • "Twitter" — Initializes the Twitter object.
  • "postTweet" — User userId posts a tweet with tweetId.
  • "getNewsFeed" — Returns a list of the 10 most recent tweet IDs in the user's news feed. The feed includes tweets from the user and from users they follow, ordered from most recent to least recent.
  • "follow" — User followerId starts following user followeeId.
  • "unfollow" — User followerId stops following user followeeId.
Input:operations = ["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"], args = [[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]
0
Twitter
1
postTweet
2
getNewsFeed
3
follow
4
postTweet
5
getNewsFeed
6
unfollow
7
getNewsFeed

Output: [null,null,[5],null,null,[6,5],null,[5]]

Explanation: User 1 posts tweet 5. Feed=[5]. User 1 follows user 2. User 2 posts tweet 6. Feed=[6,5]. User 1 unfollows user 2. Feed=[5].

Constraints

  • 1 <= userId, followerId, followeeId <= 500
  • 0 <= tweetId <= 10^4
  • All tweet IDs are unique
  • At most 3 * 10^4 calls to all operations
  • A user can follow themselves (their own tweets always appear in their feed)

Approach

Custom Data Structures pattern

1. Two Hash Maps

  • tweets: maps userId → [[timestamp, tweetId], ...]
  • following: maps userId → Set<followeeId>
  • A global timestamp counter orders all tweets globally

2. Implement PostTweet

  • Append [timestamp, tweetId] to the user's tweet list
  • Increment the global timestamp after each post

3. Implement GetNewsFeed

  • Collect tweets from the user and all their followees
  • Sort all collected tweets by timestamp in descending order
  • Return the tweetIds of the top 10

4. Implement Follow and Unfollow

  • Follow: add followeeId to the follower's set
  • Unfollow: remove followeeId from the follower's set (if present)

5. Self-Tweets Always Appear

  • Always include the user's own userId in the set of users whose tweets are fetched
  • This ensures their own posts always appear in their feed

Key Insight

  • A global timestamp ensures total ordering across all users' tweets
  • For large-scale systems, a min-heap merge of k sorted lists would be more efficient
  • This simpler approach is O(n log n) for getNewsFeed where n = total tweets from user + followees
Time
O(n log n) for getNewsFeed, O(1) for others
Space
O(total tweets + follow relationships)

Solution Code

Previous
Design Underground System
Next
Maximum Frequency Stack