A home-timeline service keeps a tiny per-user tweet log and a follow set: who posted, who follows whom, which ten ids belong on the feed. The intern version collected every tweet from you and everyone you follow, sorted by time, and sliced ten. A dozen friends painted instantly. A celebrity followee with years of posts was still sorting a warehouse to fill a ten-slot strip.
Design Twitter is post, follow, unfollow, and a ten-tweet news feed — merge-k on timelines, not a graph walk. Each user owns an append-only list of (time, tweetId). Follows live in a hash table of sets. getNewsFeed seeds a heap with each list’s newest tweet and walks older ones the same way Merge K Sorted Lists walks next — except you emit tweet ids, you do not splice. Find K Pairs is the same seed-heads-then-expand-next idea. This is an interview writeup, not a hash, heap, or graph lecture. Those posts own buckets and sift. The follow “graph” is a HashMap of HashSets. You never DFS it.
The problem
Design a class. postTweet(userId, tweetId) records a tweet. follow(followerId, followeeId) and unfollow(followerId, followeeId) maintain one-hop follows. getNewsFeed(userId) returns up to ten most recent tweet ids from that user and the people they follow, most recent first. Tweet ids are unique. Posts arrive in chronological order; keep a global time++ clock so the class does not depend on id monotonicity. You always “follow” yourself for the feed — do not put userId in that user’s follow set.
postTweet(7, 50)
postTweet(11, 51)
postTweet(3, 52)
follow(7, 11)
getNewsFeed(7) → [51, 50] // 7 sees own 50 and 11’s 51; not 3
follow(7, 3)
getNewsFeed(7) → [52, 51, 50]
postTweet(7, 53)
getNewsFeed(7) → [53, 52, 51, 50]
unfollow(7, 11)
getNewsFeed(7) → [53, 52, 50] // 51 gone
getNewsFeed(11) → [51] // 11 never followed anyone
getNewsFeed(3) → [52]Note: Self tweets always appear. Following yourself is a no-op. Unfollow of someone you do not follow is a no-op. After you follow user 3, 3’s old tweets belong on 7’s feed — the list was already there; follow only adds 3 to the seed set.
Collect every tweet, then sort is the honest brute
Same maps. getNewsFeed copies every (time, tweetId) from self and each followee, sorts by time descending, takes ten. Correct. Slow when a followee’s log is huge and you only needed ten.
List<Integer> getNewsFeedBrute(int userId) {
List<int[]> pool = new ArrayList<>();
List<int[]> mine = tweets.get(userId);
if (mine != null) {
pool.addAll(mine);
}
Set<Integer> set = follows.get(userId);
if (set != null) {
for (int u : set) {
List<int[]> tl = tweets.get(u);
if (tl != null) {
pool.addAll(tl);
}
}
}
pool.sort((a, b) -> Integer.compare(b[0], a[0]));
List<Integer> feed = new ArrayList<>();
for (int i = 0; i < pool.size() && feed.size() < FEED; i++) {
feed.add(pool.get(i)[1]);
}
return feed;
}At a dozen friends this is a rounding error. In production you paid O(T log T) to rank every tweet those users ever posted: which ten ids are newest? Each timeline was already time-ordered. You only needed the next-newest head of F sorted lists.
Max-heap of list tails, then walk older on that list
tweets maps user → append-only list of {time, tweetId}. Newest sits at size() - 1. follows maps follower → set of followees. Java’s PriorityQueue is a min-heap; invert on time so poll is the most recent. Heap entries are {time, tweetId, userId, index}.
- Seed the last tweet of self and each followee. Skip empty timelines.
- Poll, append that
tweetId. If that user has an older tweet, offerindex - 1. - Stop at ten ids, or when the heap is empty.
You never copy a celebrity’s whole log. You never mark tweet ids visited. Heap size stays one live index per user still in the merge — the same k-fronts shape as merge k sorted lists, payload is a tweet instead of a ListNode.
Walk getNewsFeed(7) after 7 posted 53, still following 11 and 3:
tweets:
7: [(t=0, 50), (t=3, 53)]
11: [(t=1, 51)]
3: [(t=2, 52)]
follows[7] = {11, 3}
seed tails: heap [(3,53,u7,i1), (1,51,u11,i0), (2,52,u3,i0)]
poll t=3 emit 53 offer 7 @ i0 (t=0, 50)
heap [(2,52,u3,i0), (1,51,u11,i0), (0,50,u7,i0)]
poll t=2 emit 52 i-1 < 0, no offer
poll t=1 emit 51 i-1 < 0, no offer
poll t=0 emit 50
feed [53, 52, 51, 50]The Java is that class. postTweet appends with time++. follow ignores self. unfollow removes if the set exists.
class Twitter {
static final int FEED = 10;
int time = 0;
Map<Integer, List<int[]>> tweets = new HashMap<>(); // [time, tweetId], append-only
Map<Integer, Set<Integer>> follows = new HashMap<>();
void postTweet(int userId, int tweetId) {
tweets.computeIfAbsent(userId, k -> new ArrayList<>())
.add(new int[] { time++, tweetId });
}
void follow(int followerId, int followeeId) {
if (followerId == followeeId) return; // following self is already implied in feed
follows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
}
void unfollow(int followerId, int followeeId) {
Set<Integer> set = follows.get(followerId);
if (set != null) set.remove(followeeId);
}
List<Integer> getNewsFeed(int userId) {
PriorityQueue<int[]> heap = new PriorityQueue<>(
(a, b) -> Integer.compare(b[0], a[0])); // max-heap on time
List<Integer> users = new ArrayList<>();
users.add(userId);
if (follows.containsKey(userId)) users.addAll(follows.get(userId));
for (int u : users) {
List<int[]> tl = tweets.get(u);
if (tl == null || tl.isEmpty()) continue;
int idx = tl.size() - 1;
int[] tw = tl.get(idx);
heap.offer(new int[] { tw[0], tw[1], u, idx });
}
List<Integer> feed = new ArrayList<>();
while (!heap.isEmpty() && feed.size() < FEED) {
int[] cur = heap.poll();
feed.add(cur[1]);
int idx = cur[3] - 1;
if (idx >= 0) {
int u = cur[2];
int[] tw = tweets.get(u).get(idx);
heap.offer(new int[] { tw[0], tw[1], u, idx });
}
}
return feed;
}
}Time for getNewsFeed is O((F + 10) log F) — F is self plus followees who have tweets; at most F seeds, then ten poll/offer pairs. Heap space is O(F) besides the maps. postTweet / follow / unfollow are expected O(1). Brute sorts T, the whole combined log. Do not re-lecture sift at the whiteboard unless they ask.
Note: Do not add the user to their own follow set, and do not BFS follows. Self is a seed, not an edge. Follow is one hop — friends-of-friends are not on the feed. Skip empty timelines when you seed, or the index walks off a missing list.
What interviewers usually poke next
- Feed size not 10.
FEEDis a named cap. If they passk, stop atkthe same way k pairs stops at k polls. Heap shape does not change. - Unfollow someone not followed.
follows.getmay be null;set.removeon a missing id is a no-op. Do not NPE, do not throw. - Post, then follow. 3 posted 52 before 7 followed 3. The next feed still emits 52. Follow adds a head to the merge; it does not snapshot “tweets from now on.”
- Brute collect-and-sort vs heap merge. Same ten ids. Brute ranks every tweet. Heap only walks ten winners plus F tails. Name that when they ask why not
sort. - Why not a graph traversal. There is no path-finding job. Follows are a set. DFS/BFS would invent friends-of-friends the spec never asked for. This is not a graphs-folder problem.
- Tweet id as time. If they promise ids arrive strictly increasing,
tweetIdcan replacetime++. Prefer the explicit clock so the class does not depend on id monotonicity. - Median from Data Stream. Also a design class plus heaps. Two halves for a moving middle — different job, not a k-way merge.
- LRU Cache. Also a design class plus a hash table. Recency of keys in one list, not a merge of k tweet streams. Do not splice a doubly linked cache into this feed.
You are done with this problem when you can walk users 7, 11, and 3 through post, follow, feed, and unfollow, and you can say why the heap holds F tails instead of every tweet those users ever posted.