How do you approach Design Twitter?

Per-user maintain a list of (timestamp, tweetId). Increment a global tick on each postTweet.

What is the time complexity of Design Twitter?

Time complexity: O(1) for post / follow / unfollow; O(k log k) for getNewsFeed where k is followee count.. Space complexity: O(T + U^2) worst case (all users follow all users); typically O(T + F) with F = total follow edges..

What are common mistakes on Design Twitter?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

gitGood.dev

← Back to problems

Design Twitter

HardSystem Design

Description

Design a simplified Twitter where users can post tweets, follow / unfollow other users, and read the 10 most recent tweets in their news feed.

Operations:

postTweet(userId, tweetId): composes a new tweet with id tweetId by user userId. Each call uses a unique tweetId.
getNewsFeed(userId): retrieve the 10 most recent tweet ids in the user's news feed. Each item must be posted by users the user follows or by the user themself. Tweets must be ordered from most recent to least recent.
follow(followerId, followeeId): followerId follows followeeId.
unfollow(followerId, followeeId): followerId unfollows followeeId. (No-op if not currently following or if unfollowing self.)

For the auto-grader: implement twitterOps(operations). Each op is:

["postTweet", userId, tweetId] → null
["getNewsFeed", userId] → number[] (ids, most recent first, up to 10)
["follow", followerId, followeeId] → null
["unfollow", followerId, followeeId] → null

Example 1

Input: operations = [["postTweet",1,5],["getNewsFeed",1],["follow",1,2],["postTweet",2,6],["getNewsFeed",1],["unfollow",1,2],["getNewsFeed",1]]

Output: [null,[5],null,null,[6,5],null,[5]]

Explanation: After user 1 follows user 2 and user 2 posts tweet 6, user 1's feed is [6, 5]. After unfollow, user 1 only sees their own tweet [5].

Constraints

- 1 <= userId, followerId, followeeId <= 500 - 0 <= tweetId <= 10^4 - All tweetIds within a single test are unique. - 1 <= operations.length <= 3 * 10^4 - Tweets are inserted in the order operations appear; treat each postTweet as one logical timestamp tick.

Design Twitter: approach, complexity and pitfalls

A hard design problem, graded against 5 test cases (2 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

If you are stuck

Show the 3-step hint ladder

Per-user maintain a list of (timestamp, tweetId). Increment a global tick on each postTweet.
For getNewsFeed, k-way merge the most-recent tail of each followed user's tweet list using a max-heap by timestamp - take the top 10.
Don't forget the user follows themself implicitly (their own tweets are in their feed).

The optimal approach

Show the approach: Per-user Tweet Lists + K-Way Merge

State per user:

- `tweets`: array of `(timestamp, tweetId)`, append-only.

- `following`: `Set<userId>`.

`postTweet`: `tweets[userId].push((globalTick++, tweetId))` in O(1).

`getNewsFeed(userId)`: collect the followed-set ∪ {userId}. For each one, take the *last* entry of their tweets list (the most recent). Push those into a max-heap keyed by timestamp. Pop 10 times; each pop, push the next-older entry from the same user. This is the k-way merge of sorted lists. With k followees and limit 10, the cost is `O((k + 10) log k)` ≈ `O(k log k)` per feed read.

`follow / unfollow`: hash-set operations, O(1).

Why heap-on-read instead of fanout-on-write? With this small problem we don't have to push tweets into followers' inboxes at write time. In a real system, fanout-on-write trades higher write cost for O(1) reads; fanout-on-read (this approach) trades the opposite. Twitter uses a hybrid: fanout-on-write for normal users, fanout-on-read for celebs (so a tweet from a 100M-follower account doesn't trigger 100M writes).

Time: O(1) for post / follow / unfollow; O(k log k) for getNewsFeed where k is followee count.
Space: O(T + U^2) worst case (all users follow all users); typically O(T + F) with F = total follow edges.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.