Question

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

 355	Design Twitter

 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.

 Your design should support the following methods:

     postTweet(userId, tweetId):
        Compose a new tweet.

     getNewsFeed(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.

     follow(followerId, followeeId):
        Follower follows a followee.

     unfollow(followerId, followeeId):
        Follower unfollows a followee.


 Example:

 Twitter twitter = new Twitter();

 // User 1 posts a new tweet (id = 5).
 twitter.postTweet(1, 5);

 // User 1's news feed should return a list with 1 tweet id -> [5].
 twitter.getNewsFeed(1);

 // User 1 follows user 2.
 twitter.follow(1, 2);

 // User 2 posts a new tweet (id = 6).
 twitter.postTweet(2, 6);

 // 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.getNewsFeed(1);

 // User 1 unfollows user 2.
 twitter.unfollow(1, 2);

 // User 1's news feed should return a list with 1 tweet id -> [5],
 // since user 1 is no longer following user 2.
 twitter.getNewsFeed(1);

 @tag-design

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

Java

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);
 */
}

above is bulky, you can never code it out in 1-hour session if you first time saw this question

public class Twitter {
    private HashMap<Integer, HashSet<Integer>> follows;
    private HashMap<Integer, LinkedList<Tweet>> tweets;
    private int timestamp;

    private class Tweet implements Comparable<Tweet> {
        private int tweetId;
        private int ts;
        private int userId;
        public Tweet(int tweetId, int userId, int timestamp) {
            this.tweetId = tweetId;
            this.ts = timestamp;
            this.userId = userId;
        }
        @Override
        public int compareTo(Tweet t2) {
            return t2.ts - this.ts;
        }
    }

    /** Initialize your data structure here. */
    public Twitter() {
        follows = new HashMap<Integer, HashSet<Integer>>();
        tweets = new HashMap<Integer, LinkedList<Tweet>>();
        timestamp = 0;
    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if (!tweets.containsKey(userId)) {
            tweets.put(userId, new LinkedList<Tweet>());
        }
        tweets.get(userId).add(0, new Tweet(tweetId, userId, timestamp++)); // put to index=0, most recent

        if (!follows.containsKey(userId)) {
            follows.put(userId, new HashSet<>());
            follows.get(userId).add(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. */
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> feed = new LinkedList<Integer>();
        PriorityQueue<Tweet> q = new PriorityQueue<Tweet>();
        if (!follows.containsKey(userId)) {
            return feed;
        }
        HashSet<Integer> followed = follows.get(userId);
        HashMap<Integer, Integer> count = new HashMap<Integer, Integer>();
        for (Integer i:followed) {
            if (tweets.containsKey(i)) {
                Tweet t = tweets.get(i).get(0);
                q.add(t);
                count.put(t.userId, 1);
            }
        }
        while (q.size() > 0 && feed.size() < 10) {
            Tweet t = q.poll();
            feed.add(t.tweetId);
            int next = count.get(t.userId);
            count.put(t.userId, next + 1);
            if (next < tweets.get(t.userId).size()) {
                q.add(tweets.get(t.userId).get(next));
            }
        }
        return feed;
    }

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

    /** 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;
        }
        if (follows.containsKey(followerId)) {
            follows.get(followerId).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);
 */

All Problems

All Solutions