Java Solution using HashMap and PriorityQueue


  • 6
    L
    private static class Tweet {
    	int timestamp;
    	int tweetId;
    
    	public Tweet(int tweetId, int timestamp) {
    		this.tweetId = tweetId;
    		this.timestamp = timestamp;
    	}
    }
    
    private Map<Integer, Set<Integer>> followMap = new HashMap<Integer, Set<Integer>>();
    private Map<Integer, List<Tweet>> tweetMap = new HashMap<Integer, List<Tweet>>();
    
    private AtomicInteger timestamp;
    
    /** Initialize your data structure here. */
    public Twitter() {
    	timestamp = new AtomicInteger(0);
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
    	Tweet newTweet = new Tweet(tweetId, timestamp.getAndIncrement());
    
    	if (!tweetMap.containsKey(userId)) {
    		tweetMap.put(userId, new ArrayList<Tweet>());  //Assuming no deletion for now?
    	}
    
    	tweetMap.get(userId).add(newTweet);
    }
    
    /**
     * 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> result = new ArrayList<Integer>(10);
    
    	PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
    		public int compare(int[] it1, int[] it2) {
    			return tweetMap.get(it2[0]).get(it2[1]).timestamp - tweetMap.get(it1[0]).get(it1[1]).timestamp;
    		}
    	});
    
    	Set<Integer> followeeSet = new HashSet<Integer>();
    	followeeSet.add(userId);
    	if (followMap.containsKey(userId)) {
    		followeeSet.addAll(followMap.get(userId));
    	}
    
    	for (Integer followee : followeeSet) {
    		if (tweetMap.containsKey(followee)) {
    			List<Tweet> tweetList = tweetMap.get(followee);
    			if (tweetList.size() > 0) {
    				pq.add(new int[] { followee, tweetList.size() - 1 });
    			}
    		}
    	}
    
    	while (result.size() < 10 && pq.size() > 0) {
    		int[] it = pq.poll();
    
    		result.add(tweetMap.get(it[0]).get(it[1]).tweetId);
    		it[1]--;
    		if (it[1] >= 0) {
    			pq.add(it);
    		}
    	}
    
    	return result;
    }
    
    /**
     * Follower follows a followee. If the operation is invalid, it should be a
     * no-op.
     */
    public void follow(int followerId, int followeeId) {
    	Set<Integer> followSet = followMap.get(followerId);
    	if (followSet == null) {
    		followSet = new HashSet<Integer>();
    		followMap.put(followerId, followSet);
    	}
    
    	followSet.add(followeeId);
    }
    
    /**
     * Follower unfollows a followee. If the operation is invalid, it should be
     * a no-op.
     */
    public void unfollow(int followerId, int followeeId) {
    	Set<Integer> followSet = followMap.get(followerId);
    	if (followSet == null) {
    		followSet = new HashSet<Integer>();
    		followMap.put(followerId, followSet);
    	}
    
    	followSet.remove(followeeId);
    }

  • -1

    Instead of using List to store the tweets, I use pointer inside tweet to connect all the tweets. This benefits the getNewsFeed operation.

    public class Twitter {
    
    /* new class*/
    class tweet{
        long postTime;
        int tweetId;
        tweet next;
        tweet(int Id, long time){
            this.tweetId=Id;
            this.postTime=time;
            this.next=null;
        }
    }
    
    long time;
    HashMap<Integer,tweet> userTweet;
    HashMap<Integer,Set<Integer>> follow;
    
    /** Initialize your data structure here. */
    public Twitter() {
        time=0;
        userTweet=new HashMap<Integer,tweet>();
        follow=new HashMap<Integer,Set<Integer>>();
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if(userTweet.containsKey(userId)){
            tweet tmp=new tweet(tweetId,time++);
            tmp.next=userTweet.get(userId);
            userTweet.put(userId,tmp);
        }
        else {
            tweet tmp=new tweet(tweetId,time++);
            userTweet.put(userId,tmp);
        }
    }
    
    /** 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> feed=new ArrayList<Integer>();
        PriorityQueue<tweet> feedQueue=new PriorityQueue<tweet>(
            new Comparator<tweet>(){
                public int compare(tweet a, tweet b){
                    if(a.postTime-b.postTime>0) return -1;
                    else return 1;
                }
            });
        if(userTweet.containsKey(userId)) feedQueue.offer(userTweet.get(userId));
        if(follow.containsKey(userId)){
            for(Integer followee : follow.get(userId)){
                if(userTweet.containsKey(followee)) feedQueue.offer(userTweet.get(followee));
            }
        }
        while(!feedQueue.isEmpty() && feed.size()<10){
            tweet top=feedQueue.poll();
            feed.add(top.tweetId);
            if(top.next!=null) feedQueue.offer(top.next);
        }
        return feed;
    }
    
    /** 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;
        if(follow.containsKey(followerId)) follow.get(followerId).add(followeeId);
        else {
            Set<Integer> tmp=new HashSet<Integer>();
            tmp.add(followeeId);
            follow.put(followerId,tmp);
        }
    }
    
    /** 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;
        if(follow.containsKey(followerId)) follow.get(followerId).remove(followeeId);
    }
    

    }


  • 0
    Q

    There is a reason people don't use List to store all tweets. The performance of this solution is pretty bad. WIth all tweets being in one giant ArrayList.

    1. Inserting into beginning of ArrayList is bad.
    2. To get user's tweets potentially need to iterate over the whole List.

  • 0
    H

    What about using linkedlist. Add operation on LinkedList is O(1)


  • 0
    Q

    You will still need to iterate over the whole list to find the tweets.


  • 0
    C

    i don't understand this line if(top.next!=null) feedQueue.offer(top.next); can someone explain please?


  • 3
    V

    Post a similar approach.

    Instead of List, I use Deque to store the tweets in the map, and poll whenever the number of tweets is greater than 10.

    private static class Tweet {
        int timestamp;
        int tweetId;
    
        public Tweet(int tweetId, int timestamp) {
            this.tweetId = tweetId;
            this.timestamp = timestamp;
        }
    }
    private Map<Integer, Set<Integer>> follow = new HashMap<>();
    private Map<Integer, Deque<Tweet>> tweets = new HashMap<> ();
    private AtomicInteger timestamp;
    
    /** Initialize your data structure here. */
    public Twitter() {
        timestamp = new AtomicInteger(0);
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        Tweet tweet = new Tweet(tweetId, timestamp.getAndIncrement());
        tweets.putIfAbsent(userId, new ArrayDeque<Tweet>(11));
        Deque queue = tweets.get(userId);
        queue.offer(tweet);
        if (queue.size() > 10)
            queue.poll();
    }
    
    /** 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<> (10);
        Set<Integer> followers = follow.getOrDefault(userId, new HashSet<> ());
        PriorityQueue<Tweet> pq = new PriorityQueue<> (20, (x, y) -> x.timestamp - y.timestamp);
        pq.addAll(tweets.getOrDefault(userId, new ArrayDeque<Tweet> ()));
        for (int follower : followers) {
            pq.addAll(tweets.getOrDefault(follower, new ArrayDeque<Tweet> ()));
            while (pq.size() > 10)
                pq.poll();
        }
        while (!pq.isEmpty())
            newsFeed.add(0, pq.poll().tweetId);
        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 (followerId == followeeId)
            return;
        follow.putIfAbsent(followerId, new HashSet<> ());
        follow.get(followerId).add(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if (follow.containsKey(followerId))
            follow.get(followerId).remove(followeeId);
    }

  • 0
    J

    To qgambit2:

    I think you didn't get the point of this post. He doesn't need to traverse the list. All he needs is to find the next one. The PQ only has 10 items. One out, then one in. And list makes it easier to which is the next to put in.

    You can check this one for more information: https://leetcode.com/discuss/108198/java-oo-design-with-most-efficient-function-getnewsfeed


Log in to reply
 

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