algoadvance

Leetcode 355. Design Twitter

Problem Statement

Design a simplified version of Twitter where users can post tweets, follow/unfollow other users, and see the 10 most recent tweets in their news feed. Implement the Twitter class with the following methods:

  1. postTweet(int userId, int tweetId): Composes a new tweet.
  2. getNewsFeed(int userId): Retrieves the 10 most recent tweet ids in the user’s news feed. Each item in the news feed should be posted by users who the user follows or by the user themselves. Tweets must be ordered from most recent to least recent.
  3. follow(int followerId, int followeeId): The user follows another user.
  4. unfollow(int followerId, int followeeId): The user unfollows another user.

Clarifying Questions

  1. Is there a maximum number of users or tweets we should handle?
    • No limitations mentioned in the problem statement, assume the implementation should scale well.
  2. Should we handle edge cases like users following themselves or unfollowing non-followed users?
    • Yes, handle such edge cases gracefully.

Strategy

  1. Data Structures:
    • Use a hash map to store users’ tweets. The key will be the userId and the value will be a list of tweet IDs and timestamps.
    • Use another hash map to store the users’ following lists. The key will be the userId and the value will be a set containing userIds that the user follows.
    • Use global timestamp to keep track of the order of tweets.
  2. Methods:
    • postTweet: Append the tweet to the user’s list.
    • getNewsFeed: Gather tweets from the user and the users they follow, sort them by timestamp, and return the top 10.
    • follow: Add the followeeId to the followerId’s set.
    • unfollow: Remove the followeeId from the followerId’s set if present.
  3. Complexity:
    • postTweet: O(1)
    • getNewsFeed: O(F * T log T) where F is the number of followees and T is the number of tweets to consider for sorting.
    • follow/unfollow: O(1)

Code

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

class Twitter {
private:
    struct Tweet {
        int tweetId;
        int time;
    };
    
    unordered_map<int, deque<Tweet>> tweets;
    unordered_map<int, unordered_set<int>> followers;
    int timeCounter;

public:
    Twitter() {
        timeCounter = 0;
    }
    
    void postTweet(int userId, int tweetId) {
        if(tweets[userId].size() == 10) {
            tweets[userId].pop_front();
        }
        tweets[userId].push_back({tweetId, timeCounter++});
    }
    
    vector<int> getNewsFeed(int userId) {
        vector<Tweet> allTweets;
        
        // Get user's own tweets
        auto &userTweets = tweets[userId];
        allTweets.insert(allTweets.end(), userTweets.begin(), userTweets.end());
        
        // Get tweets from followees
        for (int followee : followers[userId]) {
            auto &followeeTweets = tweets[followee];
            allTweets.insert(allTweets.end(), followeeTweets.begin(), followeeTweets.end());
        }
        
        // Sort tweets by time (most recent first)
        sort(allTweets.begin(), allTweets.end(), [](Tweet &a, Tweet &b) {
            return a.time > b.time;
        });
        
        // Get the 10 most recent tweets
        vector<int> result;
        for (int i = 0; i < 10 && i < allTweets.size(); i++) {
            result.push_back(allTweets[i].tweetId);
        }
        
        return result;
    }
    
    void follow(int followerId, int followeeId) {
        if (followerId != followeeId) {
            followers[followerId].insert(followeeId);
        }
    }
    
    void unfollow(int followerId, int followeeId) {
        if (followers[followerId].find(followeeId) != followers[followerId].end()) {
            followers[followerId].erase(followeeId);
        }
    }
};

Time Complexity

By using these methods, we ensure that our Twitter simulation operates efficiently and follows the problem’s constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI