Java solution beating 98.62% other solution


  • 0
    M

    Solution uses 3 classes

    Tweet:

    • tweetID
    • userID
    • order (user specific order of tweet)
    • timeStamp (time specific order of tweet)

    User:

    • userID
    • list of Tweets
    • HashSet of Int (userID) - set of followers
    • Follow method which adds user id Followers list
    • Unfollow method which removes user id from followers list
    • postTweet method which will add Tweet at the end of the Tweet list. We have to add at the end. If we add at beginning, it becomes O(n) where n is number of tweets by the user.

    Twitter:

    • timeStamp - initialized to 0. It will serve as TimeStamp to compare the Tweet list.
    • Hashtable mapping Key of the user Id to users object. Vital part to access user.
    • postTweet method - this method maps few things. First of all check if the user is already there in the hashtable or not. if not, then we need to create another user. Create tweet with TimeStamp and increase TimeStamp by 1. Get the size of list of Tweets for the user and use that as the Order as that will be the place where Tweet will be added. And finally add that new created Tweet to users TweetList.
    • Follow method - check if both Followee and Follower user exist, create new if necessary and add to the followers list.
    • Unfollow method - same as Follow method. Just remove instead of adding to the follower list.
    • getNewsFeed - I am using PriorityQueue to get the list of tweets. First add the last tweet of TweetList by the current user. Add then add last tweet of all the other users in Followers list for that user. Remove peek and according to order variable in the tweet object, find the next tweet (order-1 tweet) from the TweetList by the user. You can get user from user id of the Tweet and users hashtable of Twitter. All in all O(Followers + 10*log (followers+1)). Pretty nice.
    import java.util.*;
    
    class Tweet implements Comparable<Tweet>
    {
        public int tweetID;
        public int timeStamp;
        public int order;
        public int userID;
        public Tweet(int id, int time, int ord,int uid)
        {
            tweetID = id;
            timeStamp = time;
            order = ord;
            userID = uid;
        }
        
        public int compareTo(Tweet t)
        {
            return Integer.compare(t.timeStamp, this.timeStamp);
        }
    }
    
    class User
    {
        public int userID;
        public ArrayList<Tweet> tweetList;
        public HashSet<Integer> followees;
        
        public User(int id)
        {
            userID = id;
            tweetList = new ArrayList<>();
            followees = new HashSet<>();
        }
        
        public void postTweet(Tweet tweet)
        {
            tweetList.add(tweet);
        }
        
        public void follow(int user)
        {
            if(!followees.contains(user))
            {
                followees.add(user);
            }
        }
        
        public void unfollow(int user)
        {
            if(followees.contains(user))
            {
                followees.remove(user);
            }
        }
    }
    
    public class Twitter 
    {
        int timeStamp;
        Hashtable<Integer,User> users;
    
        /** Initialize your data structure here. */
        public Twitter() 
        {
            timeStamp=0;
            users = new Hashtable<>();
        }
        
        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) 
        {
            User usr;
            if(users.containsKey(userId))
            {
                usr = users.get(userId); 
            }
            else
            {
                usr = new User(userId);
                users.put(userId, usr);
            }
            int order = usr.tweetList.size();
            Tweet twt = new Tweet(tweetId, timeStamp,order,userId);
            timeStamp++;
            usr.postTweet(twt);
        }
        
        /** 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(!users.containsKey(userId))
            {
                return new ArrayList<Integer>();
            }
            
            User usr = users.get(userId);
            
            PriorityQueue<Tweet> feed = new PriorityQueue<Tweet>();
            List<Integer> ans = new ArrayList<>();
            
            if(usr.tweetList.size()>0)
            {
                feed.add(usr.tweetList.get(usr.tweetList.size()-1));
            }
    
            Iterator iter = usr.followees.iterator();
            while (iter.hasNext()) 
            {
                User ur = (User)users.get(iter.next());
                if(ur.tweetList.size()>0)
                {
                    feed.add(ur.tweetList.get(ur.tweetList.size()-1));
                }
            }
            int k=10;
            while(!feed.isEmpty() && k-->0)
            {
                Tweet tw=feed.poll();
                ans.add(tw.tweetID);
                if(tw.order>0)
                {
                    feed.offer(users.get(tw.userID).tweetList.get(tw.order-1));
                }
            }
            return ans;
        }
        
        /** 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;
            User follower,followee;
            
            if(users.containsKey(followerId))
            {
                follower = users.get(followerId);
            }
            else
            {
                follower = new User(followerId);
                users.put(followerId, follower);
            }
            
            if(users.containsKey(followeeId))
            {
                followee = users.get(followeeId);
            }
            else
            {
                followee = new User(followeeId);
                users.put(followeeId, followee);
            }
            
            follower.follow(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;
            User follower,followee;
            
            if(users.containsKey(followerId))
            {
                follower = users.get(followerId);
            }
            else
            {
                follower = new User(followerId);
                users.put(followerId, follower);
            }
            
            if(users.containsKey(followeeId))
            {
                followee = users.get(followeeId);
            }
            else
            {
                followee = new User(followeeId);
                users.put(followeeId, followee);
            }
            
            follower.unfollow(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);
     */
    

Log in to reply
 

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