# 355. Design Twitter

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

T: O(mnlogmn)

S: O(mn)

```java
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)
```

```java
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 事先排出來最小的..

```java
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);
        }
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/design/355.-design-twitter.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.