Java easy design with heap to construct newsfeed


  • 0

    Use maxHeap to get most recent post among one's friends.
    A user class Pair<Tweet, Iterator> is defined to keep track of next tweet in the list.
    Notice that using index is inefficient because LinkedList's get takes O(n), but iterator.next() takes O(1)
    This design does not have a dedicated createAccount() method, which causes confusion.

    public class Twitter {
        
        private Map<Integer, User> users;
        private Map<Integer, Tweet> tweets;
        private int time;
    
        /** Initialize your data structure here. */
        public Twitter() {
            users = new HashMap<>();
            tweets = new HashMap<>();
        }
        
        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) {
            if (!users.containsKey(userId)) {
                users.put(userId, new User(userId));
            }
            Tweet tweet = new Tweet(tweetId, time++);
            tweets.put(tweetId, tweet);
            users.get(userId).tweets.add(0, tweet);
        }
        
        /** 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) {
            List<Integer> newsfeed = new ArrayList<>();
            if (!users.containsKey(userId)) {
                users.put(userId, new User(userId));
            }
            
            Queue<Pair> maxHeap = new PriorityQueue<>(new Comparator<Pair>() {
                public int compare(Pair p1, Pair p2) {
                    return p2.tweet.timestamp - p1.tweet.timestamp;
                } 
            });
            
            for (User friend : users.get(userId).friends) {
                Iterator<Tweet> it = friend.tweets.iterator();
                if (it.hasNext()) {
                    maxHeap.offer(new Pair(it.next(), it));
                }
            }
            
            while (!maxHeap.isEmpty() && newsfeed.size() < 10) {
                Pair recent = maxHeap.poll();
                newsfeed.add(recent.tweet.id);
                if (recent.iterator.hasNext()) {
                    recent.tweet = recent.iterator.next();
                    maxHeap.offer(recent);
                }
            }
            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 (!users.containsKey(followerId)) {
                users.put(followerId, new User(followerId));
            }
            if (!users.containsKey(followeeId)) {
                users.put(followeeId, new User(followeeId));
            }
            users.get(followerId).friends.add(users.get(followeeId));
        }
        
        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        public void unfollow(int followerId, int followeeId) {
            if (users.containsKey(followerId) && followerId != followeeId) {
                users.get(followerId).friends.remove(users.get(followeeId));
            }
        }
    }
    
    class Pair {
        Tweet tweet;
        Iterator<Tweet> iterator;
        public Pair(Tweet tweet, Iterator<Tweet> iterator) {
            this.tweet = tweet;
            this.iterator = iterator;
        }
    }
    
    class User {
        int id;
        Set<User> friends;
        List<Tweet> tweets;
        public User(int userId) {
            id = userId;
            tweets = new LinkedList<>();
            friends = new HashSet<>();
            friends.add(this);//add self as friend for convenience of getting newsfeed 
        }
    }
    
    class Tweet {
        int id;
        int timestamp;
        public Tweet(int tweetId, int time) {
            timestamp = time;
            id = tweetId;
        }
    }

Log in to reply
 

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