Twitter feed design

Twitter ran 6,000 writes per second and 300,000 reads per second when Raffi Krikorian gave the architecture talk in 2013. The fifty-to-one ratio is the only number that matters for picking a timeline strategy. Read-side merging from scratch on every request would melt the read tier; pre-computing every follower's timeline at write time would melt the write tier for accounts like Lady Gaga (31 million followers in 2013, 31 million Redis inserts per tweet). The production answer is a hybrid that splits the workload by celebrity threshold. The LC 355 answer is the read-side merge core of that hybrid, raised to a class boundary, with the production scale removed so the algorithm is what's left.

The four-method contract is fixed: postTweet, follow, unfollow, getNewsFeed. Three of those are one-line operations on a hash map. The fourth is the chapter. getNewsFeed(u) returns the ten most recent tweets across u and everyone u follows, ordered most-recent first, and that's a k-way merge of |followees| + 1 time-sorted lists with a hard cap on the output size. The shape is the same as LC 23 Merge k Sorted Lists, and we already taught the merge in Heaps and priority queues. What's new here is wrapping that merge inside a class with state, making the timestamps monotonic so the order is unambiguous, and noticing that the feed cap of 10 turns the asymptotic envelope from O(n log k) into O(k log k) regardless of how many tweets exist.

The four methods, in plain terms#

A user can do four things. They can post a tweet, which adds the tweet to their personal log. They can follow another user, which adds that user to their follow set. They can unfollow, which removes one. And they can ask for their news feed, which returns up to ten of the most recent tweets across themselves and everyone they follow, newest first.^[1]

Three pieces of state cover all four operations: a per-user list of tweets, a per-user follow set, and one global counter that ticks up on every post.

The global counter is what makes ordering across users unambiguous. Real Twitter uses Snowflake IDs that embed a 41-bit millisecond timestamp; the LC harness gives us a single integer that increments once per call, which is the same idea minus the wall-clock.^[2] Two posts from two different users in two different postTweet calls receive distinct, comparable ts values, so "newest first" has one definition across the whole class.

Each instance owns a per-user tweet log (append-only) and a per-user follow set; ts is the monotonic global counter that orders tweets across all users.

postTweet, follow, unfollow#

Three of the four methods are hash-map updates. They earn one paragraph total.

postTweet(userId, tweetId) increments the global timestamp, then appends (ts, tweetId) to that user's log. The append is amortized O(1) per call by the standard dynamic-array argument we proved in Hash maps and hash sets, and the log is time-sorted by construction because every new entry carries a ts strictly greater than every previous entry. follow(followerId, followeeId) short-circuits the self-follow case (a user following themselves is a no-op; their own tweets already reach their feed through a different path) and otherwise inserts followeeId into the follower's set. unfollow(followerId, followeeId) calls the set's discard primitive (Python's set.discard, Java's Set.remove, C++'s unordered_set::erase, Go's delete); all four are silent on missing keys, which matches the LC contract that unfollowing someone you don't follow is not an error.^[1:1] All three operations are expected O(1) under the chained-hash-table bound from CLRS Theorem 11.1.^[3]

The teaching content of this chapter starts at the fourth method.

getNewsFeed: the k-way merge#

The naive reading is the wrong reading. "Return the ten most recent tweets across the user and everyone they follow" sounds like collect every tweet, sort by timestamp, take the first ten. That works. It also wastes most of its work.

# Wrong instinct: O(N log N) where N = total tweets across all followees
def get_news_feed_wrong(self, userId):
    authors = self.following[userId] | {userId}
    all_tweets = []
    for a in authors:
        all_tweets.extend(self.tweets[a])
    all_tweets.sort(key=lambda t: -t[0])
    return [tid for _, tid in all_tweets[:10]]

Two things are wrong with that. First, the sort is doing far more work than the answer needs. We want ten items; the sort produces a fully-ordered sequence of all N items and throws N - 10 of them away. Second, N is unbounded: a user following 1,000 people who each posted 1,000 times has a million tweets to sort on every news-feed call. The correct shape is partial merge with early stop.

The reduction is the chapter's hardest insight: each followee's tweet log is already sorted by timestamp, in descending order if we read it from the back. So getNewsFeed is not "sort across followees", it's "merge across followees and stop after ten." That's LC 23 Merge k Sorted Lists with two adjustments: the lists are read from the back instead of the front, and the merge halts at ten outputs instead of running to exhaustion.

The k-way merge with a max-heap is the standard solution. Seed the heap with one entry per author (the most recent tweet of each followee, plus the user's own most recent), then pop ten times, pushing each popped author's next-older tweet back onto the heap before the next pop. Heap size never exceeds k = |followees| + 1 because every pop is paired with at most one push from the same author.^[4]

# LC 355. Design Twitter
# In-memory class with four operations. The non-trivial work is in
# getNewsFeed, which k-way-merges per-author tweet logs through a max-heap
# keyed on a monotonic timestamp. Heap size is bounded by the author count,
# not the total tweet count, because each author contributes one entry at a
# time. O(k log k) per call where k = |followees| + 1; O(1) for the others.
import heapq
from collections import defaultdict
from typing import Dict, List, Set, Tuple


class Twitter:
    """In-memory Twitter timeline supporting post/follow/unfollow/news-feed."""

    FEED_CAP = 10

    def __init__(self) -> None:
        self.tweets: Dict[int, List[Tuple[int, int]]] = defaultdict(list)
        self.following: Dict[int, Set[int]] = defaultdict(set)
        self.ts: int = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.ts += 1
        self.tweets[userId].append((self.ts, tweetId))

    def getNewsFeed(self, userId: int) -> List[int]:
        authors = self.following[userId] | {userId}
        # heapq is min-only; negate ts to simulate a max-heap.
        heap: List[Tuple[int, int, int, int]] = []
        for a in authors:
            tw = self.tweets.get(a)
            if not tw:
                continue
            idx = len(tw) - 1
            ts, tid = tw[idx]
            heapq.heappush(heap, (-ts, tid, a, idx))

        feed: List[int] = []
        while heap and len(feed) < self.FEED_CAP:
            _, tid, a, idx = heapq.heappop(heap)
            feed.append(tid)
            if idx > 0:
                next_idx = idx - 1
                nts, ntid = self.tweets[a][next_idx]
                heapq.heappush(heap, (-nts, ntid, a, next_idx))
        return feed

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId == followeeId:
            return
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)

// LC 355. Design Twitter
// In-memory class with four operations. getNewsFeed runs a bounded
// k-way merge through a max-heap keyed on a monotonic timestamp; each
// author contributes at most one heap entry at a time, so heap size
// stays at |followees| + 1. PriorityQueue<int[]> avoids autoboxing
// in the comparator hot path; the comparator uses Integer.compare(b, a)
// for max-heap semantics without subtraction-overflow risk.
import java.util.*;

public class Twitter {
    private static final int FEED_CAP = 10;

    private final Map<Integer, List<int[]>> tweets = new HashMap<>();      // userId -> list of {ts, tweetId}
    private final Map<Integer, Set<Integer>> following = new HashMap<>();  // userId -> followees
    private int ts = 0;

    public Twitter() {}

    public void postTweet(int userId, int tweetId) {
        ts++;
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{ts, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> authors = new HashSet<>(following.getOrDefault(userId, Collections.emptySet()));
        authors.add(userId);

        // Max-heap on ts. Entry: [ts, tweetId, authorId, idxInTheirList].
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        for (int a : authors) {
            List<int[]> tw = tweets.get(a);
            if (tw == null || tw.isEmpty()) continue;
            int idx = tw.size() - 1;
            int[] last = tw.get(idx);
            heap.offer(new int[]{last[0], last[1], a, idx});
        }

        List<Integer> feed = new ArrayList<>(FEED_CAP);
        while (!heap.isEmpty() && feed.size() < FEED_CAP) {
            int[] top = heap.poll();
            feed.add(top[1]);
            int a = top[2];
            int idx = top[3];
            if (idx > 0) {
                int next = idx - 1;
                int[] prev = tweets.get(a).get(next);
                // Allocate a fresh array on push; never mutate one already in the heap.
                heap.offer(new int[]{prev[0], prev[1], a, next});
            }
        }
        return feed;
    }

    public void follow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        following.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        Set<Integer> s = following.get(followerId);
        if (s != null) s.remove(followeeId);
    }
}

// LC 355. Design Twitter
// In-memory class with four operations. getNewsFeed runs a bounded
// k-way merge through a max-heap keyed on a monotonic timestamp.
// std::priority_queue is the rare structural win in C++: max-heap is
// the default, and tuples compare lexicographically, so the leading
// ts field drives the order without a custom comparator.
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>
#include <tuple>

class Twitter {
public:
    Twitter() = default;

    void postTweet(int userId, int tweetId) {
        ++ts;
        tweets[userId].emplace_back(ts, tweetId);
    }

    std::vector<int> getNewsFeed(int userId) {
        std::unordered_set<int> authors = following[userId];
        authors.insert(userId);

        std::priority_queue<std::tuple<int, int, int, int>> heap;
        for (int a : authors) {
            auto it = tweets.find(a);
            if (it == tweets.end() || it->second.empty()) continue;
            int idx = static_cast<int>(it->second.size()) - 1;
            const auto& [t, tid] = it->second[idx];
            heap.emplace(t, tid, a, idx);
        }

        std::vector<int> feed;
        feed.reserve(FEED_CAP);
        while (!heap.empty() && static_cast<int>(feed.size()) < FEED_CAP) {
            auto [t, tid, a, idx] = heap.top();
            heap.pop();
            feed.push_back(tid);
            if (idx > 0) {
                int next = idx - 1;
                const auto& [pt, ptid] = tweets[a][next];
                heap.emplace(pt, ptid, a, next);
            }
        }
        return feed;
    }

    void follow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        following[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        auto it = following.find(followerId);
        if (it != following.end()) it->second.erase(followeeId);
    }

private:
    static constexpr int FEED_CAP = 10;
    std::unordered_map<int, std::vector<std::pair<int, int>>> tweets;
    std::unordered_map<int, std::unordered_set<int>> following;
    int ts = 0;
};

// LC 355. Design Twitter
// In-memory class with four operations. getNewsFeed runs a bounded
// k-way merge through a max-heap keyed on a monotonic timestamp.
// container/heap requires implementing heap.Interface (5 methods);
// flipping Less from < to > converts the default min-heap to a max-heap.
package main

import "container/heap"

const feedCap = 10

type tweet struct {
	ts      int
	tweetID int
}

type heapItem struct {
	ts       int
	tweetID  int
	authorID int
	idx      int
}

// Max-heap on ts: Less returns h[i].ts > h[j].ts.
type tweetHeap []heapItem

func (h tweetHeap) Len() int           { return len(h) }
func (h tweetHeap) Less(i, j int) bool { return h[i].ts > h[j].ts }
func (h tweetHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *tweetHeap) Push(x any)        { *h = append(*h, x.(heapItem)) }
func (h *tweetHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

type Twitter struct {
	tweets    map[int][]tweet
	following map[int]map[int]struct{}
	ts        int
}

func Constructor() Twitter {
	return Twitter{
		tweets:    make(map[int][]tweet),
		following: make(map[int]map[int]struct{}),
	}
}

func (t *Twitter) PostTweet(userID, tweetID int) {
	t.ts++
	t.tweets[userID] = append(t.tweets[userID], tweet{ts: t.ts, tweetID: tweetID})
}

func (t *Twitter) GetNewsFeed(userID int) []int {
	authors := map[int]struct{}{userID: {}}
	for a := range t.following[userID] {
		authors[a] = struct{}{}
	}
	h := &tweetHeap{}
	for a := range authors {
		tw := t.tweets[a]
		if len(tw) == 0 {
			continue
		}
		idx := len(tw) - 1
		heap.Push(h, heapItem{ts: tw[idx].ts, tweetID: tw[idx].tweetID, authorID: a, idx: idx})
	}
	feed := make([]int, 0, feedCap)
	for h.Len() > 0 && len(feed) < feedCap {
		top := heap.Pop(h).(heapItem)
		feed = append(feed, top.tweetID)
		if top.idx > 0 {
			next := top.idx - 1
			tw := t.tweets[top.authorID][next]
			heap.Push(h, heapItem{ts: tw.ts, tweetID: tw.tweetID, authorID: top.authorID, idx: next})
		}
	}
	return feed
}

func (t *Twitter) Follow(followerID, followeeID int) {
	if followerID == followeeID {
		return
	}
	if _, ok := t.following[followerID]; !ok {
		t.following[followerID] = make(map[int]struct{})
	}
	t.following[followerID][followeeID] = struct{}{}
}

func (t *Twitter) Unfollow(followerID, followeeID int) {
	if s, ok := t.following[followerID]; ok {
		delete(s, followeeID)
	}
}

The four-language drift is exactly what Heaps and priority queues prepared us for. Python's heapq is min-only, so we negate the timestamp on push and on pop. C++'s std::priority_queue is max-by-default and tuples compare lexicographically, so the leading ts field drives the order with no comparator. Java's PriorityQueue<int[]> needs an explicit Integer.compare(b[0], a[0]) to flip min into max, and the implementation allocates a fresh int[] on every push because mutating an array still inside the heap silently breaks the heap invariant. Go's container/heap requires the five-method heap.Interface and a Less returning > instead of <. Same algorithm, four languages of taxes.

Why heap size stays at k#

The lazy-push invariant is the part most candidates skip and the part the algorithm depends on. Seeding inserts exactly one entry per author. Every iteration of the main loop pops one entry and conditionally pushes one entry from the same author (the next-older tweet, if any). Net change per iteration: at most zero. So heap size is bounded by k for the whole life of the call.^[4:1]

The tempting alternative is to seed the heap with every tweet from every followee. Correctness still holds. But heap size becomes O(N) instead of O(k), and every push and pop pays log N instead of log k. On a user following 1,000 people who each posted 1,000 tweets, the difference is 20 vs 10 per heap operation, and we do those operations a million times during seeding alone. The lazy seed is what makes the algorithm sublinear in N.

A trace of the canonical input#

The arithmetic gets concrete on a small instance. Eight calls, the last of which is the news feed:

postTweet(1, 5)        # ts=1, tweets[1]=[(1,5)]
postTweet(1, 3)        # ts=2, tweets[1]=[(1,5),(2,3)]
follow(1, 2)
postTweet(2, 6)        # ts=3, tweets[2]=[(3,6)]
follow(1, 4)
postTweet(4, 9)        # ts=4, tweets[4]=[(4,9)]
postTweet(2, 7)        # ts=5, tweets[2]=[(3,6),(5,7)]
getNewsFeed(1)         # authors = {1, 2, 4}

Five tweets total in the feed. The output [7, 9, 6, 3, 5] is in ts-descending order: 5, 4, 3, 2, 1. The heap never holds more than three entries (one per author), and the algorithm visits exactly five postTweet records. No more than the answer's worth.

Every pop is paired with at most one push from the same author, keeping heap size bounded by |authors| for the duration of the call.

What it actually costs#

k = |followees(u)| + 1, F = 10 (the LC-fixed feed cap), n = total tweets stored across the class lifetime.

Two complexity claims need a one-line proof.

The getNewsFeed bound. Seeding scans k authors and pushes one entry each, costing O(k log k). The main loop runs at most F = 10 iterations; each iteration does one pop and at most one push, both O(log k) since the heap has at most k items. Total is O(k log k + F log k), which simplifies to O(k log k) because F is a fixed constant. CLRS Theorem 6.5 gives the per-operation O(log k) bound, and Exercise 6.5-9 establishes the O(n log k) total cost of full k-way merge. We pay the same per-operation cost but only F operations instead of n.^[4:2]

The postTweet amortization. Each call appends to a dynamic array. The doubling-on-overflow strategy charges O(1) to most appends and O(n) to the rare doubling event; CLRS §17.4 spreads the cost evenly across calls. The same argument we made for hash-map insert applies verbatim.^[3:1]

Where readers go wrong#

What this looks like at scale#

LC 355 is the read-merge core of Twitter's home-timeline service with the scale removed. The full production architecture isn't pull-only.

Krikorian's 2013 talk laid out the trade.^[2:2] Pure pull (the LC 355 model) makes postTweet cheap and getNewsFeed expensive, because every read does the k-way merge from scratch. Pure push, also called fan-out-on-write, inverts the trade. When a user posts, the system iterates their follower list and inserts the tweet into each follower's pre-computed home timeline. Reads become a single Redis range scan. The cost is write amplification proportional to follower count, which is fine for most users and catastrophic for celebrities. A Lady Gaga tweet at 31 million followers became 31 million Redis inserts.

Pure pull (LC 355) trades cheap writes for expensive reads; pure push trades cheap reads for unbounded write amplification on celebrities; the hybrid splits the workload by follower-count threshold and merges the two paths at read time.

The hybrid is what Twitter actually shipped. Non-celebrity tweets fan out at write time into per-follower Redis lists capped at 800 entries. Celebrity tweets skip fan-out and live in the author's own user-timeline list. getNewsFeed for any user merges their precomputed home timeline with on-demand reads of each followed celebrity's user-timeline, then sorts the combined result by timestamp and trims to the requested page size. The threshold is a tuning parameter, conventionally somewhere around 1 million followers.^[2:3]

Yao Yue's 2014 talk added the storage detail. Twitter's Timeline Service ran a forked Redis with two custom data types, Hybrid List (a linked list of fixed-size ziplists) and a custom BTree, sized to handle 30 million queries per second across roughly 6,000 instances and about 40 TB of allocated heap.^[5] The Hybrid List existed because vanilla Redis ziplists require an O(timeline size) memmove on every insert, which is fine at 50 entries and ruinous at 800; splitting the timeline into bounded ziplist nodes caps the memmove at the node size.

None of that scaling work changes the algorithm in getNewsFeed. The read-side merge is still a heap-based k-way merge of timestamp-sorted lists, just with two sources (precomputed timeline + celebrity pulls) instead of k sources, and with the heap living in a Redis-resident structure instead of a process-local one. The LC 355 algorithm is the algorithmic kernel that survives every scale-up.

Problem ladder#

CORE (solve all to claim chapter mastery)#

• LC 355 — Design Twitter [Medium] • k-way-merge-design ★
• LC 1797 — Design Authentication Manager [Medium] • ttl-design
• LC 1825 — Finding MK Average [Hard] • sliding-window-with-trimmed-mean

STRETCH (optional)#

• LC 1603 — Design Parking System [Easy] • counter-design
• LC 1622 — Fancy Sequence [Hard] • lazy-evaluation-design (LeetCode Premium)

The Twitter pattern admits no canonical Easy from inside the merge family. Strip out any of the four moving parts (constructor state, monotonic timestamp, follow set, feed merge) and the problem either collapses into a trivial counter or loses the timeline-merge teaching point. LC 1603 fills the Easy slot from an adjacent design pattern: a constructor with state, a counter check, a boolean return. Different algorithm, same class-shape discipline.

Where this leads#

The merge subroutine is taught in Heaps and priority queues, which has the full LC 23 walkthrough this chapter compresses into one section. The hash-map operations are taught in Hash maps and hash sets, which gives the chained-hash-table proof we relied on for the O(1) follow and unfollow bounds. For the production architecture itself (fan-out trade-offs, celebrity thresholds, multi-region replication of the timeline service), that's a system-design topic and lives outside this handbook's algorithmic core.

References#