Skip to content

355. Design Twitter

Hard

Description

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

Implement the Twitter class:

  1. Twitter()

    Initializes your twitter object.

  2. void postTweet(int userId, int tweetId)

    Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.

  3. List<Integer> getNewsFeed(int userId)

    Retrieves 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.

  4. void follow(int followerId, int followeeId)

    The user with ID followerId started following the user with ID followeeId.

  5. void unfollow(int followerId, int followeeId)

    The user with ID followerId started unfollowing the user with ID followeeId.

Example 1:

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

Explanation
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> [5]. return [5]
twitter.follow(1, 2);    // User 1 follows user 2.
twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.unfollow(1, 2);  // User 1 unfollows user 2.
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.

Constraints:

  • 1 <= userId, followerId, followeeId <= 500
  • 0 <= tweetId <= 10โด
  • All the tweets have unique IDs.
  • At most 3 * 10โด calls will be made to postTweet, getNewsFeed, follow, and unfollow.
  • A user cannot follow himself.

Solutions ๐Ÿ”’

Video Solution Coming Soon

Approach : Heap (Priority Queue)

Time complexity: \(O(n \log k)\), where \(n =|\text tweetsโˆฃ\) and \(k = (min(10,โˆฃ\text tweetsโˆฃ))\)

Space complexity: \(O(n + m)\)

Algorithm

  • The Twitter class needs to handle posting tweets, following/unfollowing users, and retrieving the 10 most recent tweets in a user's news feed.
  • We use a counter to assign a unique, decrementing timestamp to each tweet, which helps in sorting tweets by recency.
  • Tweets are stored in a deque for each user, allowing efficient addition to the front and removal from the back when more than 10 tweets are present.
  • Follow relationships are managed using sets to ensure that each user follows another user uniquely and efficiently check follow status.
  • To retrieve the news feed, we gather all tweets from the user and their followees, merge these sorted lists using a heap, and then extract the top 10 tweets.
import itertools
import collections
import heapq

class Twitter:
    def __init__(self):
        self.timer = itertools.count(step=-1)                       # Initialize a counter that starts at 0 and increments by -1 each time (to simulate time)
        self.tweets = collections.defaultdict(deque)                # Store tweets in a deque to maintain order and limit to 10 tweets per user
        self.followees = collections.defaultdict(set)               # Store follow relationships in a set for each user

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].appendleft((next(self.timer), tweetId)) # Record the tweet with a timestamp and tweetId
        if len(self.tweets[userId]) > 10:                           # Ensure only the last 10 tweets are kept
            self.tweets[userId].pop()

    def getNewsFeed(self, userId: int) -> list[int]:
        tweets = []                                                 # Collect all tweets from the user and their followees
        for followee in self.followees[userId] | {userId}:
            tweets.append(self.tweets[followee])
        merged*tweets = heapq.merge(*tweets)                        # Merge the sorted deques into a single sorted iterator
        return [tweetId for *, tweetId in list(merged_tweets)[:10]] # Return the last 10 tweetIds from the merged sorted iterator


    def follow(self, followerId: int, followeeId: int) -> None:
        self.followees[followerId].add(followeeId)                  # Add followeeId to the set of users that followerId is following

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.followees[followerId].discard(followeeId)              # Remove followeeId from the set of users that followerId is following

# 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)
equivalency 
def getNewsFeed(self, userId: int) -> list[int]:
    tweets = []
    for followee in self.followees[userId] | {userId}:
        tweets.append(self.tweets[followee])
    merged_tweets = heapq.merge(*tweets)
    return [tweetId for _ , tweetId in list(merged_tweets)[:10]]

                ||
                ||
                ||

def getNewsFeed(self, userId: int) -> list[int]:
    tweets = [self.tweets[followee] for followee in self.followees[userId] | {userId}]
    merged_tweets = heapq.merge(*tweets)
    return [tweetId for _ , tweetId in list(merged_tweets)[:10]]

                ||
                ||
                ||

def getNewsFeed(self, userId: int) -> list[int]:
    tweets = list(heapq.merge(*(self.tweets[followee] for followee in self.followees[userId] | {userId})))
    return [tweetId for _ , tweetId in tweets[:10]]

Complexity Discussion

  • Time: The time complexity for each operation is as follows:

    • postTweet: O(1) because appending to the front of a deque and potentially removing an element from the back are both O(1) operations.
    • getNewsFeed: O(n log k) where n is the total number of tweets from the user and their followees, and k is the number of users being followed plus one (the user themselves).This is because merging k sorted lists takes O(n log k) time using a min-heap.
    • follow: O(1) because adding an element to a set is an average O(1) operation.
    • unfollow: O(1) because removing an element from a set is an average O(1) operation.

  • Space: The space complexity is O(n + m) where n is the total number of tweets stored across all users (each user stores up to 10 tweets) and m is the total number of follow relationships stored (each relationship is stored once in the appropriate set).

    • O(n) for storing tweets, with each user having a deque that holds up to 10 tweets.
    • O(m) for storing follow relationships, with each user having a set of followees.
Akhil Singh Chauhan Akhil Singh Chauhan
Creator

Comments