Design Twitter
Design a simplified social feed. Twitter() creates an empty system. postTweet(userId, tweetId) records a new tweet by the user; every tweetId is unique, and each call is more recent than the last. getNewsFeed(userId) returns the IDs of the 10 most recent tweets posted by the user or by anyone the user follows, newest first. follow(followerId, followeeId) and unfollow(followerId, followeeId) start and stop following, and unfollowing someone the user doesn't follow has no effect.
Examples
Twitter(); postTweet(1, 11); follow(1, 2); postTweet(2, 21); getNewsFeed(1); unfollow(1, 2); getNewsFeed(1) returns [21, 11], [11]
While following user 2, user 1 sees tweet 21 above their own 11. After unfollowing, only their own tweet remains.
Twitter(); postTweet(3, 31); postTweet(3, 32); getNewsFeed(4) returns []
User 4 follows no one and has posted nothing, so the feed is empty.
Twitter(); postTweet(2, 5); postTweet(3, 9); postTweet(2, 7); follow(1, 2); follow(1, 3); getNewsFeed(1) returns [7, 9, 5]
The feed is ordered by posting time across both users, so 7, posted last, comes first.
Constraints
- 1 <= userId, followerId, followeeId <= 500
- 0 <= tweetId <= 10^4
- All tweet IDs are unique.
- followerId != followeeId in follow and unfollow.
- At most 3 * 10^4 calls will be made in total.
Hints
Each user's own tweets are already in time order. What does building the feed have in common with merging sorted lists?
Stamp each tweet with a global counter. The feed is the 10 largest timestamps across several sorted lists, which a heap with one entry per list finds without scanning everything.
Push the latest tweet of the user and of each followee into a max-heap as (time, tweetId, userId, index). Pop up to 10 times, and after each pop push the same user's tweet at index - 1 if it exists.
Drill This: Your Approach First
Approach
Stamp every tweet with a global counter, keep each user's tweets in a list in posting order, and keep each user's followees in a hash set. postTweet, follow, and unfollow are then O(1). getNewsFeed is a k-way merge: the user and each followee have a list already sorted by time, so seed a max-heap with the newest tweet from each list, then repeatedly pop the most recent tweet, add it to the feed, and push the next older tweet from the same user, until the feed holds 10 tweets or the heap is empty. With f followees that's O(f log f) per feed, independent of how many tweets exist.
Time
O(1) post and follow, O(f log f) feed
Space
O(users + tweets + follows)
Pitfall
Solutions
class Twitter {
private int clock = 0;
private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // userId -> [time, tweetId]
private final Map<Integer, Set<Integer>> following = new HashMap<>();
public Twitter() {}
public void postTweet(int userId, int tweetId) {
tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{clock++, tweetId});
}
public List<Integer> getNewsFeed(int userId) {
// Heap entries: [time, tweetId, userId, index], newest first.
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
Set<Integer> users = new HashSet<>(following.getOrDefault(userId, Collections.emptySet()));
users.add(userId);
for (int u : users) {
List<int[]> list = tweets.get(u);
if (list == null || list.isEmpty()) continue;
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) {
following.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
Set<Integer> set = following.get(followerId);
if (set != null) set.remove(followeeId);
}
}import heapq
from collections import defaultdict
class Twitter:
def __init__(self):
self.clock = 0
self.tweets = defaultdict(list) # userId -> [(time, tweetId)]
self.following = defaultdict(set)
def postTweet(self, userId: int, tweetId: int) -> None:
self.tweets[userId].append((self.clock, tweetId))
self.clock += 1
def getNewsFeed(self, userId: int):
heap = []
for u in self.following[userId] | {userId}:
if self.tweets[u]:
i = len(self.tweets[u]) - 1
time, tweet = self.tweets[u][i]
heap.append((-time, tweet, u, i))
heapq.heapify(heap)
feed = []
while heap and len(feed) < 10:
_, tweet, u, i = heapq.heappop(heap)
feed.append(tweet)
if i > 0:
time, older = self.tweets[u][i - 1]
heapq.heappush(heap, (-time, older, u, i - 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)