Java neat code beats 99%


  • 1
    C
    public class Twitter {
        static class Tweet{
            int id;
            int seq;
            Tweet next;
            static int counter = 0;
            
            public Tweet(int id){
                this.id = id;
                seq = counter++;
            }
        }
    
        Map<Integer, Set<Integer>> connections;
        Map<Integer, Tweet> tweets;
        PriorityQueue<Tweet> latest;
        
        /** Initialize your data structure here. */
        public Twitter() {
            connections = new HashMap<>();
            tweets = new HashMap<>();
            latest = new PriorityQueue<>(10, (Tweet t1, Tweet t2)->{return Integer.compare(t2.seq, t1.seq);});
        }
        
        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) {
            Tweet head = tweets.getOrDefault(userId, new Tweet(0));
            Tweet tweet = new Tweet(tweetId);
            tweet.next = head.next;
            head.next = tweet;
            tweets.put(userId, head);
        }
        
        
        /** 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) {
            latest.clear();
            
            Set<Integer> followees = connections.getOrDefault(userId, new HashSet<>());
            followees.add(userId);
            for (Integer id : followees){
                Tweet head = tweets.get(id);
                if (head != null){
                    latest.add(head.next);
                }
            }
            
            List<Integer> latest10 = new ArrayList<>(10);
            while(latest10.size() < 10 && !latest.isEmpty()){
                Tweet tweet = latest.poll();
                latest10.add(tweet.id);
                if (tweet.next != null){
                    latest.add(tweet.next);
                }
            }
            return latest10;
        }
        
        /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
        public void follow(int followerId, int followeeId) {
            Set<Integer> followees = connections.getOrDefault(followerId, new HashSet<>());
            followees.add(followeeId);
            connections.put(followerId, followees);
        }
        
        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        public void unfollow(int followerId, int followeeId) {
            connections.getOrDefault(followerId, new HashSet<>()).remove(followeeId);
        }
    }
    

  • 0
    V

    Hi, in your getNewsFeed function, you have a bug.
    you add userId to underlying hashSet for connections.
    correct way should make copy of that or just separate to add for self's feed instead:

    Set<Integer> followees = new HashSet<>();
    followees.add(userId);
    Set<Integer> connection = connections.get(userId);
    if (connection != null){
        followees.addAll(connection);
    }
    

    The code here is very neat and smart, I used a local PriorityQueue and another list which seems your ways here is better:

    List<Integer> latest10 = new ArrayList<>(10);
    while(latest10.size() < 10 && !latest.isEmpty()){
        Tweet tweet = latest.poll();
        latest10.add(tweet.id);
        if (tweet.next != null){
            latest.add(tweet.next);
        }
    }
    

Log in to reply
 

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