Medium — Hash Table | Design | Heap | Object Oriented Design

The Problem

Design a simplified Twitter system that supports posting tweets, following/unfollowing users, and retrieving a user’s news feed containing the 10 most recent tweets from themselves and people they follow.

Approach

Use hash maps to store user tweets and follower relationships, with a global timestamp to order tweets chronologically. For news feed retrieval, collect tweets from the user and all followees, then sort by timestamp and return the 10 most recent.

Time: O(N log N) for getNewsFeed where N is total tweets from user and followees, O(1) for other operations · Space: O(U + T + F) where U is users, T is total tweets, and F is total follow relationships

Code

import heapq

class Tweet:
    def __init__(self, tweet_id, timestamp):
        self.tweet_id = tweet_id
        self.timestamp = timestamp

class Twitter:
    def __init__(self):
        self.user_tweets = {}  # User ID -> List of Tweet objects
        self.user_followees = {}  # User ID -> Set of followees
        self.timestamp = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.timestamp += 1
        if userId not in self.user_tweets:
            self.user_tweets[userId] = []
        self.user_tweets[userId].append(Tweet(tweetId, self.timestamp))

    def getNewsFeed(self, userId: int) -> List[int]:
        tweets = []

        if userId in self.user_tweets:
            tweets.extend(self.user_tweets[userId])

        if userId in self.user_followees:
            for followee in self.user_followees[userId]:
                if followee in self.user_tweets:
                    tweets.extend(self.user_tweets[followee])

        tweets.sort(key=lambda x: x.timestamp, reverse=True)
        return [tweet.tweet_id for tweet in tweets[:10]]

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

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

# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment