Design Twitter: building a news feed

Every tweet gets a global timestamp. Each user's tweets are stored oldest → newest. To build a feed, put the newest tweet of each followed user into a max-heap. Then repeatedly take the most recent one and let that user's next-older tweet take its place, until 10 tweets are collected. This is a k-way merge of sorted lists.

Use post 1 5, feed 1, follow 1 2, unfollow 1 2, or paste LeetCode's two input arrays.
Try:
CALL
1 / 1

Operations

Click a call to jump to it

Code

Users

Tweets are listed newest first (stored oldest first). t is the global timestamp. In a feed: blue = candidate in the heap, green ✓ = already in the feed.

getNewsFeed merge

heap one candidate per user: newest not-yet-taken tweet; most recent on top

feed most recent → least recent, stops at 10

Cost: postTweet, follow and unfollow are O(1). A feed over f followees costs O(f + 10·log f), because the heap never holds more than one tweet per user, and it never looks at more than 10 + f tweets, however many exist.

Dry-run trace

Every step as a row. Click a row to jump there.

#ActionCallDetailheap (t:id)feed

Keyboard: ← → step, Space play or pause. Up to 40 calls and 8 different users.