Optimized Min-Heap with size capped to 10


  • 0
    A
    public class Twitter {
    
    int TIME_STAMP = 0; // global time stamp tracker
    
    class Tweet {
    	int tweetId;
    	int userId;
    	int timeStamp;
    
    	public Tweet(int userId, int tweetId) {
    		this.userId = userId;
    		this.tweetId = tweetId;
    		this.timeStamp = TIME_STAMP++;
    	}
    }
    
    Map<Integer, List<Tweet>> tweetMap = null;
    Map<Integer, Set<Integer>> followMap = null;
    
    public Twitter() {
    	tweetMap = new HashMap<Integer, List<Tweet>>(); // user -> userTweetList
    	followMap = new HashMap<Integer, Set<Integer>>(); // user -> userFollowList
    }
    
    
    public void postTweet(int userId, int tweetId) {
    	if (!tweetMap.containsKey(userId)) {
    		tweetMap.put(userId, new LinkedList<Tweet>());
    	}
    	tweetMap.get(userId).add(new Tweet(userId, tweetId));
    }
    
    
    public List<Integer> getNewsFeed(int userId) {
    	PriorityQueue<Tweet> pq = new PriorityQueue<Tweet>(1, (t1, t2) -> t1.timeStamp - t2.timeStamp); // min heap
    	Set<Integer> follow = followMap.get(userId) == null ? new HashSet<Integer>() : followMap.get(userId);
    	follow.add(userId);
    	for (int uid : follow) {
    		List<Tweet> tweets = tweetMap.get(uid);
    		if (tweets != null) {
    			for (Tweet t : tweets) {
    				if (pq.size() < 10)
    					pq.add(t);
    				else {
    					if (t.timeStamp > pq.peek().timeStamp) { // only add if timestamp is more than peek
    						pq.poll();
    						pq.add(t);
    					}
    				}
    			}
    		}
    	}
    	int count = 0;
    	LinkedList<Integer> list = new LinkedList<Integer>();
    	while (!pq.isEmpty() && count++ < 10) {
    		list.addFirst(pq.poll().tweetId); // add in reverse order
    	}
    	return list;
    }
    
    
    public void follow(int followerId, int followeeId) {
    	if (!followMap.containsKey(followerId)) {
    		followMap.put(followerId, new HashSet<Integer>());
    	}
    	followMap.get(followerId).add(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
    	if (followMap.containsKey(followerId)) {
    		if (followMap.get(followerId).contains(followeeId)) {
    			followMap.get(followerId).remove(followeeId);
    		}
    	}
    }

Log in to reply
 

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