355. Design Twitter – Leetcode Solutions

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]]

class Twitter:

    def __init__(self):
        # Dictionary to store all tweets per user: {userId: [(time, tweetId), ...]}
        self.tweets = defaultdict(list)
        # Dictionary to store following relationships: {followerId: {followeeId, ...}}
        self.following = defaultdict(set)
        # A timestamp to track the order of tweets
        self.time = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        # Add the tweet with a timestamp to the user's tweet list
        self.tweets[userId].append((self.time, tweetId))
        # Increment the timestamp for the next tweet
        self.time += 1

    def getNewsFeed(self, userId: int) -> list:
        # Min-heap to store the top 10 tweets by timestamp
        heap = []
        
        # Get the user's own tweets
        if userId in self.tweets:
            for tweet in self.tweets[userId]:
                heapq.heappush(heap, tweet)
                if len(heap) > 10:
                    heapq.heappop(heap)

        # Get the tweets from the users the current user follows
        for followeeId in self.following[userId]:
            if followeeId in self.tweets:
                for tweet in self.tweets[followeeId]:
                    heapq.heappush(heap, tweet)
                    if len(heap) > 10:
                        heapq.heappop(heap)
        
        # Extract tweets from the heap, ordered from most recent to oldest
        result = []
        while heap:
            result.append(heapq.heappop(heap)[1])
        
        # Return the result in reverse order since we want most recent first
        return result[::-1]

    def follow(self, followerId: int, followeeId: int) -> None:
        # A user cannot follow themselves, so only add if followerId != followeeId
        if followerId != followeeId:
            self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        # Remove followeeId from followerId's following list if it exists
        if followeeId in self.following[followerId]:
            self.following[followerId].remove(followeeId)

class Twitter {
    // A struct to represent each tweet with a unique ID and a timestamp for sorting
    struct Tweet {
        int tweetId;
        int timestamp;
        Tweet(int id, int time) : tweetId(id), timestamp(time) {}
    };

    // Keeps track of the timestamp of each tweet (incremental)
    int time;
    
    // Maps a userId to the list of their own tweets (deque is used for fast insertion/removal)
    unordered_map<int, deque<Tweet>> tweets;

    // Maps a userId to the set of userIds they are following
    unordered_map<int, unordered_set<int>> following;

public:
    // Constructor to initialize the Twitter object
    Twitter() {
        time = 0;
    }

    // Function to post a new tweet
    void postTweet(int userId, int tweetId) {
        // Add the tweet to the user's tweet list with the current timestamp
        tweets[userId].emplace_front(tweetId, time++);
        // Keep only the 10 most recent tweets to limit memory usage
        if (tweets[userId].size() > 10) {
            tweets[userId].pop_back();
        }
    }

    // Function to retrieve the 10 most recent tweets for a user's news feed
    vector<int> getNewsFeed(int userId) {
        vector<Tweet> feed;

        // Add the user's own tweets to the news feed
        if (tweets.count(userId)) {
            feed.insert(feed.end(), tweets[userId].begin(), tweets[userId].end());
        }

        // Add tweets from users that this user follows
        for (int followeeId : following[userId]) {
            if (tweets.count(followeeId)) {
                feed.insert(feed.end(), tweets[followeeId].begin(), tweets[followeeId].end());
            }
        }

        // Sort the feed by timestamp (most recent first)
        sort(feed.begin(), feed.end(), [](const Tweet& a, const Tweet& b) {
            return a.timestamp > b.timestamp;
        });

        // Collect the most recent 10 tweet IDs for the feed
        vector<int> result;
        for (int i = 0; i < min(10, (int)feed.size()); ++i) {
            result.push_back(feed[i].tweetId);
        }

        return result;
    }

    // Function to follow another user
    void follow(int followerId, int followeeId) {
        // A user cannot follow themselves
        if (followerId != followeeId) {
            following[followerId].insert(followeeId);
        }
    }

    // Function to unfollow another user
    void unfollow(int followerId, int followeeId) {
        // Remove the followeeId from the set of users that followerId is following
        following[followerId].erase(followeeId);
    }
};

var Twitter = function() {
    // Store user tweets: key is userId, value is an array of tweet objects with tweetId and timestamp
    this.tweets = new Map();
    
    // Store user following information: key is userId, value is a set of followeeIds
    this.following = new Map();
    
    // Global timestamp to simulate tweet posting order
    this.timestamp = 0;
};

/** 
 * @param {number} userId 
 * @param {number} tweetId
 * @return {void}
 */
Twitter.prototype.postTweet = function(userId, tweetId) {
    // If user doesn't have any tweets yet, initialize an array for their tweets
    if (!this.tweets.has(userId)) {
        this.tweets.set(userId, []);
    }
    // Add the new tweet with the tweetId and the current timestamp
    this.tweets.get(userId).push({ tweetId, time: this.timestamp });
    
    // Increment the global timestamp for next tweet
    this.timestamp++;
};

/** 
 * @param {number} userId
 * @return {number[]}
 */
Twitter.prototype.getNewsFeed = function(userId) {
    // Collect tweets from the user and the users they follow
    let feed = [];
    
    // Add user's own tweets to the feed
    if (this.tweets.has(userId)) {
        feed.push(...this.tweets.get(userId));
    }
    
    // Add tweets from followees to the feed
    if (this.following.has(userId)) {
        for (let followeeId of this.following.get(userId)) {
            if (this.tweets.has(followeeId)) {
                feed.push(...this.tweets.get(followeeId));
            }
        }
    }

    // Sort tweets by timestamp in descending order (most recent first)
    feed.sort((a, b) => b.time - a.time);
    
    // Return the 10 most recent tweet IDs
    return feed.slice(0, 10).map(tweet => tweet.tweetId);
};

/** 
 * @param {number} followerId 
 * @param {number} followeeId
 * @return {void}
 */
Twitter.prototype.follow = function(followerId, followeeId) {
    // If the follower isn't following anyone yet, initialize a set for them
    if (!this.following.has(followerId)) {
        this.following.set(followerId, new Set());
    }
    
    // Add followeeId to the follower's followee set
    this.following.get(followerId).add(followeeId);
};

/** 
 * @param {number} followerId 
 * @param {number} followeeId
 * @return {void}
 */
Twitter.prototype.unfollow = function(followerId, followeeId) {
    // If follower is following someone, and they follow the followeeId, remove the followeeId
    if (this.following.has(followerId)) {
        this.following.get(followerId).delete(followeeId);
    }
};

class Twitter {
    
    // A map to store the tweets of each user (userId -> List of tweetIds)
    private Map<Integer, List<Tweet>> userTweets;
    
    // A map to store the follow relationships (followerId -> Set of followeeIds)
    private Map<Integer, Set<Integer>> userFollows;
    
    // A timestamp to track the order of tweets globally
    private int timestamp;

    // Inner class to represent a tweet with its ID and timestamp
    private class Tweet {
        int tweetId;
        int time;
        
        Tweet(int tweetId, int time) {
            this.tweetId = tweetId;
            this.time = time;
        }
    }

    /** Initialize your Twitter object. */
    public Twitter() {
        userTweets = new HashMap<>();
        userFollows = new HashMap<>();
        timestamp = 0;
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        // Initialize user's tweet list if not already done
        if (!userTweets.containsKey(userId)) {
            userTweets.put(userId, new ArrayList<>());
        }
        
        // Add the new tweet to the user's list with a timestamp
        userTweets.get(userId).add(new Tweet(tweetId, timestamp++));
    }
    
    /** Retrieve the 10 most recent tweet IDs in the user's news feed. */
    public List<Integer> getNewsFeed(int userId) {
        // Create a priority queue to get the 10 most recent tweets
        PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.time - a.time);
        
        // Get the user's own tweets
        if (userTweets.containsKey(userId)) {
            pq.addAll(userTweets.get(userId));
        }
        
        // Get the tweets of users that this user follows
        if (userFollows.containsKey(userId)) {
            for (int followeeId : userFollows.get(userId)) {
                if (userTweets.containsKey(followeeId)) {
                    pq.addAll(userTweets.get(followeeId));
                }
            }
        }
        
        // Extract the 10 most recent tweets
        List<Integer> result = new ArrayList<>();
        int count = 0;
        while (!pq.isEmpty() && count < 10) {
            result.add(pq.poll().tweetId);
            count++;
        }
        
        return result;
    }
    
    /** Follow another user. */
    public void follow(int followerId, int followeeId) {
        // A user cannot follow themselves
        if (followerId == followeeId) return;
        
        // Initialize the follow set if not already done
        if (!userFollows.containsKey(followerId)) {
            userFollows.put(followerId, new HashSet<>());
        }
        
        // Add the followee to the follower's follow set
        userFollows.get(followerId).add(followeeId);
    }
    
    /** Unfollow another user. */
    public void unfollow(int followerId, int followeeId) {
        // If the follower doesn't follow anyone, no need to proceed
        if (!userFollows.containsKey(followerId)) return;
        
        // Remove the followee from the follower's follow set
        userFollows.get(followerId).remove(followeeId);
    }
}