Design Twitter

PracticeNeetCode ↗LeetCode ↗

Design a simplified social feed supporting: posting a tweet for a user, following/unfollowing another user, and fetching a user's news feed — the 10 most recent tweet ids from people they follow, including their own tweets, most recent first.

Example

Key Pointers

• Tweets need a global ordering across every user — a single increasing counter, used as a timestamp, does that without a real clock.
• Each user only ever needs their own tweets sorted by that timestamp, and a set of who they follow.
• Fetching a feed is really "merge the most recent tweets from a handful of sorted lists" — keeping only the last 10 tweets per candidate user before merging is enough, since older ones can never make the final top 10.

Step-by-Step Analysis

1. Maintain a global counter that increases with every posted tweet, used to order tweets across all users.
2. postTweet(userId, tweetId): append (time, tweetId) to that user's tweet list.
3. getNewsFeed(userId): gather the last 10 tweets from the user and everyone they follow, then take the 10 most recent overall.
4. follow / unfollow: add or remove the followee from the follower's set (guarding against following yourself).

Complexity

Time: O(1) for post/follow/unfollow, O(F · log 10) for getNewsFeed where F is the number of followees — Space: O(n)

Code

import heapq
from collections import defaultdict

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

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

    def getNewsFeed(self, userId: int) -> list[int]:
        candidates = []
        for uid in self.follows[userId] | {userId}:
            candidates.extend(self.tweets[uid][-10:])

        top = heapq.nlargest(10, candidates)
        return [tweetId for _, tweetId in top]

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

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.follows[followerId].discard(followeeId)

Code Explanation

How the solution above works, piece by piece.

1. time is a global counter; each tweet is stored as (time, tweetId) so newer tweets compare larger.
2. tweets[user] is that user's list in posting order; follows[user] is a set of followees.
3. getNewsFeed: for the user and everyone they follow, take at most the last 10 tweets, then heapq.nlargest(10, …) picks the 10 most recent overall.
4. follow ignores following yourself; unfollow uses discard, so unfollowing someone you don't follow is harmless.
5. A feed costs O(F · 10 · log 10) for F followees; posting, following and unfollowing are O(1).

Visual Walkthrough

Running postTweet(1, 5) then getNewsFeed(1):

Video Explanation

NeetCode — Design Twitter, LeetCode 355