Java solution using 2 HashMap,1 time counter, and MergeKsortedList


  • -1

    Denote each tweet as a ListNode, containing info of tweetId and posting time; a user's tweets are arranged in a sorted LinkedList regarding to posting time,from latest to earliest.

    Two HashMap: user denotes {user: all his tweets} ; userHeCare denotes {user: all users he follows}

    When a new tweet is generated, we add it to the corresponding user's history(create a time stamped ListNode and insert it,keeping list sorted).

    When asked to get top 10, we take out all tweets from the user and all he follows, select 10(just what we do when we merge K sorted list).

    When doing follow-unfollow, just adding /deleting from userHeCare for current user

     class TweetNode{
    int id;
    int rank;
    TweetNode next;
    public TweetNode(int id,int rank){
    	this.id=id;
    	//a larger rank value indicates a more recent post
    	this.rank=rank;
    }
    

    }

    public class Twitter {
    HashMap<Integer,TweetNode> user;
    HashMap<Integer,HashSet<Integer>> userCare;
    int count;
    /** Initialize your data structure here. */
    public Twitter() {
    	user=new HashMap<>();
    	userCare=new HashMap<>();
    	count=0;
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
    	//if it's a new user, we save his information
    	if(!user.containsKey(userId)){
    		addNewUser(userId);
    	}
    
    	//insert a new tweet in current user's history(isnert at the head of LinkedList)
    	TweetNode curr=new TweetNode(tweetId,count);
    	TweetNode head=user.get(userId);
    	curr.next=head.next;
    	head.next=curr;
    	count++;
    
    }
    
    /** 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> res=new ArrayList<>();
    	if(!user.containsKey(userId)){
    		return res;
    	}
    	
    	//make sure tweets will be generated from latest post to oldest 
    	Comparator<TweetNode> comp=new Comparator<TweetNode>(){
    		public int compare(TweetNode tweet1,TweetNode tweet2){
    			return tweet2.rank-tweet1.rank;
    		}
    	};
    	PriorityQueue<TweetNode> heap=new PriorityQueue<TweetNode>(10,comp);
    	
    	//if current user and his followers ever tweets, we get all their tweets LinkedList(each individual has all his tweets sorted from latest to oldest)
    	if(user.get(userId).next!=null){
    		heap.offer(user.get(userId).next);
    	}
    	for(Integer care:userCare.get(userId)){
    		if(user.get(care).next!=null){
    			heap.offer(user.get(care).next);
    		}
    	}
    	//get top 10 latest tweets
    	for(int i=0;i<10&&!heap.isEmpty();i++){
    		TweetNode curr=heap.poll();
    		res.add(curr.id);
    		if(curr.next!=null){
    			heap.offer(curr.next);
    		}
    
    	}
    	return res;
    }
    
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
    	if(user.containsKey(followerId)){
    		if(!user.containsKey(followeeId)){
    			addNewUser(followeeId);
    		}
    		//we won't allow a followee following himself, because that would cause duplicates when we get top 10:his own tweets might be counted twice
    		if(followerId!=followeeId){
    			userCare.get(followerId).add(followeeId);
    		}
    	}else{
    		addNewUser(followerId);
    		if(!user.containsKey(followeeId)){
    			addNewUser(followeeId);
    		}
    
    		userCare.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(user.containsKey(followerId)){
    		userCare.get(followerId).remove(followeeId);
    	}       
    }
    
    //register a new user
    public void addNewUser(int userId){
    	user.put(userId,new TweetNode(0,-1));
    	userCare.put(userId,new HashSet<Integer>());
    }
    

    }


Log in to reply
 

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