Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Design Twitter

MEDIUMProblemSolveExternal Links

Description

Design a simplified version of Twitter that supports the following operations:

  1. Post a tweet: A user can publish a new tweet identified by a unique tweet ID.
  2. Get news feed: Retrieve the 10 most recent tweet IDs that should appear in a given user's news feed. The feed includes tweets from the user themselves and from users they follow. Tweets must be ordered from most recent to least recent.
  3. Follow: One user starts following another user. After following, the follower will see the followee's tweets in their news feed.
  4. Unfollow: One user stops following another user. After unfollowing, the followee's tweets will no longer appear in the follower's news feed.

You need to implement the Twitter class with the following methods:

  • Twitter() — Initializes the Twitter object
  • postTweet(userId, tweetId) — User userId publishes tweet tweetId. Each call uses a unique tweetId.
  • getNewsFeed(userId) — Returns a list of at most 10 most recent tweet IDs for user userId's feed
  • follow(followerId, followeeId) — User followerId starts following user followeeId
  • unfollow(followerId, followeeId) — User followerId stops following 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:

  1. Twitter twitter = new Twitter() — Create the Twitter object.
  2. twitter.postTweet(1, 5) — User 1 posts tweet 5.
  3. twitter.getNewsFeed(1) — User 1's feed contains only their own tweet → [5].
  4. twitter.follow(1, 2) — User 1 follows User 2.
  5. twitter.postTweet(2, 6) — User 2 posts tweet 6.
  6. twitter.getNewsFeed(1) — User 1's feed now includes tweets from User 2 as well. Tweet 6 (more recent) comes before tweet 5 → [6, 5].
  7. twitter.unfollow(1, 2) — User 1 unfollows User 2.
  8. twitter.getNewsFeed(1) — User 2's tweets are no longer visible. Only User 1's own tweet remains → [5].

Example 2

Input:

["Twitter", "postTweet", "postTweet", "getNewsFeed", "follow", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 10], [2, 20], [1], [1, 2], [1], [1, 2], [1]]

Output: [null, null, null, [10], null, [20, 10], null, [10]]

Explanation:

  1. User 1 posts tweet 10, User 2 posts tweet 20.
  2. getNewsFeed(1) — User 1 only sees their own tweet → [10].
  3. User 1 follows User 2.
  4. getNewsFeed(1) — Now User 1 sees both tweets. Tweet 20 is more recent → [20, 10].
  5. User 1 unfollows User 2.
  6. getNewsFeed(1) — Back to only User 1's tweets → [10].

Constraints

  • 1 ≤ userId, followerId, followeeId ≤ 500
  • 0 ≤ tweetId ≤ 10^4
  • All tweet IDs are unique across all calls to postTweet
  • At most 3 × 10^4 total calls will be made to postTweet, getNewsFeed, follow, and unfollow
  • A user cannot follow themselves

Editorial

Brute Force

Intuition

Think of Twitter like a bulletin board system. Every user has their own board where they pin their tweets. When you ask for someone's news feed, you walk up to their board, collect their tweets, then walk to every person they follow and collect those tweets too. Finally, you lay all the collected tweets on a table, sort them by time (newest first), and pick the top 10.

The simplest data structures for this are:

  • A hash map from userId to a list of (timestamp, tweetId) pairs — storing each user's tweets in chronological order
  • A hash map from userId to a set of followeeIds — tracking who follows whom
  • A global counter that increments with each tweet — acting as a clock to determine recency

For postTweet, we just append to the user's tweet list. For follow/unfollow, we add/remove from the set. For getNewsFeed, we gather tweets from the user and all their followees, sort everything by timestamp, and return the 10 most recent.

Step-by-Step Explanation

Let's trace through Example 1 step by step:

Step 1: Initialize Twitter. Create empty maps: user_tweets = {}, following = {}, time = 0.

Step 2: postTweet(1, 5). Increment time to 1. Store tweet: user_tweets[1] = [(1, 5)]. User 1 now has one tweet.

Step 3: getNewsFeed(1). User 1 follows nobody. Relevant users = {1}. Collect tweets from User 1: [(1, 5)]. Sort by timestamp (descending): [(1, 5)]. Return top 10 tweet IDs: [5].

Step 4: follow(1, 2). Add 2 to User 1's following set: following[1] = {2}.

Step 5: postTweet(2, 6). Increment time to 2. Store: user_tweets[2] = [(2, 6)].

Step 6: getNewsFeed(1). Relevant users = {1, 2} (self + followees). Collect all tweets: [(1, 5), (2, 6)]. Sort descending by timestamp: [(2, 6), (1, 5)]. Return top 10: [6, 5].

Step 7: unfollow(1, 2). Remove 2 from User 1's following set: following[1] = {}.

Step 8: getNewsFeed(1). Relevant users = {1} only. Collect: [(1, 5)]. Return: [5].

Brute Force — Collecting and Sorting Tweets for News Feed — Watch how the brute force approach stores tweets with timestamps, then collects and sorts all relevant tweets to build the news feed.

Algorithm

Data Structures:

  • user_tweets: HashMap mapping userId → list of (timestamp, tweetId)
  • following: HashMap mapping userId → set of followeeIds
  • time: Global integer counter

postTweet(userId, tweetId):

  1. Increment time
  2. Append (time, tweetId) to user_tweets[userId]

getNewsFeed(userId):

  1. Build the set of relevant users: {userId} ∪ following[userId]
  2. Collect ALL tweets from all relevant users into one list
  3. Sort the list by timestamp in descending order
  4. Return the first 10 tweet IDs

follow(followerId, followeeId):

  1. Add followeeId to following[followerId]

unfollow(followerId, followeeId):

  1. Remove followeeId from following[followerId] if present

Code

class Twitter {
    unordered_map<int, vector<pair<int, int>>> userTweets;
    unordered_map<int, unordered_set<int>> following;
    int timeCounter;
    
public:
    Twitter() : timeCounter(0) {}
    
    void postTweet(int userId, int tweetId) {
        userTweets[userId].push_back({++timeCounter, tweetId});
    }
    
    vector<int> getNewsFeed(int userId) {
        vector<pair<int, int>> allTweets;
        
        // Collect tweets from self
        for (auto& t : userTweets[userId]) {
            allTweets.push_back(t);
        }
        // Collect tweets from followees
        for (int followee : following[userId]) {
            for (auto& t : userTweets[followee]) {
                allTweets.push_back(t);
            }
        }
        
        // Sort by timestamp descending
        sort(allTweets.begin(), allTweets.end(), greater<>());
        
        vector<int> feed;
        for (int i = 0; i < min((int)allTweets.size(), 10); i++) {
            feed.push_back(allTweets[i].second);
        }
        return feed;
    }
    
    void follow(int followerId, int followeeId) {
        following[followerId].insert(followeeId);
    }
    
    void unfollow(int followerId, int followeeId) {
        following[followerId].erase(followeeId);
    }
};
class Twitter:
    def __init__(self):
        self.user_tweets = {}   # userId -> list of (timestamp, tweetId)
        self.following = {}     # userId -> set of followeeIds
        self.time = 0
    
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.time += 1
        if userId not in self.user_tweets:
            self.user_tweets[userId] = []
        self.user_tweets[userId].append((self.time, tweetId))
    
    def getNewsFeed(self, userId: int) -> list[int]:
        # Gather all relevant users
        relevant = {userId}
        if userId in self.following:
            relevant |= self.following[userId]
        
        # Collect all tweets
        all_tweets = []
        for uid in relevant:
            if uid in self.user_tweets:
                all_tweets.extend(self.user_tweets[uid])
        
        # Sort by timestamp descending and take top 10
        all_tweets.sort(key=lambda x: -x[0])
        return [tid for _, tid in all_tweets[:10]]
    
    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId not in self.following:
            self.following[followerId] = set()
        self.following[followerId].add(followeeId)
    
    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId in self.following:
            self.following[followerId].discard(followeeId)
class Twitter {
    private Map<Integer, List<int[]>> userTweets;
    private Map<Integer, Set<Integer>> following;
    private int time;
    
    public Twitter() {
        userTweets = new HashMap<>();
        following = new HashMap<>();
        time = 0;
    }
    
    public void postTweet(int userId, int tweetId) {
        userTweets.computeIfAbsent(userId, k -> new ArrayList<>())
                  .add(new int[]{++time, tweetId});
    }
    
    public List<Integer> getNewsFeed(int userId) {
        List<int[]> allTweets = new ArrayList<>();
        
        // Collect self tweets
        if (userTweets.containsKey(userId)) {
            allTweets.addAll(userTweets.get(userId));
        }
        // Collect followee tweets
        if (following.containsKey(userId)) {
            for (int followee : following.get(userId)) {
                if (userTweets.containsKey(followee)) {
                    allTweets.addAll(userTweets.get(followee));
                }
            }
        }
        
        // Sort descending by timestamp
        allTweets.sort((a, b) -> b[0] - a[0]);
        
        List<Integer> feed = new ArrayList<>();
        for (int i = 0; i < Math.min(allTweets.size(), 10); i++) {
            feed.add(allTweets.get(i)[1]);
        }
        return feed;
    }
    
    public void follow(int followerId, int followeeId) {
        following.computeIfAbsent(followerId, k -> new HashSet<>())
                 .add(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        if (following.containsKey(followerId)) {
            following.get(followerId).remove(followeeId);
        }
    }
}

Complexity Analysis

Time Complexity:

  • postTweet: O(1) — append to a list and increment a counter
  • follow / unfollow: O(1) — hash set insert/remove
  • getNewsFeed: O(N log N) where N is the total number of tweets from the user and all their followees. We collect all N tweets into one list, then sort the entire list. This is the expensive operation.

Space Complexity: O(T + F)

  • T = total tweets across all users (stored in user_tweets)
  • F = total follow relationships (stored in following)
  • The getNewsFeed call creates a temporary list of up to N tweets

Why This Approach Is Not Efficient

The bottleneck is getNewsFeed. Every time a user requests their feed, we:

  1. Collect all tweets from every relevant user (not just the recent ones)
  2. Sort the entire collection
  3. Discard everything except the top 10

With up to 3 × 10^4 total operations, a popular user who follows many prolific tweeters could trigger a getNewsFeed call that scans and sorts thousands of tweets — even though we only need the 10 most recent.

The waste: If User A follows 100 users who each have 300 tweets, getNewsFeed collects 30,000 tweets, sorts all 30,000 in O(30000 × log(30000)) ≈ 450,000 operations, then throws away 29,990 of them.

Key insight: We do not need to see ALL tweets — we only need the 10 most recent. If we could efficiently merge the most recent tweets from each user without sorting everything, we would save enormous work. A min-heap (priority queue) can do exactly this: maintain only the top-k elements from multiple sorted streams, processing just O(k) elements instead of all N.

Optimal Approach - Heap-Based Merge

Intuition

Imagine each user's tweets are like a stack of cards, with the most recent card on top. When building a news feed, instead of dumping ALL cards onto a table and sorting them, you can be much smarter:

  1. Look at only the top card from each relevant user's stack (the most recent tweet from each person).
  2. Among those top cards, pick the one with the highest timestamp — that is the #1 most recent tweet overall.
  3. Remove that card and look at the next card from the same user's stack.
  4. Repeat until you have 10 tweets.

This is exactly what a max-heap (priority queue) does. We seed the heap with one tweet per user (their most recent), then repeatedly extract the maximum and push the next tweet from the same user. We stop after extracting 10 tweets.

This approach processes at most 10 + U tweets (where U is the number of relevant users), compared to sorting all N tweets. When U is small relative to N, this is dramatically faster.

The key data design change is storing each user's tweets as a list in chronological order so we can easily walk backwards from the most recent tweet. We also use a global timestamp counter to determine ordering across users.

Step-by-Step Explanation

Let's trace the heap-based getNewsFeed after these operations:

postTweet(1, 5)   → time=1
follow(1, 2)
postTweet(2, 6)   → time=2
postTweet(1, 7)   → time=3
postTweet(2, 8)   → time=4
postTweet(1, 9)   → time=5
getNewsFeed(1)

State: User 1's tweets = [(1,5), (3,7), (5,9)]. User 2's tweets = [(2,6), (4,8)]. User 1 follows {2}.

Step 1: Identify relevant users: {1, 2}. For each user, find their most recent tweet index (last element in their list). User 1: index 2, tweet (5, 9). User 2: index 1, tweet (4, 8).

Step 2: Seed the max-heap with the most recent tweet from each user: heap = [(-5, 9, user1, idx=2), (-4, 8, user2, idx=1)]. We negate timestamps because Python's heapq is a min-heap.

Step 3: Pop the max: (-5, 9, user1, idx=2). Tweet 9 (time=5) is the most recent overall. Add 9 to feed. feed = [9]. Push User 1's next tweet: index 1, tweet (3, 7). Heap = [(-4, 8, user2, idx=1), (-3, 7, user1, idx=1)].

Step 4: Pop the max: (-4, 8, user2, idx=1). Tweet 8 (time=4). Add to feed. feed = [9, 8]. Push User 2's next: index 0, tweet (2, 6). Heap = [(-3, 7, user1, idx=1), (-2, 6, user2, idx=0)].

Step 5: Pop the max: (-3, 7, user1, idx=1). Tweet 7 (time=3). Add to feed. feed = [9, 8, 7]. Push User 1's next: index 0, tweet (1, 5). Heap = [(-2, 6, user2, idx=0), (-1, 5, user1, idx=0)].

Step 6: Pop the max: (-2, 6, user2, idx=0). Tweet 6 (time=2). Add to feed. feed = [9, 8, 7, 6]. User 2 has no more tweets (index was 0, nothing before it). Heap = [(-1, 5, user1, idx=0)].

Step 7: Pop the max: (-1, 5, user1, idx=0). Tweet 5 (time=1). Add to feed. feed = [9, 8, 7, 6, 5]. User 1 has no more tweets. Heap = empty.

Step 8: Heap is empty and we have < 10 tweets. Return feed = [9, 8, 7, 6, 5]. We processed exactly 5 tweets (all of them in this small example) but would stop at 10 for larger inputs.

Max-Heap Merge — Building News Feed from Multiple Users — Watch how a max-heap efficiently merges tweets from multiple users' sorted lists, extracting only the top-k most recent without scanning all tweets.

Algorithm

Data Structures:

  • user_tweets: HashMap mapping userId → list of (timestamp, tweetId) in chronological order
  • following: HashMap mapping userId → set of followeeIds
  • time: Global integer counter

postTweet(userId, tweetId):

  1. Increment time
  2. Append (time, tweetId) to user_tweets[userId]

getNewsFeed(userId):

  1. Build the set of relevant users: {userId} ∪ following[userId]
  2. Initialize a max-heap
  3. For each relevant user who has tweets:
    • Push their most recent tweet (last element) into the heap along with the user ID and tweet index
  4. While heap is not empty AND feed has fewer than 10 tweets:
    • Extract the tweet with the maximum timestamp
    • Add its tweetId to the feed
    • If the same user has an older tweet (index > 0), push that tweet into the heap
  5. Return the feed

follow(followerId, followeeId):

  1. Add followeeId to following[followerId]

unfollow(followerId, followeeId):

  1. Remove followeeId from following[followerId] if present

Code

class Twitter {
    unordered_map<int, vector<pair<int, int>>> userTweets;
    unordered_map<int, unordered_set<int>> following;
    int timeCounter;
    
public:
    Twitter() : timeCounter(0) {}
    
    void postTweet(int userId, int tweetId) {
        userTweets[userId].push_back({++timeCounter, tweetId});
    }
    
    vector<int> getNewsFeed(int userId) {
        // Max-heap: (timestamp, tweetId, userId, index in their list)
        priority_queue<tuple<int, int, int, int>> maxHeap;
        
        // Seed heap with most recent tweet from each relevant user
        auto seedUser = [&](int uid) {
            if (!userTweets[uid].empty()) {
                int idx = userTweets[uid].size() - 1;
                auto& [ts, tid] = userTweets[uid][idx];
                maxHeap.push({ts, tid, uid, idx});
            }
        };
        
        seedUser(userId);
        for (int followee : following[userId]) {
            seedUser(followee);
        }
        
        vector<int> feed;
        while (!maxHeap.empty() && feed.size() < 10) {
            auto [ts, tid, uid, idx] = maxHeap.top();
            maxHeap.pop();
            feed.push_back(tid);
            
            if (idx > 0) {
                auto& [prevTs, prevTid] = userTweets[uid][idx - 1];
                maxHeap.push({prevTs, prevTid, uid, idx - 1});
            }
        }
        return feed;
    }
    
    void follow(int followerId, int followeeId) {
        following[followerId].insert(followeeId);
    }
    
    void unfollow(int followerId, int followeeId) {
        following[followerId].erase(followeeId);
    }
};
import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.user_tweets = defaultdict(list)  # userId -> [(timestamp, tweetId)]
        self.following = defaultdict(set)     # userId -> set of followeeIds
        self.time = 0
    
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.time += 1
        self.user_tweets[userId].append((self.time, tweetId))
    
    def getNewsFeed(self, userId: int) -> list[int]:
        max_heap = []
        
        # Seed heap with most recent tweet from each relevant user
        relevant = {userId} | self.following[userId]
        for uid in relevant:
            tweets = self.user_tweets[uid]
            if tweets:
                idx = len(tweets) - 1
                ts, tid = tweets[idx]
                # Negate timestamp for max-heap behavior
                heapq.heappush(max_heap, (-ts, tid, uid, idx))
        
        feed = []
        while max_heap and len(feed) < 10:
            neg_ts, tid, uid, idx = heapq.heappop(max_heap)
            feed.append(tid)
            
            if idx > 0:
                prev_ts, prev_tid = self.user_tweets[uid][idx - 1]
                heapq.heappush(max_heap, (-prev_ts, prev_tid, uid, idx - 1))
        
        return feed
    
    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)
    
    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)
class Twitter {
    private Map<Integer, List<int[]>> userTweets;
    private Map<Integer, Set<Integer>> following;
    private int time;
    
    public Twitter() {
        userTweets = new HashMap<>();
        following = new HashMap<>();
        time = 0;
    }
    
    public void postTweet(int userId, int tweetId) {
        userTweets.computeIfAbsent(userId, k -> new ArrayList<>())
                  .add(new int[]{++time, tweetId});
    }
    
    public List<Integer> getNewsFeed(int userId) {
        // Max-heap by timestamp: [timestamp, tweetId, userId, index]
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]
        );
        
        // Seed with most recent tweet from each relevant user
        Set<Integer> relevant = new HashSet<>();
        relevant.add(userId);
        if (following.containsKey(userId)) {
            relevant.addAll(following.get(userId));
        }
        
        for (int uid : relevant) {
            if (userTweets.containsKey(uid)) {
                List<int[]> tweets = userTweets.get(uid);
                if (!tweets.isEmpty()) {
                    int idx = tweets.size() - 1;
                    int[] t = tweets.get(idx);
                    maxHeap.offer(new int[]{t[0], t[1], uid, idx});
                }
            }
        }
        
        List<Integer> feed = new ArrayList<>();
        while (!maxHeap.isEmpty() && feed.size() < 10) {
            int[] top = maxHeap.poll();
            feed.add(top[1]);
            
            int uid = top[2];
            int idx = top[3];
            if (idx > 0) {
                int[] prev = userTweets.get(uid).get(idx - 1);
                maxHeap.offer(new int[]{prev[0], prev[1], uid, idx - 1});
            }
        }
        return feed;
    }
    
    public void follow(int followerId, int followeeId) {
        following.computeIfAbsent(followerId, k -> new HashSet<>())
                 .add(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        if (following.containsKey(followerId)) {
            following.get(followerId).remove(followeeId);
        }
    }
}

Complexity Analysis

Time Complexity:

  • postTweet: O(1) — append to a list and increment a counter
  • follow / unfollow: O(1) — hash set insert/remove
  • getNewsFeed: O(U + K log U) where U is the number of relevant users (self + followees) and K = min(10, total available tweets)
    • Seeding the heap: O(U log U) — one heap push per user
    • Extracting K tweets: K iterations, each doing one pop O(log U) and at most one push O(log U)
    • Total: O(U log U + K log U) = O((U + K) log U)
    • Since K ≤ 10 is constant, this simplifies to O(U log U) which is dramatically better than the brute force O(N log N) where N is the total number of tweets

Space Complexity: O(T + F)

  • T = total tweets across all users
  • F = total follow relationships
  • The heap uses at most O(U) space during getNewsFeed, where U ≤ 500