Pattern visualizer

Design Twitter

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. 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]..

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

time O(u + k log u)space O(u)step 1 / 11

A·t1

line 4

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

Where to practice Heap

Practice Heap problems All Heap problems Back to roadmap