Design Twitter
Design Twitter is a medium heaps problem solved with the merge k sorted pattern.
The best approach, optimal (per-user lists + k-way merge with a heap), runs in O(1) post/follow, O(F + 10 log F) feed time and O(T + F) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (one global tweet list) up.
Problem
Build a small social network class Twitter. Users post short messages called tweets, follow and unfollow each other, and read a news feed.
Twitter()creates an empty network.postTweet(int userId, int tweetId)records a new tweet with idtweetIdwritten byuserId. Each call is newer than every earlier one.getNewsFeed(int userId)returns the ids of the 10 most recent tweets written byuserIdor by anyoneuserIdfollows, newest first (fewer if there are not that many).follow(int followerId, int followeeId)makesfollowerIdfollowfolloweeId;unfollow(int followerId, int followeeId)stops it. Both do nothing if the relation is already in that state.
Examples
Example 1
- Input
Twitter(), postTweet(1, 50), postTweet(2, 60), getNewsFeed(1), follow(1, 2), getNewsFeed(1), unfollow(1, 2), getNewsFeed(1)- Output
[50], [60, 50], [50]- Why
- User 1 first sees only their own tweet. After following user 2, tweet 60 is newer, so it comes first. After unfollowing, it disappears again.
Example 2
- Input
Twitter(), follow(3, 4), postTweet(4, 7), postTweet(3, 8), postTweet(4, 9), getNewsFeed(3), getNewsFeed(4)- Output
[9, 8, 7], [9, 7]- Why
- User 3 sees all three tweets newest first. User 4 follows nobody, so only their own two tweets appear.
Constraints
1 <= userId, followerId, followeeId <= 5000 <= tweetId <= 10^4, and every posted tweet has a different id.followerId != followeeIdinfollowandunfollow.- At most
3 * 10^4calls in total.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (one global tweet list) | O(1) post/follow, O(T) feed | O(T + F) |
| Optimal (per-user lists + k-way merge with a heap) | O(1) post/follow, O(F + 10 log F) feed | O(T + F) |
1Brute force (one global tweet list)
O(1) post/follow, O(T) feedA feed may scan all T tweets ever posted if the user follows few active people.O(T + F)T tweets and F follow relations are stored.Store every tweet in one list in posting order and every user's followee set. To build a feed, walk the global list from the newest tweet backwards and keep the ones written by the user or someone they follow, stopping at 10.
- postTweet: append (userId, tweetId) to the global list.
- follow / unfollow: add to / remove from the follower's set.
- getNewsFeed(u): scan the list from the end; keep a tweet if its author is u or in u's set; stop after 10.
class Twitter {
private final List<int[]> tweets = new ArrayList<>(); // {userId, tweetId}
private final Map<Integer, Set<Integer>> follows = new HashMap<>();
public Twitter() {}
public void postTweet(int userId, int tweetId) {
tweets.add(new int[] { userId, tweetId });
}
public List<Integer> getNewsFeed(int userId) {
Set<Integer> f = follows.getOrDefault(userId, Collections.emptySet());
List<Integer> feed = new ArrayList<>();
for (int i = tweets.size() - 1; i >= 0 && feed.size() < 10; i--) {
int author = tweets.get(i)[0];
if (author == userId || f.contains(author)) feed.add(tweets.get(i)[1]);
}
return feed;
}
public void follow(int followerId, int followeeId) {
follows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
Set<Integer> f = follows.get(followerId);
if (f != null) f.remove(followeeId);
}
}class Twitter:
def __init__(self):
self.tweets: List[Tuple[int, int]] = [] # (userId, tweetId)
self.follows: Dict[int, Set[int]] = {}
def postTweet(self, userId: int, tweetId: int) -> None:
self.tweets.append((userId, tweetId))
def getNewsFeed(self, userId: int) -> List[int]:
f = self.follows.get(userId, set())
feed = []
for i in range(len(self.tweets) - 1, -1, -1):
if len(feed) == 10:
break
author, tid = self.tweets[i]
if author == userId or author in f:
feed.append(tid)
return feed
def follow(self, followerId: int, followeeId: int) -> None:
self.follows.setdefault(followerId, set()).add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
self.follows.get(followerId, set()).discard(followeeId)class Twitter {
vector<pair<int, int>> tweets; // {userId, tweetId}
unordered_map<int, unordered_set<int>> follows;
public:
Twitter() {}
void postTweet(int userId, int tweetId) {
tweets.push_back({userId, tweetId});
}
vector<int> getNewsFeed(int userId) {
unordered_set<int>& f = follows[userId];
vector<int> feed;
for (int i = (int)tweets.size() - 1; i >= 0 && feed.size() < 10; i--) {
int author = tweets[i].first;
if (author == userId || f.count(author)) feed.push_back(tweets[i].second);
}
return feed;
}
void follow(int followerId, int followeeId) {
follows[followerId].insert(followeeId);
}
void unfollow(int followerId, int followeeId) {
follows[followerId].erase(followeeId);
}
};class Twitter {
constructor() {
this.tweets = []; // [userId, tweetId]
this.follows = new Map();
}
postTweet(userId, tweetId) {
this.tweets.push([userId, tweetId]);
}
getNewsFeed(userId) {
const f = this.follows.get(userId) || new Set();
const feed = [];
for (let i = this.tweets.length - 1; i >= 0 && feed.length < 10; i--) {
const [author, tid] = this.tweets[i];
if (author === userId || f.has(author)) feed.push(tid);
}
return feed;
}
follow(followerId, followeeId) {
if (!this.follows.has(followerId)) this.follows.set(followerId, new Set());
this.follows.get(followerId).add(followeeId);
}
unfollow(followerId, followeeId) {
const f = this.follows.get(followerId);
if (f) f.delete(followeeId);
}
}2Optimal (per-user lists + k-way merge with a heap)
O(1) post/follow, O(F + 10 log F) feedBuilding the heap touches the user's F followees once; then only 10 pops and pushes happen, each O(log F).O(T + F)Tweets and follow sets are stored once; the heap holds at most F + 1 entries.Each user keeps their own tweets as a list of (time, tweetId) in posting order, so each list is sorted by time. A feed is the 10 newest entries across the lists of the user and their followees. Put the newest tweet of each such list into a max-heap by time; pop the top, add it to the feed, and push the next older tweet from the same list. After 10 pops (or an empty heap) the feed is done.
- postTweet: append (time++, tweetId) to the user's own list.
- follow / unfollow: update the follower's set.
- getNewsFeed(u): for u and each followee with tweets, push (time, tweetId, user, index of last tweet) into a max-heap.
- Repeat up to 10 times: pop the newest, record its tweetId, and if index > 0 push that user's tweet at index - 1.
class Twitter {
private int time = 0;
private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // user -> {time, tweetId}
private final Map<Integer, Set<Integer>> follows = new HashMap<>();
public Twitter() {}
public void postTweet(int userId, int tweetId) {
tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[] { time++, tweetId });
}
public List<Integer> getNewsFeed(int userId) {
// heap entries: {time, tweetId, user, index}
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
Set<Integer> sources = new HashSet<>(follows.getOrDefault(userId, Collections.emptySet()));
sources.add(userId);
for (int u : sources) {
List<int[]> list = tweets.get(u);
if (list != null && !list.isEmpty()) {
int i = list.size() - 1;
heap.add(new int[] { list.get(i)[0], list.get(i)[1], u, i });
}
}
List<Integer> feed = new ArrayList<>();
while (!heap.isEmpty() && feed.size() < 10) {
int[] top = heap.poll();
feed.add(top[1]);
int i = top[3] - 1;
if (i >= 0) {
int[] t = tweets.get(top[2]).get(i);
heap.add(new int[] { t[0], t[1], top[2], i });
}
}
return feed;
}
public void follow(int followerId, int followeeId) {
follows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
Set<Integer> f = follows.get(followerId);
if (f != null) f.remove(followeeId);
}
}class Twitter:
def __init__(self):
self.time = 0
self.tweets: Dict[int, List[Tuple[int, int]]] = {} # user -> [(time, tweetId)]
self.follows: Dict[int, Set[int]] = {}
def postTweet(self, userId: int, tweetId: int) -> None:
self.tweets.setdefault(userId, []).append((self.time, tweetId))
self.time += 1
def getNewsFeed(self, userId: int) -> List[int]:
heap = [] # (-time, tweetId, user, index)
sources = set(self.follows.get(userId, set()))
sources.add(userId)
for u in sources:
lst = self.tweets.get(u)
if lst:
i = len(lst) - 1
heap.append((-lst[i][0], lst[i][1], u, i))
heapq.heapify(heap)
feed = []
while heap and len(feed) < 10:
_, tid, u, i = heapq.heappop(heap)
feed.append(tid)
if i > 0:
t, nid = self.tweets[u][i - 1]
heapq.heappush(heap, (-t, nid, u, i - 1))
return feed
def follow(self, followerId: int, followeeId: int) -> None:
self.follows.setdefault(followerId, set()).add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
self.follows.get(followerId, set()).discard(followeeId)class Twitter {
int time = 0;
unordered_map<int, vector<pair<int, int>>> tweets; // user -> {time, tweetId}
unordered_map<int, unordered_set<int>> follows;
public:
Twitter() {}
void postTweet(int userId, int tweetId) {
tweets[userId].push_back({time++, tweetId});
}
vector<int> getNewsFeed(int userId) {
// {time, tweetId, user, index}; max-heap by time
priority_queue<tuple<int, int, int, int>> heap;
unordered_set<int> sources = follows[userId];
sources.insert(userId);
for (int u : sources) {
auto it = tweets.find(u);
if (it != tweets.end() && !it->second.empty()) {
int i = it->second.size() - 1;
heap.push({it->second[i].first, it->second[i].second, u, i});
}
}
vector<int> feed;
while (!heap.empty() && feed.size() < 10) {
auto [t, tid, u, i] = heap.top();
heap.pop();
feed.push_back(tid);
if (i > 0) {
auto& p = tweets[u][i - 1];
heap.push({p.first, p.second, u, i - 1});
}
}
return feed;
}
void follow(int followerId, int followeeId) {
follows[followerId].insert(followeeId);
}
void unfollow(int followerId, int followeeId) {
follows[followerId].erase(followeeId);
}
};class Twitter {
constructor() {
this.time = 0;
this.tweets = new Map(); // user -> [[time, tweetId]]
this.follows = new Map();
}
postTweet(userId, tweetId) {
if (!this.tweets.has(userId)) this.tweets.set(userId, []);
this.tweets.get(userId).push([this.time++, tweetId]);
}
getNewsFeed(userId) {
// binary max-heap of [time, tweetId, user, index]
const heap = [];
const push = (e) => {
heap.push(e);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p][0] >= heap[i][0]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0];
const last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < heap.length && heap[l][0] > heap[m][0]) m = l;
if (r < heap.length && heap[r][0] > heap[m][0]) m = r;
if (m === i) break;
[heap[m], heap[i]] = [heap[i], heap[m]];
i = m;
}
}
return top;
};
const sources = new Set(this.follows.get(userId) || []);
sources.add(userId);
for (const u of sources) {
const list = this.tweets.get(u);
if (list && list.length > 0) {
const i = list.length - 1;
push([list[i][0], list[i][1], u, i]);
}
}
const feed = [];
while (heap.length > 0 && feed.length < 10) {
const [, tid, u, i] = pop();
feed.push(tid);
if (i > 0) {
const [t, nid] = this.tweets.get(u)[i - 1];
push([t, nid, u, i - 1]);
}
}
return feed;
}
follow(followerId, followeeId) {
if (!this.follows.has(followerId)) this.follows.set(followerId, new Set());
this.follows.get(followerId).add(followeeId);
}
unfollow(followerId, followeeId) {
const f = this.follows.get(followerId);
if (f) f.delete(followeeId);
}
}Edge cases to test
- News feed of a user with no tweets and no followees is empty
- More than 10 matching tweets: only the 10 newest are returned
- Following the same user twice, or unfollowing someone you do not follow, changes nothing
- A user always sees their own tweets, even after unfollowing everyone
Hints
Hint 1
Give every tweet a global, increasing timestamp so that "newer" is just a bigger number.
Hint 2
The simplest feed scans all tweets from newest to oldest and keeps those written by the user or a followee. That wastes time on unrelated tweets.
Hint 3
Keep a separate list per user, already ordered by time. The feed is then the 10 largest timestamps across several sorted lists: merge them with a max-heap holding one candidate per list.
FAQ
What is the best time complexity for Design Twitter?
Optimal (per-user lists + k-way merge with a heap) runs in O(1) post/follow, O(F + 10 log F) feed time and O(T + F) extra space. Building the heap touches the user's F followees once; then only 10 pops and pushes happen, each O(log F).
Which pattern does Design Twitter use?
It is a heaps problem that uses the merge k sorted pattern. Other problems with the same pattern: Merge k Sorted Lists, Merge k Sorted Arrays, Smallest Range Covering Elements from K Lists.
Is there a brute force solution for Design Twitter?
Yes. Brute force (one global tweet list) takes O(1) post/follow, O(T) feed time and O(T + F) space. Store every tweet in one list in posting order and every user's followee set.
Which edge cases should I test for Design Twitter?
News feed of a user with no tweets and no followees is empty; More than 10 matching tweets: only the 10 newest are returned; Following the same user twice, or unfollowing someone you do not follow, changes nothing; A user always sees their own tweets, even after unfollowing everyone.