1
Per-user lists + heap merge
Time O(f + 10 log f) per feed for f followees Space O(users + tweets + follows)tweets: user → list of {time, id}. Feed: push each relevant user's latest tweet into a max-heap by time; pop up to 10, pushing that user's previous tweet each time.
post(1, 5); feed(1); follow(1, 2); post(2, 6); feed(1); unfollow(1, 2); feed(1)tweets {time, id}(map)
user 1: [{0, 5}]
follows(map)
empty
state(vars)
clock: 1
Step 1/5post(1, 5): user 1's list gets tweet 5 stamped with time 0. The clock moves to 1.
import java.util.*;
class Twitter {
private int clock = 0;
private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // {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[]{clock++, tweetId});
}
public List<Integer> getNewsFeed(int userId) {
Set<Integer> users = new HashSet<>(follows.getOrDefault(userId, Set.of()));
users.add(userId);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0])); // {time, user, index}
for (int u : users) {
List<int[]> list = tweets.get(u);
if (list != null && !list.isEmpty()) pq.offer(new int[]{list.get(list.size() - 1)[0], u, list.size() - 1});
}
List<Integer> feed = new ArrayList<>();
while (!pq.isEmpty() && feed.size() < 10) {
int[] top = pq.poll();
List<int[]> list = tweets.get(top[1]);
feed.add(list.get(top[2])[1]);
if (top[2] > 0) pq.offer(new int[]{list.get(top[2] - 1)[0], top[1], top[2] - 1});
}
return feed;
}
public void follow(int followerId, int followeeId) {
if (followerId != followeeId) follows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
Set<Integer> s = follows.get(followerId);
if (s != null) s.remove(followeeId);
}
}Verdict: Pull-based feed; real systems often precompute (push) for most users.