Why PriorityQueue based getNewsFeed() is faster?


  • 0

    Hi everyone,

    I see many posts who are using PriorityQueue based getNewsFeed(). But I did not understand why this solution is faster than the Collections.sort(ArrayList<>) based solution.

    My solution takes 158 ms. I will really appreciate if anyone can help me improve my code time complexity.

    public class Twitter {
        class MyTweet {
            int id, time;
            
            MyTweet(int id, int time) {
                this.id = id;
                this.time = time;
            }
        }
        
        class MyComp implements Comparator<MyTweet> { 
            @Override
            public int compare(MyTweet t1, MyTweet t2) {
                return t2.time - t1.time;
            } 
        }
        
        private HashMap<Integer, ArrayList<MyTweet>> userTweetMap;
        private HashMap<Integer, HashSet<Integer>> userFollowerMap;
        private int timeStamp;
        
        /** Initialize your data structure here. */
        public Twitter() {
            userTweetMap = new HashMap<Integer, ArrayList<MyTweet>>();
            userFollowerMap = new HashMap<Integer, HashSet<Integer>>();
            timeStamp = 0;
        }
        
        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) {
            MyTweet tweet = new MyTweet(tweetId, ++timeStamp);
            
            ArrayList<MyTweet> tweetList = new ArrayList<>();
            if(userTweetMap.containsKey(userId)) {
                tweetList = userTweetMap.get(userId);
            }
            
            tweetList.add(tweet);
            userTweetMap.put(userId, tweetList);
        }
        
        /** 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) {
            ArrayList<MyTweet> tweetList = new ArrayList<>();
    
            if(userFollowerMap.containsKey(userId)) {
                for(int follower : userFollowerMap.get(userId)) {
                    if(userTweetMap.containsKey(follower)) {
                        tweetList.addAll(userTweetMap.get(follower));
                    }
                }
            }
    
            if(userTweetMap.containsKey(userId))
                tweetList.addAll(userTweetMap.get(userId));
        
            Collections.sort(tweetList, new MyComp());
            ArrayList<Integer> newsFeed = new ArrayList<>(10);
    
            int count=0;
            for(MyTweet tweet : tweetList) {
                newsFeed.add(tweet.id);
                if(++count == 10) {
                    break;
                }
            }
            
            return newsFeed;
        }
        
        /** 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) {
                HashSet<Integer> followerSet;
                
                if(userFollowerMap.containsKey(followerId)) {
                    followerSet = userFollowerMap.get(followerId);
                } else {
                    followerSet = new HashSet<>();
                }
    
                followerSet.add(followeeId);
                userFollowerMap.put(followerId, followerSet);
            }
        }
        
        /** 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 && userFollowerMap.containsKey(followerId)) {
                HashSet<Integer> followerSet = userFollowerMap.get(followerId);
                followerSet.remove(Integer.valueOf(followeeId));
                userFollowerMap.put(followerId, followerSet);
            }
        }
    }
    
    /**
     * 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);
     */
    

  • 0
    R

    Theoretically both solutions are O( N logN ) if you consider 10 as a constant.
    However, priority queue solution can be improved to skip some unnecessary inserts.
    For example, in the array solution, you collect and sort 10 tweets from every followed user even if you don't need that many from each user.
    However in the priority queue solution, you collect one (latest) from each user, get the latest among those collected, and then add one more from that user, until you have 10 tweets and then you're done.

    If you consider 10 as a variable, let's say M, your solution's complexity is O( NM * log(NM) )
    Priority Queue solution's complexity in that case would be O(T * logT) where T is the greater of M and N.

    Check out the getNewsFeed in this solution:
    https://discuss.leetcode.com/topic/48100/java-oo-design-with-most-efficient-function-getnewsfeed/2


Log in to reply
 

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