Log inSign up
mediumLeetCodeNot Started

Design Twitter

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and see the 10 most recent tweets in the user's 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 the user userId. Each call 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 is following or by the user themself. 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 stopped following the user with ID followeeId.

Example 1 · 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.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Design Twitter.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Design Twitter
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Toy models or small mock services.
  • BETTER: Moderate follower counts where combining and sorting 10 × F items is inexpensive.
  • OPTIMAL: Industry-standard approach for real-time feed aggregation across feeds.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Global Tweet Log Filtering

Intuition

Store all tweets globally in a single list [(timestamp, userId, tweetId)]. Maintain a follower mapping followers[followerId] = set of followeeIds. When getNewsFeed(userId) is called, scan through the global tweet log backwards, checking if the author is userId or in the user's follow set. Collect up to 10 tweets and return. While simple, iterating through all global tweets scales with O(T) where T is the total number of tweets across all users.

When to apply: Toy models or small mock services.

Algorithm

  1. Step 1: Maintain a global tweets array and a followees map of sets.
  2. Step 2: On postTweet, append (timestamp++, userId, tweetId) to the global tweets array.
  3. Step 3: On follow and unfollow, add/remove followeeId from following[followerId].
  4. Step 4: On getNewsFeed, scan backwards from the end of global tweets, appending matching tweetIds until 10 are collected.
  5. Step 5: Return the collected list of tweet IDs.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5
6struct Tweet {
7 int time;
8 int userId;
9 int tweetId;
10};
11
12class TwitterBrute {
13 int timer = 0;
14 std::vector<Tweet> allTweets;
15 std::unordered_map<int, std::unordered_set<int>> following;
16public:
17 TwitterBrute() {}
18
19 void postTweet(int userId, int tweetId) {
20 allTweets.push_back({timer++, userId, tweetId});
21 }
22
23 std::vector<int> getNewsFeed(int userId) {
24 std::vector<int> feed;
25 const auto& follows = following[userId];
26 for (int i = (int)allTweets.size() - 1; i >= 0 && feed.size() < 10; --i) {
27 int author = allTweets[i].userId;
28 if (author == userId || follows.count(author)) {
29 feed.push_back(allTweets[i].tweetId);
30 }
31 }
32 return feed;
33 }
34
35 void follow(int followerId, int followeeId) {
36 if (followerId != followeeId) {
37 following[followerId].insert(followeeId);
38 }
39 }
40
41 void unfollow(int followerId, int followeeId) {
42 following[followerId].erase(followeeId);
43 }
44};
45
46int main() {
47 TwitterBrute twitter;
48 twitter.postTweet(1, 5);
49 auto f1 = twitter.getNewsFeed(1);
50 std::cout << f1[0] << std::endl;
51 twitter.follow(1, 2);
52 twitter.postTweet(2, 6);
53 auto f2 = twitter.getNewsFeed(1);
54 for (int t : f2) std::cout << t << " ";
55 std::cout << std::endl;
56 twitter.unfollow(1, 2);
57 auto f3 = twitter.getNewsFeed(1);
58 for (int t : f3) std::cout << t << " ";
59 std::cout << std::endl;
60 return 0;
61}

Time & Space Complexity

  • Time complexity: O(1) for postTweet, follow, unfollow; O(T) for getNewsFeed where T is total tweets
  • Space complexity: O(T + U^2) where T is total tweets and U is number of users

2. Per-User Tweet Lists + Combined Sorting

Intuition

Store tweets in a hash map where each userId maps to an array of their own tweets [(time, tweetId)]. When user requests news feed: 1. Gather the latest <= 10 tweets from userId itself, plus the latest <= 10 tweets from each user in following[userId]. 2. Total collected candidates is at most 10 × (F + 1) where F is followee count. 3. Sort all candidates descending by timestamp and return the top 10 tweet IDs. This decouples feed generation from unrelated users, significantly faster than scanning all global tweets.

When to apply: Moderate follower counts where combining and sorting 10 × F items is inexpensive.

Algorithm

  1. Step 1: Map userId to an array of personal tweets { time, tweetId }.
  2. Step 2: On postTweet, append tweet to the user's personal array.
  3. Step 3: On getNewsFeed, gather recent tweets from self and all followees into a combined list.
  4. Step 4: Sort the combined list descending by time.
  5. Step 5: Extract the first 10 tweet IDs and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5#include <algorithm>
6
7struct TweetPair {
8 int time;
9 int tweetId;
10};
11
12class TwitterBetter {
13 int timer = 0;
14 std::unordered_map<int, std::vector<TweetPair>> userTweets;
15 std::unordered_map<int, std::unordered_set<int>> following;
16public:
17 TwitterBetter() {}
18
19 void postTweet(int userId, int tweetId) {
20 userTweets[userId].push_back({timer++, tweetId});
21 }
22
23 std::vector<int> getNewsFeed(int userId) {
24 std::vector<TweetPair> candidates;
25 std::unordered_set<int> authors = following[userId];
26 authors.insert(userId);
27
28 for (int author : authors) {
29 const auto& tweets = userTweets[author];
30 int n = tweets.size();
31 for (int i = n - 1; i >= std::max(0, n - 10); --i) {
32 candidates.push_back(tweets[i]);
33 }
34 }
35
36 std::sort(candidates.begin(), candidates.end(), [](const TweetPair& a, const TweetPair& b) {
37 return a.time > b.time;
38 });
39
40 std::vector<int> feed;
41 for (size_t i = 0; i < std::min((size_t)10, candidates.size()); ++i) {
42 feed.push_back(candidates[i].tweetId);
43 }
44 return feed;
45 }
46
47 void follow(int followerId, int followeeId) {
48 if (followerId != followeeId) {
49 following[followerId].insert(followeeId);
50 }
51 }
52
53 void unfollow(int followerId, int followeeId) {
54 following[followerId].erase(followeeId);
55 }
56};
57
58int main() {
59 TwitterBetter twitter;
60 twitter.postTweet(1, 5);
61 auto f1 = twitter.getNewsFeed(1);
62 std::cout << f1[0] << std::endl;
63 twitter.follow(1, 2);
64 twitter.postTweet(2, 6);
65 auto f2 = twitter.getNewsFeed(1);
66 for (int t : f2) std::cout << t << " ";
67 std::cout << std::endl;
68 twitter.unfollow(1, 2);
69 auto f3 = twitter.getNewsFeed(1);
70 for (int t : f3) std::cout << t << " ";
71 std::cout << std::endl;
72 return 0;
73}

Time & Space Complexity

  • Time complexity: O(1) for postTweet, follow, unfollow; O(F * log(F)) where F is number of followees for getNewsFeed
  • Space complexity: O(T + U^2) total space

3. Per-User Tweet Lists + K-Way Merge with Max-Heap

Intuition

Because every user's tweets are already chronologically ordered, retrieving the top 10 tweets across all followees is an instance of the K-Way Merge problem (identical to Merge K Sorted Lists): 1. Identify all F users the requester follows, plus the requester themself (F + 1 streams). 2. Insert the most recent tweet of each non-empty stream into a max-heap (priority queue ordered by timestamp), along with the stream pointer/index. 3. In a loop running at most 10 times: - Extract the top element from the heap (guaranteed to be the globally most recent across all candidate streams). - Append its tweetId to the news feed result. - If that stream has another older tweet available, push it into the heap. 4. Stop when 10 tweets are retrieved or the heap is empty. 5. This requires only O(F + 10 log F) time per getNewsFeed, completely avoiding full list sorting.

When to apply: Industry-standard approach for real-time feed aggregation across feeds.

Algorithm

  1. Step 1: Each user maintains an append-only list of tweets.
  2. Step 2: Collect followees and user self into a set of candidate authors.
  3. Step 3: Push the newest tweet of each author into a max-heap keyed by timestamp.
  4. Step 4: Repeatedly extract max from heap, append tweetId to feed, and push the author's next newer tweet.
  5. Step 5: Stop after 10 tweets or heap exhaustion, and return the feed.

Interactive trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
postTweet(1, 5): User 1 posts tweet 5 at t=0
Visual state
Values and pointers at this exact step
pointers
S
5
0
Check / comparison
userTweets[1] = [{ time: 0, tweetId: 5 }]
Decision / next transition
Tweet recorded successfully.
Why this step matters

postTweet(1, 5): User 1 posts tweet 5 at t=0.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5#include <queue>
6
7struct Tweet {
8 int time;
9 int tweetId;
10};
11
12struct HeapNode {
13 int time;
14 int tweetId;
15 int author;
16 int idx;
17
18 bool operator<(const HeapNode& other) const {
19 return time < other.time; // Max-heap
20 }
21};
22
23class Twitter {
24 int timer = 0;
25 std::unordered_map<int, std::vector<Tweet>> userTweets;
26 std::unordered_map<int, std::unordered_set<int>> following;
27public:
28 Twitter() {}
29
30 void postTweet(int userId, int tweetId) {
31 userTweets[userId].push_back({timer++, tweetId});
32 }
33
34 std::vector<int> getNewsFeed(int userId) {
35 std::priority_queue<HeapNode> maxHeap;
36 std::unordered_set<int> authors = following[userId];
37 authors.insert(userId);
38
39 for (int author : authors) {
40 auto it = userTweets.find(author);
41 if (it != userTweets.end() && !it->second.empty()) {
42 int lastIdx = (int)it->second.size() - 1;
43 maxHeap.push({it->second[lastIdx].time, it->second[lastIdx].tweetId, author, lastIdx});
44 }
45 }
46
47 std::vector<int> feed;
48 while (!maxHeap.empty() && feed.size() < 10) {
49 HeapNode top = maxHeap.top();
50 maxHeap.pop();
51 feed.push_back(top.tweetId);
52
53 if (top.idx > 0) {
54 int nextIdx = top.idx - 1;
55 const auto& prevTweet = userTweets[top.author][nextIdx];
56 maxHeap.push({prevTweet.time, prevTweet.tweetId, top.author, nextIdx});
57 }
58 }
59
60 return feed;
61 }
62
63 void follow(int followerId, int followeeId) {
64 if (followerId != followeeId) {
65 following[followerId].insert(followeeId);
66 }
67 }
68
69 void unfollow(int followerId, int followeeId) {
70 following[followerId].erase(followeeId);
71 }
72};
73
74int main() {
75 Twitter twitter;
76 twitter.postTweet(1, 5);
77 auto f1 = twitter.getNewsFeed(1);
78 std::cout << f1[0] << std::endl;
79 twitter.follow(1, 2);
80 twitter.postTweet(2, 6);
81 auto f2 = twitter.getNewsFeed(1);
82 for (int t : f2) std::cout << t << " ";
83 std::cout << std::endl;
84 twitter.unfollow(1, 2);
85 auto f3 = twitter.getNewsFeed(1);
86 for (int t : f3) std::cout << t << " ";
87 std::cout << std::endl;
88 return 0;
89}

Time & Space Complexity

  • Time complexity: O(1) for postTweet, follow, unfollow; O(F + 10 log F) for getNewsFeed where F is followee count
  • Space complexity: O(T + U^2) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Global Tweet Log FilteringO(1) for postTweet, follow, unfollow; O(T) for getNewsFeed where T is total tweetsO(T + U^2) where T is total tweets and U is number of usersLog every posted tweet into a global array with an incrementing timestamp. Filter and reverse-scan on news feed requests.O(1) for postTweet, follow, unfollow; O(T) for getNewsFeed where T is total tweets
2.Per-User Tweet Lists + Combined SortingO(1) for postTweet, follow, unfollow; O(F * log(F)) where F is number of followees for getNewsFeedO(T + U^2) total spaceStore tweets separately under each author. On news feed request, gather the recent tweets of all followees and sort them together.O(1) for postTweet, follow, unfollow; O(F * log(F)) where F is number of followees for getNewsFeed
3.Per-User Tweet Lists + K-Way Merge with Max-HeapOptimalO(1) for postTweet, follow, unfollow; O(F + 10 log F) for getNewsFeed where F is followee countO(T + U^2) auxiliary spaceModel each followed user's tweet history as a sorted stream and merge the top 10 tweets using a priority queue in O(F + 10 log F) time.O(1) for postTweet, follow, unfollow; O(F + 10 log F) for getNewsFeed where F is followee count

Common Pitfalls & Crucial Edge Cases

Pushing all historic tweets of all followed users into a heap

If followed users have 10,000 tweets, pushing all takes O(TotalTweets log TotalTweets). Only pull the top 10 from each user's list or use K-way merge.

Not accounting for the user's own tweets

Forgetting to include the user's personal tweet list in the K-way merge.

Global timestamp vs tweetId

Tweet IDs are NOT guaranteed to be strictly chronological. You must maintain a separate monotonically increasing global timestamp counter.

Crucial Edge Cases to Validate:

  • User unfollows someone they never followed — Unfollow operation should be a no-op without error.
  • User tries to unfollow themselves — A user cannot unfollow themselves from their feed.
  • User has no tweets and follows no one — Feed returns an empty list [].
  • Total tweets available across all followees is less than 10 — Feed returns all available tweets in descending timestamp order.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast Pull (Fan-out on Read) with Push (Fan-out on Write): Twitter originally used Push for active users and Pull for high-follower celebrities.
  2. Explain the K-way merge pattern: identical to 'Merge K Sorted Lists'.
  3. Mention pagination and cursor-based querying for real-world feed generation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does Design Twitter generate the 10 most recent tweets in a user's news feed?

2.How should a user's followers and followees be tracked in O(1) time?

3.Must a user always see their own tweets in their news feed?

Back to DSA Sheet