Question

Formatted question description: https://leetcode.ca/all/355.html

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.

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.

Algorithm

We need to do it with two hash tables,

The first is to establish a mapping between the user and all his friends,
The other is to establish a mapping between users and all their tweet.

Since getting new things needs to be arranged in chronological order, then we can use an integer variable cnt to simulate the time point. Each time a message is sent, cnt increments by 1, then we know that the cnt is the most recent one.

When we establish the mapping between the user and all its tweet, we also need to establish the mapping between each message and its time point cnt.

The main difficulty of this question is to implement the getNewsFeed() function. This function gets the last 10 tweet of yourself and your friends. Our approach is that the user also adds to his friends list, and then traverses all of the user’s friends, traversing each tweet of friends maintain a hash table (or heap) of size 10,

If the newly traversed message is later than the earliest message in the hash table, then add this message, and then delete the oldest message, so that we can find the last 10 tweet.

Code

class Twitter {
    private Map<Integer, List<Integer>> userTweets;
    private Map<Integer, Set<Integer>> userFollowing;
    private Map<Integer, Integer> tweets;
    private int time;

    /** Initialize your data structure here. */
    public Twitter() {
        userTweets = new HashMap<>();
        userFollowing = new HashMap<>();
        tweets = new HashMap<>();
        time = 0;
    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        userTweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(tweetId);
        tweets.put(tweetId, ++time);
    }

    /**
     * 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 herself. Tweets must be ordered
     * from most recent to least recent.
     */
    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> following = userFollowing.getOrDefault(userId, new HashSet<>());
        Set<Integer> users = new HashSet<>(following);
        users.add(userId);
        PriorityQueue<Integer> pq
            = new PriorityQueue<>(10, (a, b) -> (tweets.get(b) - tweets.get(a)));
        for (Integer u : users) {
            List<Integer> userTweet = userTweets.get(u);
            if (userTweet != null && !userTweet.isEmpty()) {
                for (int i = userTweet.size() - 1, k = 10; i >= 0 && k > 0; --i, --k) {
                    pq.offer(userTweet.get(i));
                }
            }
        }
        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty() && res.size() < 10) {
            res.add(pq.poll());
        }
        return res;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        userFollowing.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        userFollowing.computeIfAbsent(followerId, k -> new HashSet<>()).remove(followeeId);
    }
}

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId);
 * List<Integer> param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId);
 * obj.unfollow(followerId,followeeId);
 */

//////////////////

public class Design_Twitter {
    class Twitter {
        Map<Integer, Set<Integer>> userToFollowingsMap; // user to who he/she is following
        Map<Integer, PriorityQueue<Tweet>> userToTweetsMap;
        SeqTime seqTime;

        /** Initialize your data structure here. */
        public Twitter() {
            userToFollowingsMap = new HashMap<>();
            userToTweetsMap = new HashMap<>();
            seqTime = new SeqTime();
        }

        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) {
            // init the friend map
            Tweet tweet = new Tweet(userId, tweetId, seqTime.getTime());
            Set<Integer> followings = userToFollowingsMap.getOrDefault(userId, new HashSet<>());
            followings.add(userId); // 自己是自己的friend，看自己的twitt
            userToFollowingsMap.put(userId, followings);

            // save the tweet into the tweetmap
            PriorityQueue<Tweet> tweets = userToTweetsMap.getOrDefault(userId, new PriorityQueue<Tweet>(
                (a, b) -> b.time - a.time
            ));
            tweets.offer(tweet);
            userToTweetsMap.put(userId, tweets);
        }

        /** 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 herself. Tweets must be ordered from most recent to least recent. */
        public List<Integer> getNewsFeed(int userId) {
            Set<Integer> followings = userToFollowingsMap.get(userId);

            if (followings == null || followings.isEmpty()) {
                return new ArrayList<>();
            }


            Map<Integer, PriorityQueue<Tweet>> tweetList = new HashMap<>();
            for (Integer following : followings) {
                PriorityQueue<Tweet> tweets = userToTweetsMap.get(following);
                PriorityQueue<Tweet> top10List = getTop10Tweets(tweets);

                Iterator<Tweet> it = top10List.iterator();
                if (!top10List.isEmpty()) {
                    tweetList.put(following, top10List);
                }
            }

            return mergeTweets(tweetList);
        }

        /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
        public void follow(int followerId, int followeeId) {
            Set<Integer> followings = userToFollowingsMap.getOrDefault(followerId, new HashSet<>());
            followings.add(followerId); // self follow
            followings.add(followeeId);
            userToFollowingsMap.put(followerId, followings);
        }

        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        public void unfollow(int followerId, int followeeId) {
            if (followerId == followeeId) {
                return;
            }
            Set<Integer> followings = userToFollowingsMap.getOrDefault(followerId, new HashSet<>());
            followings.remove(followeeId);
            userToFollowingsMap.put(followerId, followings);
        }

        private PriorityQueue<Tweet> getTop10Tweets(PriorityQueue<Tweet> tweets) {

            // most recent at top
            PriorityQueue<Tweet> top10Tweets = new PriorityQueue<Tweet>(
                (a, b) -> b.time - a.time
            );

            for (int i = 0; i < 10; i++) {
                if (tweets == null || tweets.isEmpty()) {
                    break;
                }

                top10Tweets.offer(tweets.poll());
            }

            // push back
            Iterator it = top10Tweets.iterator();
            while (it.hasNext()) {
                tweets.offer((Tweet)it.next());
            }

            return top10Tweets;
        }

        private List<Integer> mergeTweets(Map<Integer, PriorityQueue<Tweet>> tweetLists) {
            List<Integer> ans = new ArrayList<>();
            PriorityQueue<Tweet> finalPQ = new PriorityQueue<Tweet>(
                (a, b) -> b.time - a.time
            );

            for (Integer userId : tweetLists.keySet()) {
                PriorityQueue<Tweet> tweets = tweetLists.get(userId);
                Tweet top = tweets.poll();
                //tweetLists.put(userId, tweets);
                finalPQ.offer(top);
            }

            int count = 0;
            while (count < 10 && !tweetLists.isEmpty()) { // similar to question for LC281  k-iterators
                Tweet curr = finalPQ.poll();
                ans.add(curr.twitterId);
                PriorityQueue<Tweet> nextTweetList = tweetLists.get(curr.userId);

                if (!nextTweetList.isEmpty()) {
                    finalPQ.offer(nextTweetList.poll());
                } else {
                    tweetLists.remove(curr.userId);
                }
                count += 1;
            }

            return ans;
        }
    }

    class Tweet {
        int twitterId;
        int userId;
        int time;
        public Tweet(int userId, int twitterId, int time) {
            this.userId = userId;
            this.twitterId = twitterId;
            this.time = time;
        }
    }

    class SeqTime {
        int time;
        public SeqTime() {
            time = 0;
        }

        public int getTime() {
            int curTime = time;
            time += 1; // @note: possible overflow for int
            return curTime;
        }
    }

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId);
 * List<Integer> param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId);
 * obj.unfollow(followerId,followeeId);
 */
}

// OJ: https://leetcode.com/problems/design-twitter/
// Time:
//     * Twitter: O(1)
//     * getNewsFeed: O(F)
//     * follow: O(1)
//     * unfollow: O(1)
// Space: O(F + R) where F is number of feeds, R is count of follower-followee relationships.
class Twitter {
private:
    deque<pair<int, int>> feeds;
    unordered_map<int, unordered_set<int>> followerToFollowee;
public:
    Twitter() {}
    void postTweet(int userId, int tweetId) {
        feeds.push_front(make_pair(userId, tweetId));
    }
    vector<int> getNewsFeed(int userId) {
        vector<int> v;
        auto it = feeds.begin();
        auto &followees = followerToFollowee[userId];
        int cnt = 0;
        while (it != feeds.end() && cnt < 10) {
            int posterId = it->first;
            if (posterId == userId
            || followees.find(posterId) != followees.end()) {
                v.push_back(it->second);
                ++cnt;
            }
            ++it;
        }
        return v;
    }
    void follow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        followerToFollowee[followerId].insert(followeeId);
    }
    void unfollow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        followerToFollowee[followerId].erase(followeeId);
    }
};

'''
heapq.nlargest(n, iterable, key=None) is used to
find the n largest elements from a dataset defined by iterable.


people = [
    {"name": "Alice", "age": 30},
    {"name": "Bob", "age": 25},
    {"name": "Carol", "age": 40},
    {"name": "Dave", "age": 20}
]

# Using nlargest to find the two oldest people
oldest_two = heapq.nlargest(2, people, key=lambda person: person["age"])

print(oldest_two)
# Output: [{'name': 'Carol', 'age': 40}, {'name': 'Alice', 'age': 30}]

'''

from collections import defaultdict
from heapq import nlargest
from typing import List

class Twitter:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.user_tweets = defaultdict(list)
        self.user_following = defaultdict(set)
        self.tweet_time = defaultdict(int)  # id => timestamp
        self.time = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        """
        Compose a new tweet.
        """
        self.time += 1
        self.user_tweets[userId].append(tweetId)
        self.tweet_time[tweetId] = self.time

    def getNewsFeed(self, userId: int) -> List[int]:
        """
        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 herself. Tweets must be ordered from most recent to least recent.
        """
        following = self.user_following[userId]
        users = set(following)
        users.add(userId)  # should see my own tweets too
        tweets = [self.user_tweets[u][::-1][:10] for u in users]  # Get the 10 most recent tweets
        '''
        unconventional way to flatten a list of lists into a single list:
            lists = [[1, 2, 3], [4, 5], [6]]
            flattened = sum(lists, [])
            print(flattened)  # Output: [1, 2, 3, 4, 5, 6]

        or, another way getting flattened tweets:
            flattened_tweets = [tweet for each_user_tweets in tweets for tweet in each_user_tweets]
        '''
        tweets = sum(tweets, [])
        return nlargest(10, tweets, key=lambda tweet: self.tweet_time[tweet])

    def follow(self, followerId: int, followeeId: int) -> None:
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        """
        self.user_following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        """
        following = self.user_following[followerId]
        if followeeId in following:
            following.remove(followeeId)

# 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)

############

import heapq


class Twitter(object):

  def __init__(self):
    """
    Initialize your data structure here.
    """
    self.ts = 0
    self.tweets = collections.defaultdict(list)
    self.friendship = collections.defaultdict(set)

  def postTweet(self, userId, tweetId):
    """
    Compose a new tweet.
    :type userId: int
    :type tweetId: int
    :rtype: void
    """
    tInfo = self.ts, tweetId, userId, len(self.tweets[userId])
    self.tweets[userId].append(tInfo)
    self.ts -= 1

  def getNewsFeed(self, 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 herself. Tweets must be ordered from most recent to least recent.
    :type userId: int
    :rtype: List[int]
    """
    ret = []
    heap = []
    if self.tweets[userId]:
      heapq.heappush(heap, self.tweets[userId][-1])

    for followeeId in self.friendship[userId]:
      if self.tweets[followeeId]:
        heapq.heappush(heap, self.tweets[followeeId][-1])
    cnt = 10
    while heap and cnt > 0: # not using nlargest()
      _, tid, uid, idx = heapq.heappop(heap)
      ret.append(tid)
      if idx > 0:
        heapq.heappush(heap, self.tweets[uid][idx - 1])
      cnt -= 1
    return ret

  def follow(self, followerId, followeeId):
    """
    Follower follows a followee. If the operation is invalid, it should be a no-op.
    :type followerId: int
    :type followeeId: int
    :rtype: void
    """
    if followerId == followeeId:
      return
    self.friendship[followerId] |= {followeeId}

  def unfollow(self, followerId, followeeId):
    """
    Follower unfollows a followee. If the operation is invalid, it should be a no-op.
    :type followerId: int
    :type followeeId: int
    :rtype: void
    """
    self.friendship[followerId] -= {followeeId}

# 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)

355 - Design Twitter

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions