Skip to main content
CodeEasy v0.1

Design Twitter

Medium Subject: Design
Time Complexity
O(N log N) for feed
Space Complexity
O(U + T)

Problem Description

Problem Statement

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and see the 10 most recent tweets in the user's news feed.

Example 1:

  • Input: ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]\n[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
  • Output: [null, null, [5], null, null, [6, 5], null, [5]]

Optimal Solution

Python

Approach: Hash Maps + Heap

Maintain a map of users to their set of followees, and a map of users to a list of their tweets (with a global timestamp). For getNewsFeed, gather the tweets from the user and all followees, and use a max-heap (or min-heap of size 10) to extract the 10 most recent.

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

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.time, tweetId))
        self.time -= 1 # Use negative time for max-heap simulation later or standard sorting

    def getNewsFeed(self, userId: int) -> List[int]:
        feed = list(self.tweets[userId])
        for followee in self.following[userId]:
            feed.extend(self.tweets[followee])

        feed.sort(key=lambda x: x[0]) # Sort by time ascending (since time is negative)
        return [tweet_id for _, tweet_id in feed[:10]]

    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.following[followerId]:
            self.following[followerId].remove(followeeId)