Pattern visualizer

Design Twitter

Each user already keeps their own tweets in chronological order. Building a news feed is really a k-way merge of those sorted lists — and since you only ever need the newest handful, a max-heap keyed by timestamp can pull them out one at a time without ever sorting a user's whole history. Animated on: Design a simplified Twitter: postTweet, follow/unfollow, and getNewsFeed returning the 10 most recent tweets from a user and everyone they follow, newest first..

Heap

time O(f + k log f)space O(f)step 1 / 15

A·t1

line 4

Push user 1's newest tweet A (time 1) onto the heap — every followee starts with only its most recent post.

Pseudocode

1FUNCTION getNewsFeed(user):
2  heap <- MAX-HEAP keyed by time
3  FOR each followee IN {user} UNION following(user):
4    PUSH followee'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.followee HAS an 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