NUHMAN.com

📘 Problem Statement

Design a simplified version of Twitter where users can:

1. Post a tweet
2. Follow or unfollow other users
3. Retrieve the 10 most recent tweet IDs in the user's news feed (including their own tweets and those of people they follow)

🔧 Class Definition

python

class Twitter:

    def __init__(self):
        pass

    def postTweet(self, userId: int, tweetId: int) -> None:
        pass

    def getNewsFeed(self, userId: int) -> list[int]:
        pass

    def follow(self, followerId: int, followeeId: int) -> None:
        pass

    def unfollow(self, followerId: int, followeeId: int) -> None:
        pass

🧠 Core Concepts

• Use a timestamp to track tweet order.
• Use a min-heap (priority queue) to keep the top 10 tweets sorted by recency.
• Track:
• Tweets per user
• Follower-followee relationships

🐍 Python Code Implementation

python

import heapq
from collections import defaultdict

class Twitter:

    def __init__(self):
        self.timestamp = 0
        self.tweets = defaultdict(list)         # userId -> list of (timestamp, tweetId)
        self.following = defaultdict(set)       # userId -> set of followeeIds

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.timestamp, tweetId))
        self.timestamp -= 1                     # more recent tweets have smaller timestamps

    def getNewsFeed(self, userId: int) -> list[int]:
        heap = []

        # Add user's own tweets
        for t in self.tweets[userId][-10:]:
            heapq.heappush(heap, t)

        # Add followees' tweets
        for followeeId in self.following[userId]:
            if followeeId != userId:
                for t in self.tweets[followeeId][-10:]:
                    heapq.heappush(heap, t)

        # Get 10 most recent tweets
        return [tweetId for _, tweetId in heapq.nlargest(10, heap)]

    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)

🔍 Step-by-Step Breakdown

1. Posting a Tweet

• Add (timestamp, tweetId) to the user's tweet list.
• Use a decreasing timestamp (self.timestamp -= 1) to simulate ordering.

2. Getting News Feed

• Pull tweets from:
• The user
• The user's followees
• Push the latest tweets into a heap, then extract the top 10 most recent using heapq.nlargest.

3. Follow & Unfollow

• Use a set to maintain followees for fast lookup and update.

💡 Example

python

twitter = Twitter()
twitter.postTweet(1, 5)
twitter.getNewsFeed(1)           # [5]
twitter.follow(1, 2)
twitter.postTweet(2, 6)
twitter.getNewsFeed(1)           # [6, 5]
twitter.unfollow(1, 2)
twitter.getNewsFeed(1)           # [5]

⏱️ Time & Space Complexity

OperationComplexitypostTweetO(1)getNewsFeedO(N log K) where N = total tweets considered, K = 10follow/unfollowO(1)SpaceO(U + T) where U = users, T = tweets stored

🧵 Final Thoughts

This is a classic system design and OOP challenge that simulates a mini version of Twitter. It strengthens understanding of:

• Priority queues
• Custom data storage
• Efficient feed retrieval
• Scalable design patterns