Java AC Solution Beats 99.34% using incrementing timestamp and HashMaps


  • 0
    I
    public class Twitter {
        public class Tweet {
            int tid;
            int ts;
            public Tweet(int tid) {
                this.tid = tid;
                ts = count++;
            }
        }
        Map<Integer, List<Tweet>> tweets; //user, list of tweets
        Map<Integer, Set<Integer>> follows; //user, set of ids ur following
        PriorityQueue<List<Tweet>> pq;
        int count;
        /** Initialize your data structure here. */
        public Twitter() {
            tweets = new HashMap<>();
            follows = new HashMap<>();
            pq = new PriorityQueue<List<Tweet>>(10, new Comparator<List<Tweet>>() {
               @Override
               public int compare(List<Tweet> t1, List<Tweet> t2) {
                   return 0 - t1.get(t1.size() - 1).ts + t2.get(t2.size() - 1).ts;
               }
            });
            count = 1;
        }
        
        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) {
            if (!tweets.containsKey(userId)) tweets.put(userId, new ArrayList<>());
            if (!follows.containsKey(userId)) {
                follows.put(userId, new HashSet<>());
                follows.get(userId).add(userId);
            }
            tweets.get(userId).add(new Tweet(tweetId));
        }
        
        /** 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) {
            int fill = 10;
            List<Integer> res = new ArrayList<>(fill);
            if (!follows.containsKey(userId)) return res;
            for (Integer i : follows.get(userId)) {
                List<Tweet> curr = tweets.getOrDefault(i, new ArrayList<>());
                if (curr.size() > 0) pq.add(new ArrayList<>(curr)); //avoid adding lists with no tweets.
            }
            while (!pq.isEmpty() && fill-- > 0) { // poll until empty or 10
                List<Tweet> list = pq.poll();
                Tweet t = list.remove(list.size() - 1);
                res.add(t.tid);
                if (list.size() > 0) pq.add(list);
            }
            while (!pq.isEmpty()) pq.poll(); //empty for later use
            return res;
        }
        
        /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
        public void follow(int followeeId, int followerId) {
            if (!follows.containsKey(followeeId)) follows.put(followeeId, new HashSet<>());
            Set<Integer> following = follows.get(followeeId);
            following.add(followerId);
            following.add(followeeId);
        }
        
        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        public void unfollow(int followeeId, int followerId) {
            if (followeeId == followerId) return;
            if (!follows.containsKey(followeeId)) follows.put(followeeId, new HashSet<>());
            follows.get(followeeId).remove(followerId);
        }
    }

Log in to reply
 

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