Design a Twitter feed (class level)

01The design, in the six-step framework

1. Requirements and use cases

This is LeetCode's Design Twitter, Google-tagged: a handful of methods where the interesting choice is how the feed is assembled. It tests data structures behind a small API more than classes.

• A user posts a tweet.
• A user follows and unfollows another user; following yourself is a no-op, and your own tweets are always in your feed.
• A user reads a news feed: the ten most recent tweets among themselves and their followees, newest first.
• Unfollowing removes that user's tweets from the next read.

Out of scope: retweets, ranking, media, and the distributed version, which is the news feed system design. Assumptions to state: a global sequence defines time; memory holds everything. Non-functional constraints: post is O(1); feed is O(f log f) with f followees, independent of how many tweets each has written, which is what distinguishes a good answer from sorting everything.

2. Core entities and relationships

• Tweet: an immutable id, author, text and sequence number.
• User: holds a list of own tweets, oldest first, and the set of followees.
• FeedBuilder: merges the followees' tweet lists with a heap.
• Twitter: the public API and the sequence counter.
• TimelineObserver: an optional listener for posts, used by a push-model cache.

A user composes their tweets: each tweet has one author and one list. Following is a many-to-many association stored as ids, never as object references, so an unfollow is one set removal and no user holds another in memory.

3. Interfaces and key methods

class Twitter:
    def post(self, user_id: int, text: str) -> Tweet:
        """Append to the author's list with the next sequence number. O(1)."""
    def follow(self, follower: int, followee: int) -> None:
        """Idempotent; following yourself is ignored."""
    def unfollow(self, follower: int, followee: int) -> None:
        """Idempotent; unfollowing a stranger does nothing."""
    def feed(self, user_id: int, k: int = 10) -> list[Tweet]:
        """k newest among the user and followees, newest first."""

class FeedBuilder:
    def latest(self, lists: list[list[Tweet]], k: int) -> list[Tweet]:
        """k-way merge from the tails of sorted lists; does not copy them."""

Invariants: each user's tweets is sorted by seq; seq is unique and strictly increasing across all users; a user is never in their own following; the feed contains no duplicates because each tweet lives in exactly one list.

4. Design patterns and the choices behind them

Merge at read time with a heap

Each user's tweets are already sorted, so the feed is a k-way merge: seed a heap with each list's newest tweet, pop the largest, and push that list's next-newest. Ten pops touch only O(f) entries plus ten more. Collecting everything and sorting is correct and is O(n log n) over all tweets by all followees, which is what the interviewer is waiting for you to avoid.

Fan-out on read, with a door left open

Reading is the expensive side here, and it makes follow and unfollow trivial, since the feed always reflects the current follow set. The push alternative precomputes each timeline at post time, and makes a celebrity post cost millions of writes. An observer on post is the seam where a push cache would attach, without changing the API. It is not built by default.

A global sequence rather than clocks

Two tweets in one millisecond need a defined order. A counter under Twitter gives one. This is a modelling decision worth saying aloud, and it is the kind of assumption the requirements walk should surface early.

Signature choices

follow and unfollow are idempotent and silent on unknown cases, which matches the original problem. Keeping the API forgiving here is deliberate: a repeated tap should not be an error. Users are created lazily on first mention to keep the four methods free of registration.

5. Core flow and code

1. post takes the next sequence number and appends a Tweet to the author's list, then notifies observers.
2. feed collects the lists of the user and everyone they follow.
3. FeedBuilder.latest pushes (negative seq, list index, position) for each non-empty list.
4. It pops k times; each pop emits a tweet and pushes the previous tweet in that list, if any.

from __future__ import annotations
import heapq, itertools, threading
from collections import defaultdict
from dataclasses import dataclass, field
from typing import Protocol


@dataclass(frozen=True)
class Tweet:
    id: int
    author: int
    text: str
    seq: int


@dataclass
class User:
    id: int
    tweets: list[Tweet] = field(default_factory=list)
    following: set[int] = field(default_factory=set)
    followers: set[int] = field(default_factory=set)


class TimelineObserver(Protocol):
    def on_post(self, tweet: Tweet, followers: set[int]) -> None: ...


class FeedBuilder:
    def latest(self, lists: list[list[Tweet]], k: int) -> list[Tweet]:
        heap: list[tuple[int, int, int]] = []
        for i, tweets in enumerate(lists):
            if tweets:
                last = len(tweets) - 1
                heap.append((-tweets[last].seq, i, last))
        heapq.heapify(heap)
        out: list[Tweet] = []
        while heap and len(out) < k:
            _, i, pos = heapq.heappop(heap)
            out.append(lists[i][pos])
            if pos > 0:
                heapq.heappush(heap, (-lists[i][pos - 1].seq, i, pos - 1))
        return out


class Twitter:
    def __init__(self) -> None:
        self.users: dict[int, User] = {}
        self.builder = FeedBuilder()
        self.observers: list[TimelineObserver] = []
        self._seq = itertools.count(1)
        self._ids = itertools.count(1)
        self.lock = threading.Lock()

    def _user(self, user_id: int) -> User:
        return self.users.setdefault(user_id, User(user_id))

    def post(self, user_id: int, text: str) -> Tweet:
        with self.lock:
            user = self._user(user_id)
            tweet = Tweet(next(self._ids), user_id, text, next(self._seq))
            user.tweets.append(tweet)
            followers = set(user.followers)
        for o in self.observers:
            o.on_post(tweet, followers)
        return tweet

    def follow(self, follower: int, followee: int) -> None:
        if follower == followee:
            return
        with self.lock:
            self._user(follower).following.add(followee)
            self._user(followee).followers.add(follower)

    def unfollow(self, follower: int, followee: int) -> None:
        with self.lock:
            self._user(follower).following.discard(followee)
            self._user(followee).followers.discard(follower)

    def feed(self, user_id: int, k: int = 10) -> list[Tweet]:
        with self.lock:
            user = self._user(user_id)
            ids = user.following | {user_id}
            lists = [self._user(i).tweets for i in ids]
            return self.builder.latest(lists, k)

6. Extensions, concurrency and what interviewers probe

• Complexity to quote: post O(1), follow O(1), feed O((f + k) log f) with heapify at O(f). The tweet history size never appears, and that sentence is the point of the question.
• Hybrid fan-out: push for ordinary users, merge at read for celebrities. Say the trade-off, then point at TimelineObserver as the hook, and at the system design note for the rest.
• Delete a tweet: a tombstone flag skipped in the merge is simpler than removing from the list, and it preserves positions. The loop then pops until k live tweets are found.
• Pagination: pass the last seen seq as a cursor; the merge starts from tweets below it, using a binary search in each list.
• Concurrency: one lock is fine for this size; lists are append-only, so a reader could safely work on a length snapshot if the lock became a bottleneck.
• Test first: a user's own tweets appear with no follows; unfollow removes that author's tweets at the next read; eleven tweets yield the ten newest in order; following yourself changes nothing; unfollowing a stranger does not raise.
• Common mistake: pushing tweets into a shared feed list per user, which makes unfollow need a filter and a rebuild.

02Where this question was reported

• LeetCode Discuss · LeetCode 355 (Medium), Google-tagged, freq 23.4
• devshreebharatia.substack.com · Listed among design-style LeetCode problems Google asks
• GitHub · Machine coding 'Design Twitter/X' (all companies)
• LeetCode Discuss · Named in Google LLD tips alongside external merge sort