Java linked list solution without heap


  • 0
    A

    I use an integer for time stamp, and use a linked list to store tweets. Since most recent tweets will always be added later, so getting news feed is essentially taking the 10 most recent tweets from k sorted lists, where k is the number of users followed + 1 (self).
    This has a time complexity 10*k, usually the news feed number is small (probably under 50), so this should be O(k).
    Naive heap solution gives nlog(n) time, and takes n extra space, which n is total number of tweets we need to check.
    This can be very expensive because 1. it can be millions of tweets and 2. you need to do this for every news feed.

    public class Twitter {
        private Map<Integer, User> userMap;
        private int time;
    
        /** Initialize your data structure here. */
        public Twitter() {
            userMap = new HashMap<Integer, User>();
            time = 0;
        }
        
        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) {
            if(!userMap.containsKey(userId)){ userMap.put(userId, new User(userId)); }
            User user = userMap.get(userId);
            user.postTweet(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) {
            if(!userMap.containsKey(userId)){ return new ArrayList<Integer>(); }
            User user = userMap.get(userId);
            List<Tweet> allTweets = user.getTweets();
            return getFeed10(allTweets);
        }
        
        private List<Integer> getFeed10(List<Tweet> tweets){
            List<Integer> res = new ArrayList<Integer>(10);
            for(int i=0; i<10; i++){ // get last 10 tweets
                Tweet lastTweet = null;
                int lastIndex = -1;
                for(int j=0; j<tweets.size(); j++){ // find cur lastest tweet
                    Tweet cur = tweets.get(j);
                    if(cur!=null && (lastTweet==null || cur.time > lastTweet.time)){
                        lastTweet = cur;
                        lastIndex = j;
                    }
                }
                if(lastTweet!=null){
                    res.add(lastTweet.id);
                    tweets.set(lastIndex, lastTweet.next); // increase
                }
                else { break; }  // no more tweets, done
            }
            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; } // can't follow self
            if(!userMap.containsKey(followerId)){ userMap.put(followerId, new User(followerId)); }
            if(!userMap.containsKey(followeeId)){ userMap.put(followeeId, new User(followeeId)); }
            User follower = userMap.get(followerId);
            User followee = userMap.get(followeeId);
            follower.follow(followee);
        }
        
        /** 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; } // can't unfollow self
            if(!userMap.containsKey(followerId) || !userMap.containsKey(followeeId)){ return; }
            User follower = userMap.get(followerId);
            User followee = userMap.get(followeeId);
            follower.unfollow(followee);
        }
        
        private class User {
        public Set<User> followees;
        public Tweet lastTweet;
        public int id;
        public User(int uid){
            id = uid;
            lastTweet = null;
            followees = new HashSet<User>();
        }
        public void postTweet(int tId, int time){
            Tweet t = new Tweet(tId, time);
            t.next = lastTweet;
            lastTweet = t;
        }
        public void follow(User followee){
            if(!followees.contains(followee)){
                followees.add(followee);
            }
        }
        public void unfollow(User followee){
            if(followees.contains(followee)){
                followees.remove(followee);
            }
        }
        public List<Tweet> getTweets(){
            List<Tweet> tweets = new ArrayList<Tweet>();
            for(User u : followees){
                tweets.add(u.lastTweet);
            }
            tweets.add(this.lastTweet);
            return tweets;
        }
        }
    
        private class Tweet {
            public int id;
            public int time;
            public Tweet next;
            public Tweet(int tid, int tm){
            id = tid;
            time = tm;
            }
        }
    }

Log in to reply
 

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