JAVA solution using Top k merge and One hashMap, beats (99%)!


  • 0
    L

    The solution uses one hashMap to store the user information. each user owns its set for followees and I use the priorityQueue to output the top 10 tweets.
    ....
    public class Twitter {

    /** Initialize your data structure here. */
    private HashMap<Integer,User> uMap;
    private int count = 0;
    private Tweet preTweet;
    private User curUser;
    
    public class Tweet implements Comparable<Tweet>{
        public int context;
        public int count;
        public Tweet sonTweet;
        
        Tweet(int tweetId, int count) {
            this.context = tweetId;
            this.count = count;
    
        }
        @Override 
        public int compareTo(Tweet b) {
            return b.count - this.count;
        }
    }
    
    public class User{
        public int userId;
        public Set<Integer> followSet;
        public Tweet latestT;
        
        User(int userId, Set<Integer> followSet, Tweet latestT) {
            this.userId = userId;
            this.followSet = followSet;
            this.latestT = latestT;
        }
    }
    public Twitter() { 
        uMap = new HashMap<Integer,User>();
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if (!uMap.containsKey(userId)) {     
            addUser(userId);
        }
        curUser = uMap.get(userId);
        Tweet newTweet = new Tweet(tweetId,count++);
        preTweet = curUser.latestT;
        curUser.latestT = newTweet;
        newTweet.sonTweet = preTweet;
    }
    
    /** 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) {
        PriorityQueue<Tweet> outPut = new PriorityQueue<Tweet>();
        List<Integer> res = new ArrayList<Integer>();
        
        if (!uMap.containsKey(userId)) {
             addUser(userId);
             return res;
        }
        curUser = uMap.get(userId);
        for(Integer uId: curUser.followSet) {
            User curU = uMap.get(uId);
            if (curU.latestT != null) {
                outPut.add(curU.latestT);
            }
        }
        int sum = 0;
        while (sum < 10 && outPut.size() > 0) {
            Tweet curT = outPut.poll();
            res.add(curT.context);
            curT = curT.sonTweet;
            if (curT != null) outPut.add(curT);
            sum++;
        }
        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 (followerId == followeeId) return ;
        if (!uMap.containsKey(followerId)) {
            addUser(followerId);
        }
        if (!uMap.containsKey(followeeId)) {
            addUser(followeeId);
        }
        uMap.get(followerId).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) {
        if (followerId == followeeId) return;
        if (!uMap.containsKey(followerId))  return;
        Set<Integer> curSet = uMap.get(followerId).followSet;
        if (!curSet.contains(followeeId)) return;
        curSet.remove(followeeId);
    }
    
    private void addUser(int userId){
        User newU = new User(userId, new HashSet<Integer>(), null);
        newU.followSet.add(userId);
        uMap.put(userId, newU);
    }
    

    }
    ...


Log in to reply
 

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