355. Design Twitter

355

MediumData Structure DesignHash maps + heap (k-way merge)Timestamped feed merge

Design Twitter

Design a simplified Twitter. Support postTweet(userId, tweetId) to publish a tweet; getNewsFeed(userId) to return the ids of the 10 most recent tweets in the user's feed, newest first, where the feed includes the user's own tweets and tweets from everyone they follow; follow(followerId, followeeId) and unfollow(followerId, followeeId) to manage the follow graph. A user does not follow themselves.

Open official problem prompt ↗

In plain English

Return each user's 10 newest tweets across themselves and everyone they follow, staying correct as follows change over time.

Picture it like this

Like assembling a newspaper front page from several reporters' inboxes: each story is timestamped, and you print the 10 latest across all inboxes you subscribe to.

Example

Input: postTweet(1,5); getNewsFeed(1); follow(1,2); postTweet(2,6); getNewsFeed(1); unfollow(1,2); getNewsFeed(1)
Output: [5]; [6, 5]; [5]
Why: After following user 2, user 1's feed merges tweet 6 (newer) then 5; after unfollowing, only user 1's own tweet 5 remains.

Constraints

1 <= userId, tweetId, followerId, followeeId <= 500tweetId values are unique per postTweet callAt most 3 * 10^4 total calls across all methodsA feed returns at most 10 tweets

Pattern lesson

See the pattern, then code

Timestamped feed merge

↗

Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. Stamp every tweet with a monotonically increasing global time so 'most recent' becomes 'largest timestamp'; the feed is then the 10 largest-timestamped tweets across the user and their followees.

New words, made simpleKnow these before the algorithm

Follow graph: Who follows whom, stored as a set of followees per user.
Global timestamp: An ever-increasing counter that orders all tweets across all users.
k-way merge: Combining several sorted lists into one ordered result, here via a heap.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Store tweets with real times and re-sort each feed

Works but sorts far more than the 10 tweets actually needed.

Collect all relevant tweets and fully sort them by time on every getNewsFeed.

Time O(T log T) per feedSpace O(U + T)

Best choiceGlobal timestamp + top-10 selection

Only the 10 newest are extracted, and posting/following stay O(1).

Stamp tweets with a global counter and use a heap to pull only the 10 newest candidates.

Time O(T log 10) per feedSpace O(U + T)

The rule we keep true

Invariant

The global time counter is strictly increasing, so a larger timestamp always means a strictly more recent tweet across the entire system.

Why this is correct

Reasoning

Because the feed set is exactly {the user} union {their followees}, and every tweet carries a unique increasing timestamp, selecting the 10 largest timestamps among those users' tweets yields precisely the 10 most recent feed tweets in order.

The algorithm in three movesSay these aloud before coding

1Keep a global counter and append (time, tweetId) to the poster's tweet list on each postTweet

time = 2

2Store the follow graph as userId -> set of followees

following[1] = {2}

3For a feed, gather candidate tweets from the user plus each followee

candidates = [(0,5),(1,6)] -> top [6,5]

4Take the 10 with the largest timestamps and return their ids newest first

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

u1:(0,5)0

u2:(1,6)1

feed:[6,5]2

1 · Readuser 1 posts 5

2 · Askrecord where?

3 · Update statetweets[1]=[(0,5)], time=1

4 · Resultstored

Key takeaway

User 1's feed merges its own tweet 5 with followee 2's newer tweet 6.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-8State
A global time counter, per-user tweet lists, and the follow graph as sets.
2
Lines 10-12postTweet
Append the timestamped tweet and advance the global clock so ordering stays total.
3
Lines 14-20getNewsFeed
Union the user with their followees, gather candidate tweets, and take the 10 largest timestamps.
4
Lines 22-26follow / unfollow
Set add and discard keep the graph correct; discard is safe even if the edge is absent.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A user with no tweets and no followees returns an empty feed
Fewer than 10 total tweets returns all of them
Unfollowing an edge that was never followed is a no-op
The user's own tweets always appear even with zero follows

Common beginner mistakes

Accidentally letting a user follow themselves and double-counting their tweets
Ordering the feed oldest-first instead of newest-first
Returning (time, id) pairs instead of just tweet ids
Rebuilding or sorting all tweets when only the top 10 are required

Check your understanding

Why is a per-tweet global timestamp better than storing wall-clock time or per-user counters?

PyPython 3 · solution.py

Optimal

1import heapq2from collections import defaultdict34class Twitter:5    def __init__(self):6        self.time = 07        self.tweets: dict[int, list] = defaultdict(list)8        self.following: dict[int, set] = defaultdict(set)910    def postTweet(self, userId: int, tweetId: int) -> None:11        self.tweets[userId].append((self.time, tweetId))12        self.time += 11314    def getNewsFeed(self, userId: int) -> list[int]:15        users = self.following[userId] | {userId}16        candidates = []17        for u in users:18            candidates.extend(self.tweets[u])19        top = heapq.nlargest(10, candidates, key=lambda x: x[0])20        return [tid for _, tid in top]2122    def follow(self, followerId: int, followeeId: int) -> None:23        self.following[followerId].add(followeeId)2425    def unfollow(self, followerId: int, followeeId: int) -> None:26        self.following[followerId].discard(followeeId)

Time complexitypostTweet/follow/unfollow O(1); getNewsFeed O(T log 10) where T is total candidate tweetsOptimized

Space complexityO(U + T) for users, follows, and tweetsExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonTwitterMicrosoftBloomberg

Design Twitter

Design Twitter

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Data Structure Design