Design Twitter

Design Twitter is a classic systems-flavored interview problem. The whole thing fits in a hash map plus one neat trick for the feed: a heap that merges many sorted tweet lists into one newest-first stream.

The slow way first

The blunt approach: when someone asks for a feed, gather every tweet from the user and all their followees into one big list, sort it all by time, and slice the top 10. If a user follows k people holding n tweets total, that is O(n log n) every single call — and you re-sort tweets you have already sorted a thousand times.

The question to ask: each user list is already in time order — why throw that away? We only need the 10 newest, and each list is sorted, so we can merge lazily and stop early.

The idea: a heap to merge sorted lists

Give each user a tweet list (kept in post order, so newest is last) and a follow set. For the feed, treat each source list as a stream and merge them newest-first with a max-heap keyed by time.

Seed the heap with the newest tweet from each source (the followees plus the user themselves). Repeatedly pop the heap top — that is the globally newest unseen tweet — and when you pop a tweet, push that user next-older tweet so their stream keeps feeding the heap. Stop after 10 pops.

The heap only ever holds one tweet per source at a time, so it stays tiny no matter how many tweets exist.

Walk through it

Step through the animation. u1 follows u2 and u3, so the sources are {u1, u2, u3}. We seed the heap with each source newest tweet: 22 (t=6), 11 (t=5), 32 (t=4). Pop 22 and push u2 older tweet 21. Pop 11 (u1 has none older). Pop 32 and push u3 older tweet 31. After three pops the feed is [22, 11, 32] — newest-first, and we never sorted every tweet.

Pseudocode

get_news_feed(user):
    heap = empty max-heap keyed by time
    for each source in (people user follows) + user:
        if source has tweets:
            push source NEWEST tweet (time, id, source, index)
    feed = []
    while heap not empty and feed has < 10:
        pop the max (newest) tweet -> add its id to feed
        if that source has an older tweet:
            push that older tweet
    return feed

The Python solution

def get_news_feed(self, user_id):
    feed = []
    heap = []
    sources = self.following[user_id] | {user_id}
    for uid in sources:
        tweets = self.tweets[uid]
        if tweets:
            t, tid = tweets[-1]
            heapq.heappush(heap, (-t, tid, uid, len(tweets) - 1))
    while heap and len(feed) < 10:
        neg_t, tid, uid, idx = heapq.heappop(heap)
        feed.append(tid)
        if idx > 0:
            t, ptid = self.tweets[uid][idx - 1]
            heapq.heappush(heap, (-t, ptid, uid, idx - 1))
    return feed

• sources is the followee set unioned with the user themselves — a user always sees their own tweets.
• For each source we push its last tweet (newest, since lists grow at the end). Python heapq is a min-heap, so we store -t to pop the largest time first.
• Each heap entry carries (-t, tid, uid, idx) — the time key, the tweet id, the owning user, and the index into that user list so we can find the previous tweet.
• The loop pops the newest tweet, appends its id, and if that source has an older tweet (idx > 0) pushes it. This keeps each stream alive without ever loading the whole list.
• We stop at 10 (or when the heap empties), so we touch far fewer than all the tweets.

Complexity

Building the feed costs O(k) to seed plus O(10 log k) for ten pops — the heap holds at most one tweet per source, so it stays size k. We trade a tiny heap for skipping a full sort on every feed request.

When this pattern shows up

Practice