[LeetCode] 355. Design Twitter

Table of Contents

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:

• Twitter() Initializes your twitter object.
• 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.
• 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.
• void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
• 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.

Approach

We use hash map data structures (implemented as JavaScript objects) to store user tweets and follow relationships. Each tweet is timestamped for ordering. To get a user’s news feed, we gather recent tweets from the user and their followees, then sort and return the most recent ones.

Ideally, retrieving the news feed can use a Min-max heap for better efficiency, but that would make the implementation more complex here.

Solution

var Twitter = function () {
  // Map from userId to list of tweets (each tweet has id and createdAt timestamp)
  this.tweetsMap = {};
  // Map from followerId to a set of followeeIds (users being followed)
  this.followMap = {};
  // Global timestamp to simulate tweet posting time, increments with each tweet
  this.timestamp = 0;
};

/**
 * Compose a new tweet
 * @param {number} userId - ID of the user posting the tweet
 * @param {number} tweetId - ID of the tweet
 * @return {void}
 */
Twitter.prototype.postTweet = function (userId, tweetId) {
  // Initialize tweet list for user if not present
  this.tweetsMap[userId] ||= [];

  // Add the new tweet with current timestamp
  this.tweetsMap[userId].push({
    id: tweetId,
    createdAt: this.timestamp++,
  });
};

/**
 * Retrieve the 10 most recent tweet IDs in the user's news feed.
 * News feed includes tweets by the user and those they follow.
 * @param {number} userId - ID of the user retrieving the news feed
 * @return {number[]} List of tweet IDs ordered from most recent to least recent
 */
Twitter.prototype.getNewsFeed = function (userId) {
  const RETRIEVE_TWEETS_LIMIT = 10;

  // Get list of users the user follows (empty if none)
  const followeeIds = this.followMap[userId] || [];

  // Combine tweets from followees and the user
  const tweets = [...followeeIds, userId]
    .reduce((acc, id) => {
      // If user has no tweets, skip
      if (!this.tweetsMap[id]) return acc;

      // Add up to the last RETRIEVE_TWEETS_LIMIT tweets from this user
      return [...acc, ...this.tweetsMap[id].slice(-RETRIEVE_TWEETS_LIMIT)];
    }, [])
    // Sort combined tweets by timestamp descending (newest first)
    .sort((a, b) => b.createdAt - a.createdAt)
    // Take only the most recent RETRIEVE_TWEETS_LIMIT tweets
    .slice(0, RETRIEVE_TWEETS_LIMIT);

  // Return only the tweet IDs
  return tweets.map(tweet => tweet.id);
};

/**
 * Follower follows a followee
 * @param {number} followerId - ID of the follower
 * @param {number} followeeId - ID of the user to be followed
 * @return {void}
 */
Twitter.prototype.follow = function (followerId, followeeId) {
  // Initialize followee set for follower if not present
  this.followMap[followerId] ||= new Set();

  // Add followee to follower's follow set
  this.followMap[followerId].add(followeeId);
};

/**
 * Follower unfollows a followee
 * @param {number} followerId - ID of the follower
 * @param {number} followeeId - ID of the user to be unfollowed
 * @return {void}
 */
Twitter.prototype.unfollow = function (followerId, followeeId) {
  // If follower has no followees, do nothing
  if (!this.followMap[followerId]) return;

  // Remove followee from follower's follow set
  this.followMap[followerId].delete(followeeId);
};

/**
 * Example usage:
 * var obj = new Twitter()
 * obj.postTweet(userId, tweetId)
 * var param_2 = obj.getNewsFeed(userId)
 * obj.follow(followerId, followeeId)
 * obj.unfollow(followerId, followeeId)
 */

Complexity Analysis

Time Complexity

• postTweet: $O(1)$
• follow / unfollow: $O(1)$
• getNewsFeed: $O(k \log k)$, where $k$ is the total number of tweets considered (at most 10 per followed user)

Space Complexity

• $O(n + t)$, where $n$ is the number of users and $t$ is the number of tweets.