355. Design Twitter

2 hashMap(Map<Integer, List<Tweet>>, ) + list sort

T: O(mnlogmn)

S: O(mn)

class Twitter {

    class Tweet {
        int userId;
        int tweetId;
        int timestamp;
        Tweet(int userId,
              int tweetId,
              int timestamp) {
            
            this.userId = userId;
            this.tweetId = tweetId;
            this.timestamp = timestamp;
        }
    }
    Map<Integer, List<Tweet>> postMap;
    Map<Integer, Set<Integer>> followMap;
    int timestamp = 0;
    
    public Twitter() {
        postMap = new HashMap<>();
        followMap = new HashMap<>();
    }
    
    public void postTweet(int userId, int tweetId) {
        postMap.putIfAbsent(userId, new ArrayList<>());
        postMap.get(userId).add(new Tweet(userId, tweetId, timestamp++));
    }
    
    public List<Integer> getNewsFeed(int userId) {
        List<Tweet> all = new ArrayList<>();
        // PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.timestamp - a.timestamp);
        
        for (int targetId : followMap.getOrDefault(userId, new HashSet<>())) {
            for (Tweet tweet : postMap.getOrDefault(targetId, new ArrayList<>())) {
                // pq.offer(tweet);
                all.add(tweet);
            }
        }
        for (Tweet tweet : postMap.getOrDefault(userId, new ArrayList<>())) {
            // pq.offer(tweet);
            all.add(tweet);
        }
        Collections.sort(all, (a, b) -> b.timestamp - a.timestamp);
        List<Integer> result = new ArrayList<>();
        // int n = 0;
        // while (!pq.isEmpty() && n < 10) {
        //     result.add(pq.poll().tweetId);
        //     n++;
        // }
        int n = 0;
        while (n < 10 && n < all.size()) {
            result.add(all.get(n).tweetId);
            n++;
        }
        return result;
    }
    
    public void follow(int followerId, int followeeId) { // follower follow followee
        followMap.putIfAbsent(followerId, new HashSet<>());
        followMap.get(followerId).add(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        Set<Integer> set = followMap.getOrDefault(followerId, new HashSet<>());
        if (set.contains(followeeId)) {
            set.remove(followeeId);
        }
    }
}

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId);
 * List<Integer> param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId);
 * obj.unfollow(followerId,followeeId);
 
1. use 2 hashMap 
Map<Integer, List<Tweet>> postMap;
use ArrayList save all tweets with timestamp, postTweet: O(1)

Map<Integer, Set<Integer>> followMap;
use set to save followee, in that way, unfollow is O(1)
follow is also O(1)

getNewsFeed()
use PQ, but needs to get all followee * tweets count
add all followee * tweets count: O(mn)
PQ: O(mnlogmn) 

add all tweets into PQ to only add top 10 recent tweets to result
no difference comparing with just "sort"  ...because I get all tweets here and add all into PQ

so actually this solution is using list, add all followee * tweets count, then sort
add all followee * tweets count: O(mn)
sort: O(mnlogmn)

 */

hashMap(Map<Integer, User>) + User has tweet linkedlist, + PQ

getNewsFeed()
T: O(this user's followed count + 10)...actually I think it still need to add all..

T: postTweet, follow, unfollow: O(1)

S: O(user*followed + user* tweets count)

class Twitter {
    int timestamp = 0;

    class Tweet {
        private int tweetId;
        private Tweet next;
        private int timestamp;
        Tweet(int tweetId,
              int timestamp) {
            
            this.tweetId = tweetId;
            this.next = null;
            this.timestamp = timestamp;
        }
    }
    class User {
        private int id;
        private Tweet head;
        private Set<Integer> followed;
        
        User(int userId) {
            this.id = userId;
            this.head = null;
            followed = new HashSet<>();
            follow(userId); // follow yourself
        }
        public void follow(int userId) {
            this.followed.add(userId);
        }
        public void unfollow(int userId) {
            if (followed.contains(userId) && this.id != userId) { // 不可以取消關注自己
                this.followed.remove(userId);
            }
        }
        public void post(int tweetId, int timestamp) {
            Tweet tweet = new Tweet(tweetId, timestamp);
            tweet.next = head;
            head = tweet;
        }
    }
    
    private Map<Integer, User> postMap;
    
    public Twitter() {
        postMap = new HashMap<>();
    }
    
    public void postTweet(int userId, int tweetId) {
        postMap.putIfAbsent(userId, new User(userId));
        postMap.get(userId).post(tweetId, timestamp++);
    }
    
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> result = new ArrayList<>();
        if (!postMap.containsKey(userId)) {
            return result; // 根本沒這人
        }
        Set<Integer> followed = postMap.get(userId).followed;
            
        PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.timestamp - a.timestamp);
        for (int f : followed) {
            User u = postMap.get(f);
            if (u == null) {
                continue;
            }
            Tweet head = u.head;
            if (head == null) {
                continue;
            }
            pq.offer(head);
        }
        
        while (!pq.isEmpty() && result.size() < 10) {
            Tweet tweet = pq.poll();
            result.add(tweet.tweetId);
            if (tweet.next != null) {
                pq.offer(tweet.next);
            }
        }
        
        return result;
    }
    
    public void follow(int followerId, int followeeId) { // follower follow followee
        postMap.putIfAbsent(followerId, new User(followerId));
        postMap.get(followerId).follow(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        if (postMap.containsKey(followerId)){
            postMap.get(followerId).unfollow(followeeId);
        }
    }
}

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId);
 * List<Integer> param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId);
 * obj.unfollow(followerId,followeeId);

getNewsFeed()
T: O(this user's followed count + 10)

T: postTweet, follow, unfollow: O(1)

S: O(user*followed + user* tweets count)

 */

still use 2 map + pq, but stop earlier, this is faster

Runtime: 10 ms, faster than 97.95% of Java online submissions

pq change to use minHeap, 當遇到 timestmap 比 heap peek 大的, 就把那個小的丟掉, 放入大的

這樣可以提早結束

最後用 linkedlist addFirst 的技巧, 達到大的在前面的效果(因為 minHeap 事先排出來最小的..

class Twitter {

    class Tweet {
        int userId;
        int tweetId;
        int timestamp;
        Tweet(int userId,
              int tweetId,
              int timestamp) {
            
            this.userId = userId;
            this.tweetId = tweetId;
            this.timestamp = timestamp;
        }
    }
    Map<Integer, List<Tweet>> postMap;
    Map<Integer, Set<Integer>> followMap;
    int timestamp = 0;
    
    public Twitter() {
        postMap = new HashMap<>();
        followMap = new HashMap<>();
    }
    
    public void postTweet(int userId, int tweetId) {
        postMap.putIfAbsent(userId, new ArrayList<>());
        postMap.get(userId).add(new Tweet(userId, tweetId, timestamp++));
    }
    
    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> a.timestamp - b.timestamp);
        LinkedList<Integer> result = new LinkedList<>();
        
        for (int targetId : followMap.getOrDefault(userId, new HashSet<>())) {
            for (Tweet tweet : postMap.getOrDefault(targetId, new ArrayList<>())) {
                if (pq.size() < 10) {
                    pq.offer(tweet);
                } else if (tweet.timestamp > pq.peek().timestamp) {
                    pq.poll();
                    pq.offer(tweet);
                }
            }
        }
        for (Tweet tweet : postMap.getOrDefault(userId, new ArrayList<>())) {
            if (pq.size() < 10) {
                pq.offer(tweet);
            } else if (tweet.timestamp > pq.peek().timestamp) {
                pq.poll();
                pq.offer(tweet);
            }
        }
        int n = 0;
        while (!pq.isEmpty() && n < 10) {
            result.addFirst(pq.poll().tweetId);
        }

        return result;
    }
    
    public void follow(int followerId, int followeeId) { // follower follow followee
        followMap.putIfAbsent(followerId, new HashSet<>());
        followMap.get(followerId).add(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        Set<Integer> set = followMap.getOrDefault(followerId, new HashSet<>());
        if (set.contains(followeeId)) {
            set.remove(followeeId);
        }
    }
}