Fast getNewsFeed()


  • 1

    The idea is to maintain a newsFeed set for each user. The assumption is that getNewsFeed() is called much more frequently than the other functions. I guess most users expect fast loading of home page, but can tolerate reasonable delays in tweeting / following / unfollowing (they can be ajax with some tricks anyway). Not sure whether it is the case for Twitter though.

    public class Twitter {
    
        int seed = 0;
        Map<Integer, Deque<Tweet>> tweetMap;
        Map<Integer, Set<Integer>> followerMap;
        Map<Integer, Set<Tweet>> newsFeedMap;
        
        /** Initialize your data structure here. */
        public Twitter() {
            tweetMap = new HashMap<>();
            followerMap = new HashMap<>();
            newsFeedMap = new HashMap<>();
        }
        
        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) {
            Tweet tweet = new Tweet(seed++, tweetId);
            Deque<Tweet> tweets = tweetMap.get(userId);
            if (tweets == null) {
                tweets = new ArrayDeque<>();
                tweetMap.put(userId, tweets);
            }
            tweets.push(tweet);
            
            Set<Tweet> selfNews = newsFeedMap.get(userId);
            if (selfNews == null) {
                selfNews = new TreeSet<>((t1, t2) -> t2.seq - t1.seq);
                newsFeedMap.put(userId, selfNews);
            }
            selfNews.add(tweet);
    
            Set<Integer> followers = followerMap.get(userId);
            if (followers != null) {
                for (Integer follower : followers) {
                    Set<Tweet> news = newsFeedMap.get(follower);
                    if (news == null) {
                        news = new TreeSet<>((t1, t2) -> t2.seq - t1.seq);
                        newsFeedMap.put(follower, news);
                    }
                    news.add(tweet);
                }
            }
        }
        
        /** 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<Tweet> news = newsFeedMap.get(userId);
            List<Integer> res = new ArrayList<>();
            if (news == null || news.isEmpty()) {
                return res;
            }
            
            int i = 0;
            Iterator<Tweet> it = news.iterator();
            while (it.hasNext() && i < 10) {
                res.add(it.next().tweetId);
                i++;
            }
            return res;
        }
        
        /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
        public void follow(int followerId, int followeeId) {
            
            if (followerId == followeeId) {
                return;
            }
            
            Set<Integer> followers = followerMap.get(followeeId);
            if (followers == null) {
                followers = new HashSet<>();
                followerMap.put(followeeId, followers);
            } else if (followers.contains(followerId)) {
                return;
            }
            followers.add(followerId);
    
            Deque<Tweet> tweets = tweetMap.get(followeeId);
            if (tweets == null || tweets.isEmpty()) {
                return;
            }
    
            Set<Tweet> news = newsFeedMap.get(followerId);
            if (news == null) {
                news = new TreeSet<>((t1, t2) -> t2.seq - t1.seq);
                newsFeedMap.put(followerId, news);
            }
            for (Tweet t : tweets) {
                news.add(t);
            }
        }
        
        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        public void unfollow(int followerId, int followeeId) {
            
            Set<Integer> followers = followerMap.get(followeeId);
            if (followers == null || followers.isEmpty()
                || !followers.contains(followerId)) {
                return;
            }
            followers.remove(Integer.valueOf(followerId));
    
            Deque<Tweet> tweets = tweetMap.get(followeeId);
            if (tweets == null || tweets.isEmpty()) {
                return;
            }
    
            Set<Tweet> news = newsFeedMap.get(followerId);
            for (Tweet t : tweets) {
                news.remove(t);
            }
        }
    }
    
    class Tweet {
        int seq;
        int tweetId;
        Tweet(int seq, int tweetId) {
            this.seq = seq;
            this.tweetId = tweetId;
        }
    }

  • 0
    Z

    Thanks for sharing. This one is actually more close to reality and scalable for a read heavy task. It's based on push model instead of pull model like most of the answer.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.