Design Twitter

k-way merge of each user's tweets via a max-heap keyed by time

time O(u + k log u)space O(u)

Each source already keeps its own tweets in chronological order, so building a feed is a k-way merge of sorted lists. Seed a max-heap with one entry per source — its newest unseen tweet — then repeatedly pop the global newest and, if that source has an older tweet left, push it back in. The heap never holds more than one entry per source, so it stays tiny no matter how much history each user has.

Details

Animated on: getNewsFeed(1) where user 1 posted A@t1 and follows user 2 (D@t6, B@t3) and user 3 (E@t5, F@t2). Expected feed, newest first: [D, E, B, F, A].

Problem:Design TwitterMedium

k-way merge of each user's tweets via a max-heap keyed by time

step 1 / 11

A·t1

Seed the heap: user 1 is a source of their own feed. Push A·t1 onto the heap. It settles at index 0 — its parent is already newer.

Pseudocode

1FUNCTION getNewsFeed(user):
2  heap <- MAX-HEAP keyed by time
3  FOR each source IN {user} UNION following(user):
4    PUSH source's newest tweet INTO heap
5  feed <- EMPTY LIST
6  WHILE heap NOT EMPTY AND LENGTH(feed) < 10:
7    top <- POP MAX(heap)
8    APPEND top.tweetId TO feed
9    IF top.source HAS older tweet:
10      PUSH that older tweet INTO heap
11  RETURN feed

← / → step · space play · Home restart

Every step in words

Show all 11 steps

Seed the heap: user 1 is a source of their own feed. Push A·t1 onto the heap. It settles at index 0 — its parent is already newer.
Followee 2 is a source too. Push D·t6 onto the heap. It out-ranks its parent by timestamp, so it sifts up to index 0.
Followee 3 is a source too. Push E·t5 onto the heap. It settles at index 2 — its parent is already newer.
Pop the max: D·t6 is the newest timestamp on the heap, so append D to the feed (now [D]). The last entry moves to the root and sifts down; E·t5 settles at the top.
User 2 has an older tweet left. Push B·t3 onto the heap. It settles at index 2 — its parent is already newer.
Pop the max: E·t5 is the newest timestamp on the heap, so append E to the feed (now [D, E]). The last entry moves to the root and sifts down; B·t3 settles at the top.
User 3 has an older tweet left. Push F·t2 onto the heap. It settles at index 2 — its parent is already newer.
Pop the max: B·t3 is the newest timestamp on the heap, so append B to the feed (now [D, E, B]). The last entry moves to the root and sifts down; F·t2 settles at the top.
Pop the max: F·t2 is the newest timestamp on the heap, so append F to the feed (now [D, E, B, F]). The last entry moves to the root and sifts down; A·t1 settles at the top.
Pop the max: A·t1 is the newest timestamp on the heap, so append A to the feed (now [D, E, B, F, A]). The heap is now empty.
Feed done: [D, E, B, F, A] — every source's tweets came out in one global newest-to-oldest order, and each of the 5 tweets was pushed and popped exactly once.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Design Twitter in the editor All Heap problems Back to roadmap