# 0355. Design Twitter
###### tags: `Leetcode` `Medium` `Design`
Link: https://leetcode.com/problems/design-twitter/description/
## 思路
三个map分别存每个user发的tweetIds，每个tweetId发的时间，每个user follow的users
用一个额外的变量timeId记录每个tweet发的时间顺序
getNewsFeed里面我们用一个priority queue
把followee的tweetId都放进去 只留前10个 最后把他们都加进list
一开始加进list的时候其实是倒序 所以需要再花O(1)把它们倒过来
## Code

class Twitter {
    Map<Integer, List<Integer>> userToTweet;
    Map<Integer, Integer> tweetIdToTimeId;
    Map<Integer, Set<Integer>> userToFollow;
    int timeId = 0;

    public Twitter() {
        userToTweet = new HashMap<>();
        tweetIdToTimeId = new HashMap<>();
        userToFollow = new HashMap<>();
    }
    
    public void postTweet(int userId, int tweetId) {
        if(!userToTweet.containsKey(userId)) userToTweet.put(userId, new ArrayList<>());
        userToTweet.get(userId).add(tweetId);
        tweetIdToTimeId.put(tweetId, timeId++);
    }
    
    public List<Integer> getNewsFeed(int userId) {
        Queue<Integer> pq = new PriorityQueue<>((a,b)->(tweetIdToTimeId.get(a)-tweetIdToTimeId.get(b)));
        Set<Integer> followees = userToFollow.getOrDefault(userId, new HashSet<>());
        followees.add(userId);
        for(int followee:followees){
            for(int tweetId:userToTweet.getOrDefault(followee, new ArrayList<>())){
                pq.add(tweetId);
                if(pq.size()>10) pq.poll();
            }
        }
        List<Integer> temp = new ArrayList<>();
        while(!pq.isEmpty()){
            temp.add(pq.poll());
        }
        List<Integer> ans = new ArrayList<>();
        for(int i=temp.size()-1; i>=0; i--){
            ans.add(temp.get(i));
        }
        return ans;
    }
    
    public void follow(int followerId, int followeeId) {
        if(!userToFollow.containsKey(followerId)){
            userToFollow.put(followerId, new HashSet<>());
        }
        userToFollow.get(followerId).add(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        if(!userToFollow.containsKey(followerId)) return;
        userToFollow.get(followerId).remove(followeeId);
    }
}

from heapq import *
from collections import defaultdict, deque

class Twitter:

    def __init__(self):
        self.following = defaultdict(set)
        self.user_tweets = defaultdict(deque)
        self.time = 0
        
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.time += 1
        tweets = self.user_tweets[userId]
        tweets.append((self.time, tweetId))
        if len(tweets) > 10:
            tweets.popleft()

    def getNewsFeed(self, userId: int) -> List[int]:
        h = []
        h.extend(self.user_tweets[userId])
        heapify(h)
        for followeeId in self.following[userId]:
            tweets = self.user_tweets[followeeId]
            for i in range(len(tweets)-1, -1, -1):
                if len(h)<10:
                    heappush(h, tweets[i])
                else:
                    if h[0][0] < tweets[i][0]:
                        heappushpop(h, tweets[i])
                    else:
                        break
        return [heappop(h)[1] for _ in range(len(h))][::-1]

    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)
        

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)