Design Twitter

Mediumheaphash-tabledesign
Category: Heap / Priority Queue
Companies that ask this question:
AmazonTwitterFacebookGoogle
LeetCode →NeetCode →

Approach

Design Twitter

Problem Statement

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

Implement the Twitter class:

  • Twitter() Initializes your twitter object
  • void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by user userId
  • List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's news feed. Each item must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent
  • void follow(int followerId, int followeeId) User followerId follows user followeeId
  • void unfollow(int followerId, int followeeId) User followerId unfollows user followeeId

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 tweet 5
twitter.getNewsFeed(1);        // Return [5] (user 1's tweets)
twitter.follow(1, 2);          // User 1 follows user 2
twitter.postTweet(2, 6);       // User 2 posts tweet 6
twitter.getNewsFeed(1);        // Return [6, 5] (2's tweet + 1's tweet)
twitter.unfollow(1, 2);        // User 1 unfollows user 2
twitter.getNewsFeed(1);        // Return [5] (only user 1's tweets)

Intuition

Data Structures Needed:

  1. Tweets Storage: Map userId → list of (timestamp, tweetId)
  2. Follow Graph: Map userId → set of followee IDs
  3. Timestamp: Global counter for tweet ordering

GetNewsFeed Challenge: Merge k sorted lists (each user's tweets)!

  • Use min-heap to efficiently find 10 most recent across all followed users

Pattern Recognition

This is a Multi-List Merge with Heap problem:

  • Each user has chronological tweets (sorted by time)
  • Merge multiple sorted lists
  • K-way merge using heap

Approach

Hash Maps + Heap

Data Structures:

tweets = {}  # userId → [(time, tweetId), ...]
following = {}  # userId → {followeeId, ...}
timestamp = 0  # Global counter

postTweet:

  • Increment timestamp
  • Add (timestamp, tweetId) to user's tweet list

follow/unfollow:

  • Update following set

getNewsFeed:

  1. Collect all followees (+ self)
  2. For each followee, get their recent tweets
  3. Use max-heap to merge and get top 10
  4. Return in chronological order

Optimization: Use heap to avoid sorting all tweets

Edge Cases

  • User not following anyone (only see own tweets)
  • Following self (implicit)
  • Unfollow non-followed user
  • Get feed for user with no tweets
  • Multiple tweets at same time
  • Less than 10 tweets available

Complexity Analysis

  • postTweet: O(1)

    • Append to list

  • follow/unfollow: O(1)

    • Set operations

  • getNewsFeed: O(k * 10 log k) where k = number of followees

    • For each followee, check their tweets: O(k)
    • Heap operations for top 10: O(k log k)
    • Simplified: O(k log k)

  • Space: O(users + tweets + follows)

    • Store all data

Solution

java
1import java.util.*;
2
3class Twitter {
4    private Map<Integer, List<int[]>> tweets;  // userId -> [(timestamp, tweetId)]
5    private Map<Integer, Set<Integer>> following;  // userId -> {followeeId}
6    private int timestamp;
7
8    public Twitter() {
9        tweets = new HashMap<>();
10        following = new HashMap<>();
11        timestamp = 0;
12    }
13
14    public void postTweet(int userId, int tweetId) {
15        tweets.putIfAbsent(userId, new ArrayList<>());
16        tweets.get(userId).add(new int[]{++timestamp, tweetId});
17    }
18
19    public List<Integer> getNewsFeed(int userId) {
20        // Max-heap to get 10 most recent (compare by timestamp descending)
21        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
22            (a, b) -> b[0] - a[0]  // Compare timestamps (descending)
23        );
24
25        // Add user's own tweets
26        if (tweets.containsKey(userId)) {
27            List<int[]> userTweets = tweets.get(userId);
28            if (!userTweets.isEmpty()) {
29                int[] tweet = userTweets.get(userTweets.size() - 1);
30                maxHeap.offer(new int[]{tweet[0], tweet[1], userId, userTweets.size() - 1});
31            }
32        }
33
34        // Add followees' tweets
35        if (following.containsKey(userId)) {
36            for (int followee : following.get(userId)) {
37                if (tweets.containsKey(followee)) {
38                    List<int[]> followeeTweets = tweets.get(followee);
39                    if (!followeeTweets.isEmpty()) {
40                        int[] tweet = followeeTweets.get(followeeTweets.size() - 1);
41                        maxHeap.offer(new int[]{tweet[0], tweet[1], followee, followeeTweets.size() - 1});
42                    }
43                }
44            }
45        }
46
47        // Extract top 10 tweets
48        List<Integer> result = new ArrayList<>();
49        while (!maxHeap.isEmpty() && result.size() < 10) {
50            int[] curr = maxHeap.poll();
51            result.add(curr[1]);  // Add tweetId
52
53            // Add next tweet from same user if exists
54            int userIdx = curr[2];
55            int tweetIdx = curr[3];
56            if (tweetIdx > 0) {
57                int[] nextTweet = tweets.get(userIdx).get(tweetIdx - 1);
58                maxHeap.offer(new int[]{nextTweet[0], nextTweet[1], userIdx, tweetIdx - 1});
59            }
60        }
61
62        return result;
63    }
64
65    public void follow(int followerId, int followeeId) {
66        if (followerId != followeeId) {
67            following.putIfAbsent(followerId, new HashSet<>());
68            following.get(followerId).add(followeeId);
69        }
70    }
71
72    public void unfollow(int followerId, int followeeId) {
73        if (following.containsKey(followerId)) {
74            following.get(followerId).remove(followeeId);
75        }
76    }
77}
78
Loading visualizer...