Design Twitter · DSA Prep

This is a data-structure design problem: the algorithmic core is “merge several already-time-ordered lists (one per followed user) and take the top 10” — precisely the classic k-way merge, for which a heap is the standard tool. The design choice that matters is where to put the heap: at every getNewsFeed call (cheap writes, heavier reads) versus at every postTweet call (cheap reads, heavier writes). This solution takes the first approach, which fits Twitter’s actual read/write ratio (most tweets are read far more often than posted).

Per-User Tweet Lists + Merge on Read

OptimalTime postTweet O(1), follow/unfollow O(1), getNewsFeed O(F log F) for F followeesSpace O(T + U) for T tweets, U follow edges

Give every user their own list of (timestamp, tweetId) pairs, appended to on every post — a global counter that only decreases gives us a strictly-decreasing timestamp, so “most recent” always means “numerically largest.” A set per user tracks who they follow.

To build a news feed: gather the last 10 tweets from the caller and each user they follow (no user can contribute more than 10 to a top-10 result, so trimming each list to its own last 10 bounds the merge size), then merge those short lists and keep the top 10 overall. A heap keeps that merge to O(log F) per element instead of re-sorting everything.

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)     # userId -> [(time, tweetId), ...]
        self.following = defaultdict(set)   # userId -> set of followeeIds

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.time, tweetId))
        self.time -= 1  # decreasing "clock" so smaller = more recent

    def getNewsFeed(self, userId: int) -> list[int]:
        heap = []
        candidates = self.following[userId] | {userId}
        for uid in candidates:
            for t, tid in self.tweets[uid][-10:]:
                heap.append((t, tid))
        return [tid for _, tid in heapq.nsmallest(10, heap)]

    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)

Trace the example operations (trace data lives in this problem folder’s data.ts). Watch three things: each post landing in exactly one user’s timeline, the follow edge changing who is allowed into the merge, and the feed filling newest-first because the smallest clock value always wins:

initclock → next tweet t = 0user 1 feed set = {1}

follow graph · an arrow means the left user follows the right user

1user 1self2user 2

per-user tweet lists · appended on every post, oldest first

user 1no tweets yet

user 2no tweets yet

news feed · built per getNewsFeed call, newest first

slot 1 newest → slot 10 oldest

1–

2–

3–

4–

5–

6–

7–

8–

9–

10–

1 / 10

tweet in a timeline→follow linkfeed candidatenewest picked

init: Twitter starts with no tweets and no follow edges. The only state is a global clock at 0, one append-only list of (t, tweetId) pairs per user, and one follow set per user. The feed is never stored — every getNewsFeed call rebuilds it from these lists, so everything shown here is the whole data structure.

The three feeds — [5], [6, 5], [5] — match the example output exactly.

Correctness: using a monotonically decreasing counter as the timestamp guarantees a strict, collision-free recency ordering regardless of how many tweets exist — sorting ascending by this value is equivalent to sorting by “most recent first.” Capping each contributing user’s tweets to their last 10 before merging is safe because no single user can ever supply more than 10 tweets to a top-10 result.

Complexity: postTweet, follow, and unfollow are O(1). getNewsFeed gathers up to 10 tweets from each of F followees (plus self), so O(F log F) to heapify and extract the top 10 (or O(10F) with a simpler sort-and-slice, since 10 is a constant, whichever framing you prefer — either is effectively linear in the number of followees). Space is O(T) for all stored tweets plus O(U) for the follow graph.

Alternative worth naming in an interview: if getNewsFeed were called far more often relative to postTweet — or if celebrities with huge follower counts made “fan out on write” (push every new tweet directly into every follower’s precomputed feed) too expensive — this read-time merge is the better trade-off, since posting stays O(1) no matter how many followers a user has.