4.17.6 — Design Twitter

LeetCode 355 · Medium

The problem

Implement four operations:

• postTweet(userId, tweetId)
• getNewsFeed(userId) — the 10 most recent tweets from the user and everyone they follow, newest first
• follow(followerId, followeeId)
• unfollow(followerId, followeeId)

The pattern

getNewsFeed is the only interesting operation, and it is a k-way merge: each followed user has their own list of tweets already in time order, and you want the 10 newest across all of them.

That is 4.9.10 Merge K Sorted Lists with an early stop after 10 items. A max-heap of one candidate per user gives the newest in O(\log k), and you repeat 10 times.

The other three operations are bookkeeping over two hash maps.

The state

• tweets: user → list of (timestamp, tweetId), appended to, so already in time order.
• following: user → set of the users they follow.
• A single global counter for timestamps.

A global counter, not a wall clock. Two tweets in the same millisecond must still have a definite order, and a monotonically increasing integer guarantees that with no ties. This is the same reasoning behind logical clocks in distributed systems (Chapter 10.3), where wall-clock time is unreliable across machines.

The solution

Python

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)       # user → [(time, tweetId)]
        self.following = defaultdict(set)     # user → set of followees

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

    def getNewsFeed(self, userId: int) -> List[int]:
        heap = []
        users = self.following[userId] | {userId}          # include yourself

        for u in users:
            if self.tweets[u]:
                index = len(self.tweets[u]) - 1            # newest for this user
                t, tid = self.tweets[u][index]
                heapq.heappush(heap, (-t, tid, u, index))  # negate for a max-heap

        feed = []
        while heap and len(feed) < 10:
            t, tid, u, index = heapq.heappop(heap)
            feed.append(tid)
            if index > 0:                                  # this user has an older one
                index -= 1
                nt, ntid = self.tweets[u][index]
                heapq.heappush(heap, (-nt, ntid, u, index))

        return feed

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

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)     # no error if absent

TypeScript

class Twitter {
  private time = 0;
  private tweets = new Map<number, Array<[number, number]>>();
  private following = new Map<number, Set<number>>();

  postTweet(userId: number, tweetId: number): void {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId)!.push([++this.time, tweetId]);
  }

  getNewsFeed(userId: number): number[] {
    const users = new Set(this.following.get(userId) ?? []);
    users.add(userId);

    const heap = new MaxHeap<[number, number, number, number]>((a) => a[0]);
    for (const u of users) {
      const list = this.tweets.get(u);
      if (list?.length) {
        const i = list.length - 1;
        heap.push([list[i][0], list[i][1], u, i]);
      }
    }

    const feed: number[] = [];
    while (heap.size && feed.length < 10) {
      const [, tid, u, i] = heap.pop()!;
      feed.push(tid);
      if (i > 0) {
        const list = this.tweets.get(u)!;
        heap.push([list[i - 1][0], list[i - 1][1], u, i - 1]);
      }
    }

    return feed;
  }

  follow(a: number, b: number): void {
    if (a === b) return;
    if (!this.following.has(a)) this.following.set(a, new Set());
    this.following.get(a)!.add(b);
  }

  unfollow(a: number, b: number): void {
    this.following.get(a)?.delete(b);
  }
}

Four details worth naming.

Include yourself in the feed. Your own tweets appear, and you do not follow yourself. following[userId] | {userId} handles it in one expression.

Push only one tweet per user initially, then push that user's next-older tweet each time one of theirs is taken. That keeps the heap at size k rather than holding every tweet, which is the whole point of a k-way merge.

Carry the index in the heap entry so you know where to continue in that user's list.

A set for followees, so follow is idempotent — following twice does nothing — and unfollow with discard does not raise when the user was not followed.

Complexity

• postTweet — O(1).
• follow and unfollow — O(1).
• getNewsFeed — O(k + 10 \log k) for k followees: build the heap, then pop ten times.

Space is O(\text{total tweets} + \text{total follow edges}).

What a real system does differently

This is worth a sentence in an interview, because the naive design has a real failure mode.

Pull (what this code does): build the feed at read time by merging the followees' tweets. Writes are cheap, reads are expensive, and a user following 10,000 accounts makes every feed load slow.

Push (fan-out on write): when someone tweets, copy the tweet into a precomputed feed for each follower. Reads become a single lookup. But a celebrity with 50 million followers triggers 50 million writes for one tweet.

The real answer is a hybrid. Fan out on write for ordinary users, and merge in celebrity tweets at read time. That is exactly what large systems do, and Chapter 11.8 builds the news feed properly.

Saying "pull is O(k) per read, push is O(\text{followers}) per write, so production uses a hybrid" turns this from a coding exercise into a design answer.

Where this goes next

• Merge K Sorted Lists — the same k-way merge without the early stop. 4.9.10.
• Design a news feed — Chapter 11.8.
• Any "most recent N across many sources" — log aggregation, notification centres, activity streams.

What the interviewer will push on

"Why a heap and not just sorting everything?" Sorting all tweets from all followees is O(m \log m) for m total tweets; the heap gives the top 10 in O(k + 10\log k).

"Why a global counter instead of a timestamp?" Ties. Two tweets in the same instant still need a definite order.

"What if a user follows 100,000 people?" The heap build is O(k) per read, which is the pull model's weakness. Mention fan-out on write.

"What if a user has millions of followers?" Fan-out on write becomes the weakness. Hence the hybrid.

"Do you include the user's own tweets?" Yes, and it is easy to forget.

One thing to volunteer: name the read-versus-write trade unprompted. It costs one sentence and it is the difference between an exercise answer and a design answer.

Next: 4.17.7 Find Median from Data Stream — two heaps facing each other, and the cleverest use of the structure in the set.