Design Twitter

January 26, 2024

Problem Statement #

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

Functionalities: #

1. postTweet(userId, tweetId): Compose a new tweet.
2. getNewsFeed(userId): Retrieve the 10 most recent tweet IDs in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.
3. follow(followerId, followeeId): Follower follows a followee.
4. unfollow(followerId, followeeId): Follower unfollows a followee.

Solution Approach #

The solution involves using hashmaps to keep track of users’ tweets and their follow relationships. A heap (priority queue) can be used to retrieve the 10 most recent tweets.

Algorithm Steps #

1. Use a hashmap to store users’ tweets and a hashmap to store follow relationships.
2. For postTweet, add the tweet to the user’s list in the hashmap.
3. For getNewsFeed, use a heap to get the 10 most recent tweets from the user and their followees.
4. For follow and unfollow, update the follow relationships hashmap.

Code (Python) #

import heapq

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = {}
        self.followee = {}

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

    def getNewsFeed(self, userId):
        heap = []
        self.followee.setdefault(userId, set()).add(userId)
        for user in self.followee[userId]:
            if user in self.tweets:
                for tweet in self.tweets[user][:10]:
                    heapq.heappush(heap, tweet)

        news_feed = []
        while heap and len(news_feed) < 10:
            news_feed.append(heapq.heappop(heap)[1])
        return news_feed

    def follow(self, followerId, followeeId):
        self.followee.setdefault(followerId, set()).add(followeeId)

    def unfollow(self, followerId, followeeId):
        if followerId != followeeId and followeeId in self.followee.get(followerId, set()):
            self.followee[followerId].remove(followeeId)

# Test the class
twitter = Twitter()
twitter.postTweet(1, 5)
print(twitter.getNewsFeed(1))  # Output: [5]
twitter.follow(1, 2)
twitter.postTweet(2, 6)
print(twitter.getNewsFeed(1))  # Output: [6, 5]
twitter.unfollow(1, 2)
print(twitter.getNewsFeed(1))  # Output: [5]

Time Complexity #

• postTweet: O(1)
• getNewsFeed: O(N log N), where N is the total number of tweets by the user and their followees.
• follow, unfollow: O(1)

Space Complexity #

• Overall: O(U + T), where U is the number of users and T is the total number of tweets.