# Design Twitter
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-twitter)
Canonical: https://scaleengineer.com/dsa/problems/design-twitter
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Hash Table, Linked List, Heap (Priority Queue)
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [Coupang](https://scaleengineer.com/companies/coupang), [X](https://scaleengineer.com/companies/x)
---
## Problem
Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the `10` most recent tweets in the user's news feed.

Implement the `Twitter` class:

* `Twitter()` Initializes your twitter object.
* `void postTweet(int userId, int tweetId)` Composes a new tweet with ID `tweetId` by the user `userId`. Each call to this function will be made with a unique `tweetId`.
* `List<Integer> getNewsFeed(int userId)` Retrieves 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 themself. Tweets must be **ordered from most recent to least recent**.
* `void follow(int followerId, int followeeId)` The user with ID `followerId` started following the user with ID `followeeId`.
* `void unfollow(int followerId, int followeeId)` The user with ID `followerId` started unfollowing the user with ID `followeeId`.

**Example 1:**

**Input**
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
**Output**
[null, null, [5], null, null, [6, 5], null, [5]]

**Explanation**
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> [5]. return [5]
twitter.follow(1, 2);    // User 1 follows user 2.
twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.unfollow(1, 2);  // User 1 unfollows user 2.
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.

**Constraints:**

* `1 <= userId, followerId, followeeId <= 500`
* `0 <= tweetId <= 104`
* All the tweets have **unique** IDs.
* At most `3 * 104` calls will be made to `postTweet`, `getNewsFeed`, `follow`, and `unfollow`.
* A user cannot follow himself.

# Approaches
## Brute-force Sorting
This is a straightforward approach where we simulate the process directly. For `getNewsFeed`, we gather all tweets from the user and the users they follow into a single list, sort this list by time, and then take the 10 most recent ones.
**Time:** `postTweet`, `follow`, `unfollow`: O(1)
`getNewsFeed`: O(N log N), where N is the total number of tweets from the user and their followees. Sorting dominates the complexity. · **Space:** O(U + T), where U is the number of users and T is the total number of tweets stored. `getNewsFeed` also requires O(N) temporary space for the list of candidate tweets, where N is the number of tweets from the user and their followees.
**Pros:** Simple to understand and implement.; `postTweet`, `follow`, and `unfollow` operations are very fast, typically O(1).
**Cons:** `getNewsFeed` is very inefficient. Its performance degrades significantly as the total number of tweets (`N`) from the user and their followees increases.
### Explanation
We use a `Map` to store follow relationships (`userId -> Set<followeeId>`) and another `Map` to store each user's tweets (`userId -> List<Tweet>`). A global timestamp is used to record the post time of each tweet, ensuring chronological order. `postTweet` adds a new tweet with the current timestamp to the user's tweet list. `follow` and `unfollow` simply update the follow-relationship map. The main logic is in `getNewsFeed`. It first identifies all relevant users (the user themselves and their followees). It then iterates through these users, collecting all their tweets into a temporary list. This list is then sorted in descending order based on the tweet's timestamp. Finally, the IDs of the first 10 tweets from the sorted list are returned.

```java
class Twitter {
    private static int timestamp = 0;
    private Map<Integer, Set<Integer>> userFollows;
    private Map<Integer, List<Tweet>> userTweets;

    private class Tweet {
        int id;
        int time;
        public Tweet(int id, int time) {
            this.id = id;
            this.time = time;
        }
    }

    public Twitter() {
        userFollows = new HashMap<>();
        userTweets = new HashMap<>();
    }
    
    public void postTweet(int userId, int tweetId) {
        userTweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new Tweet(tweetId, timestamp++));
    }
    
    public List<Integer> getNewsFeed(int userId) {
        List<Tweet> allTweets = new ArrayList<>();
        
        // Add user's own tweets
        if (userTweets.containsKey(userId)) {
            allTweets.addAll(userTweets.get(userId));
        }
        
        // Add followees' tweets
        Set<Integer> followees = userFollows.get(userId);
        if (followees != null) {
            for (int followeeId : followees) {
                if (userTweets.containsKey(followeeId)) {
                    allTweets.addAll(userTweets.get(followeeId));
                }
            }
        }
        
        // Sort all collected tweets by time descending
        allTweets.sort((a, b) -> b.time - a.time);
        
        List<Integer> newsFeed = new ArrayList<>();
        for (int i = 0; i < Math.min(10, allTweets.size()); i++) {
            newsFeed.add(allTweets.get(i).id);
        }
        
        return newsFeed;
    }
    
    public void follow(int followerId, int followeeId) {
        userFollows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        if (userFollows.containsKey(followerId) && followerId != followeeId) {
            userFollows.get(followerId).remove(followeeId);
        }
    }
}
```
### Algorithm
- Maintain a map `userFollows` for follow/unfollow relationships (`Map<Integer, Set<Integer>>`).
- Maintain a map `userTweets` to store a list of `Tweet` objects for each user (`Map<Integer, List<Tweet>>`). A `Tweet` object contains its ID and a timestamp.
- Use a global, static, incrementing `timestamp` for each new tweet to ensure chronological order.
- For `getNewsFeed(userId)`:
  1. Create an empty list `candidateTweets`.
  2. Add all of `userId`'s own tweets to `candidateTweets`.
  3. For each `followeeId` that `userId` follows, add all of their tweets to `candidateTweets`.
  4. Sort `candidateTweets` based on timestamp in descending order.
  5. Return the IDs of the first 10 tweets in the sorted list.

## Selection with a Min-Heap
This approach improves upon the brute-force method by avoiding a full sort. Instead of sorting all candidate tweets, we iterate through them once and use a min-heap of a fixed size (10) to keep track of the 10 most recent tweets seen so far.
**Time:** `postTweet`, `follow`, `unfollow`: O(1)
`getNewsFeed`: O(N), where N is the total number of candidate tweets. We iterate through N tweets, and each heap operation is O(log K) where K=10, so it's effectively O(N). · **Space:** O(U + T) for storing all data, where U is the number of users and T is the total number of tweets. The heap in `getNewsFeed` uses O(K) space, where K=10, which is constant O(1).
**Pros:** More efficient than full sorting for `getNewsFeed`.; Avoids creating a large intermediate list and sorting it.
**Cons:** Still requires iterating through every single tweet of the user and their followees, which can be slow if there are many tweets in total.
### Explanation
The data structures for storing user and tweet data remain the same as the brute-force approach. The `getNewsFeed` method is optimized. It initializes a min-heap that orders tweets by their timestamp (oldest on top). It iterates through all tweets from the user and their followees. For each tweet, it's compared with the top element of the heap. If the heap has fewer than 10 tweets, the current tweet is added. If the heap is full (size 10) and the current tweet is more recent than the oldest tweet in the heap (the heap's peek), the oldest is removed, and the new one is added. After checking all candidate tweets, the heap contains the 10 most recent ones. These are then extracted and returned in the correct (most recent first) order.

```java
class Twitter {
    private static int timestamp = 0;
    private Map<Integer, Set<Integer>> userFollows;
    private Map<Integer, List<Tweet>> userTweets;

    private class Tweet {
        int id;
        int time;
        public Tweet(int id, int time) {
            this.id = id;
            this.time = time;
        }
    }

    public Twitter() {
        userFollows = new HashMap<>();
        userTweets = new HashMap<>();
    }
    
    public void postTweet(int userId, int tweetId) {
        userTweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new Tweet(tweetId, timestamp++));
    }
    
    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<Tweet> minHeap = new PriorityQueue<>((a, b) -> a.time - b.time);
        
        Set<Integer> relevantUsers = new HashSet<>();
        relevantUsers.add(userId);
        if (userFollows.containsKey(userId)) {
            relevantUsers.addAll(userFollows.get(userId));
        }
        
        for (int uId : relevantUsers) {
            if (userTweets.containsKey(uId)) {
                for (Tweet tweet : userTweets.get(uId)) {
                    minHeap.offer(tweet);
                    if (minHeap.size() > 10) {
                        minHeap.poll();
                    }
                }
            }
        }
        
        LinkedList<Integer> newsFeed = new LinkedList<>();
        while (!minHeap.isEmpty()) {
            newsFeed.addFirst(minHeap.poll().id);
        }
        
        return newsFeed;
    }
    
    public void follow(int followerId, int followeeId) {
        userFollows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        if (userFollows.containsKey(followerId) && followerId != followeeId) {
            userFollows.get(followerId).remove(followeeId);
        }
    }
}
```
### Algorithm
- Use the same data structures as the brute-force approach.
- For `getNewsFeed(userId)`:
  1. Initialize a min-heap `topTenTweets` of size at most 10, ordered by timestamp (oldest on top).
  2. Collect all relevant users (the user and their followees).
  3. Iterate through every tweet of every relevant user.
  4. For each `tweet`:
     - If `topTenTweets.size() < 10`, add the `tweet`.
     - Else if the current `tweet` is more recent than the oldest tweet in the heap (`topTenTweets.peek()`), remove the top element and add the new `tweet`.
  5. Extract all tweets from the heap and reverse them to get the descending order of time. Return their IDs.

## K-Way Merge with a Max-Heap
This is the most efficient approach, especially for users who follow many others. It treats the problem as merging `k` sorted lists, where each list is a user's timeline of tweets (which are naturally sorted by time). A max-heap is used to efficiently find the next most recent tweet across all these timelines.
**Time:** `postTweet`, `follow`, `unfollow`: O(1)
`getNewsFeed`: O(M log k + k), where `k` is the number of users followed (plus one) and `M` is the number of tweets to retrieve (10). This is because we build a heap of size `k` (O(k log k), or O(k) with heapify) and then perform `M` poll/offer operations (each O(log k)). · **Space:** O(U + T) for storing all data, where U is the number of users and T is the total number of tweets. The heap in `getNewsFeed` uses O(k) space, where k is the number of users followed plus one.
**Pros:** Highly efficient `getNewsFeed`. The complexity depends on the number of people followed (`k`), not the total number of tweets (`N`).; Very scalable for systems where users post and follow frequently.
**Cons:** More complex to implement due to the need to manage heap state (including user and index pointers).
### Explanation
We maintain the same data structures for follows and tweets. Each user's tweet list is inherently sorted by time. The `getNewsFeed` method works by initializing a max-heap. Instead of putting all tweets into the heap, we only put the *most recent* tweet from the user and each of their followees. The heap stores not just the tweet, but also metadata: which user it came from and its index in that user's tweet list. The process then becomes:
1. Poll the most recent tweet from the heap. Add it to our result list.
2. Using the metadata, find the *next* most recent tweet from the *same user* whose tweet we just polled.
3. Add this next tweet to the heap.
We repeat this process 10 times to get the 10 most recent tweets overall. This avoids ever looking at tweets that are too old to make it into the top 10.

```java
class Twitter {
    private static int timestamp = 0;
    private Map<Integer, Set<Integer>> userFollows;
    private Map<Integer, List<Tweet>> userTweets;

    private class Tweet {
        int id;
        int time;
        public Tweet(int id, int time) {
            this.id = id;
            this.time = time;
        }
    }

    public Twitter() {
        userFollows = new HashMap<>();
        userTweets = new HashMap<>();
    }

    public void postTweet(int userId, int tweetId) {
        userTweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new Tweet(tweetId, timestamp++));
    }

    public List<Integer> getNewsFeed(int userId) {
        // Max-heap stores arrays: {time, tweetId, userId, tweetIndex}
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);

        Set<Integer> relevantUsers = new HashSet<>();
        relevantUsers.add(userId);
        if (userFollows.containsKey(userId)) {
            relevantUsers.addAll(userFollows.get(userId));
        }

        for (int uId : relevantUsers) {
            if (userTweets.containsKey(uId) && !userTweets.get(uId).isEmpty()) {
                List<Tweet> tweets = userTweets.get(uId);
                int tweetIndex = tweets.size() - 1;
                Tweet tweet = tweets.get(tweetIndex);
                maxHeap.offer(new int[]{tweet.time, tweet.id, uId, tweetIndex});
            }
        }

        List<Integer> newsFeed = new ArrayList<>();
        while (!maxHeap.isEmpty() && newsFeed.size() < 10) {
            int[] top = maxHeap.poll();
            newsFeed.add(top[1]);
            
            int uId = top[2];
            int tweetIndex = top[3];
            
            if (tweetIndex > 0) {
                int nextTweetIndex = tweetIndex - 1;
                Tweet nextTweet = userTweets.get(uId).get(nextTweetIndex);
                maxHeap.offer(new int[]{nextTweet.time, nextTweet.id, uId, nextTweetIndex});
            }
        }
        
        return newsFeed;
    }

    public void follow(int followerId, int followeeId) {
        userFollows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        if (userFollows.containsKey(followerId) && followerId != followeeId) {
            userFollows.get(followerId).remove(followeeId);
        }
    }
}
```
### Algorithm
- Use the same data structures as previous approaches.
- For `getNewsFeed(userId)`:
  1. Initialize a max-heap. The heap will store tuples of `(timestamp, tweetId, userId, tweetIndex)` to keep track of tweet's origin.
  2. Identify the set of relevant users (`k` users in total: the user and their followees).
  3. For each of the `k` users, if they have any tweets, add their most recent tweet's information to the max-heap.
  4. Initialize an empty list for the news feed result.
  5. Loop up to 10 times (or until the heap is empty):
     - Poll the top element (the globally most recent tweet) from the heap.
     - Add its `tweetId` to the result list.
     - From the polled element's metadata (`userId` and `tweetIndex`), find the next most recent tweet from that same user.
     - If it exists, add it to the heap.
  6. Return the result list.

# Solutions
### Java

```java
class Twitter { private Map < Integer , List < Integer >> userTweets ; private Map < Integer , Set < Integer >> userFollowing ; private Map < Integer , Integer > tweets ; private int time ; /** Initialize your data structure here. */ public Twitter () { userTweets = new HashMap <>(); userFollowing = new HashMap <>(); tweets = new HashMap <>(); time = 0 ; } /** Compose a new tweet. */ public void postTweet ( int userId , int tweetId ) { userTweets . computeIfAbsent ( userId , k -> new ArrayList <>()). add ( tweetId ); tweets . put ( tweetId , ++ time ); } /** * 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 ) { Set < Integer > following = userFollowing . getOrDefault ( userId , new HashSet <>()); Set < Integer > users = new HashSet <>( following ); users . add ( userId ); PriorityQueue < Integer > pq = new PriorityQueue <>( 10 , ( a , b ) -> ( tweets . get ( b ) - tweets . get ( a ))); for ( Integer u : users ) { List < Integer > userTweet = userTweets . get ( u ); if ( userTweet != null && ! userTweet . isEmpty ()) { for ( int i = userTweet . size () - 1 , k = 10 ; i >= 0 && k > 0 ; -- i , -- k ) { pq . offer ( userTweet . get ( i )); } } } List < Integer > res = new ArrayList <>(); while (! pq . isEmpty () && res . size () < 10 ) { res . add ( pq . poll ()); } return res ; } /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ public void follow ( int followerId , int followeeId ) { userFollowing . computeIfAbsent ( followerId , k -> new HashSet <>()). add ( followeeId ); } /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ public void unfollow ( int followerId , int followeeId ) { userFollowing . computeIfAbsent ( followerId , k -> new HashSet <>()). 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); */ ////////////////// public class Design_Twitter { class Twitter { Map < Integer , Set < Integer >> userToFollowingsMap ; // user to who he/she is following Map < Integer , PriorityQueue < Tweet >> userToTweetsMap ; SeqTime seqTime ; /** Initialize your data structure here. */ public Twitter () { userToFollowingsMap = new HashMap <>(); userToTweetsMap = new HashMap <>(); seqTime = new SeqTime (); } /** Compose a new tweet. */ public void postTweet ( int userId , int tweetId ) { // init the friend map Tweet tweet = new Tweet ( userId , tweetId , seqTime . getTime ()); Set < Integer > followings = userToFollowingsMap . getOrDefault ( userId , new HashSet <>()); followings . add ( userId ); // 自己是自己的friend，看自己的twitt userToFollowingsMap . put ( userId , followings ); // save the tweet into the tweetmap PriorityQueue < Tweet > tweets = userToTweetsMap . getOrDefault ( userId , new PriorityQueue < Tweet >( ( a , b ) -> b . time - a . time )); tweets . offer ( tweet ); userToTweetsMap . put ( userId , tweets ); } /** 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 ) { Set < Integer > followings = userToFollowingsMap . get ( userId ); if ( followings == null || followings . isEmpty ()) { return new ArrayList <>(); } Map < Integer , PriorityQueue < Tweet >> tweetList = new HashMap <>(); for ( Integer following : followings ) { PriorityQueue < Tweet > tweets = userToTweetsMap . get ( following ); PriorityQueue < Tweet > top10List = getTop10Tweets ( tweets ); Iterator < Tweet > it = top10List . iterator (); if (! top10List . isEmpty ()) { tweetList . put ( following , top10List ); } } return mergeTweets ( tweetList ); } /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ public void follow ( int followerId , int followeeId ) { Set < Integer > followings = userToFollowingsMap . getOrDefault ( followerId , new HashSet <>()); followings . add ( followerId ); // self follow followings . add ( followeeId ); userToFollowingsMap . put ( followerId , followings ); } /** 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 ; } Set < Integer > followings = userToFollowingsMap . getOrDefault ( followerId , new HashSet <>()); followings . remove ( followeeId ); userToFollowingsMap . put ( followerId , followings ); } private PriorityQueue < Tweet > getTop10Tweets ( PriorityQueue < Tweet > tweets ) { // most recent at top PriorityQueue < Tweet > top10Tweets = new PriorityQueue < Tweet >( ( a , b ) -> b . time - a . time ); for ( int i = 0 ; i < 10 ; i ++) { if ( tweets == null || tweets . isEmpty ()) { break ; } top10Tweets . offer ( tweets . poll ()); } // push back Iterator it = top10Tweets . iterator (); while ( it . hasNext ()) { tweets . offer (( Tweet ) it . next ()); } return top10Tweets ; } private List < Integer > mergeTweets ( Map < Integer , PriorityQueue < Tweet >> tweetLists ) { List < Integer > ans = new ArrayList <>(); PriorityQueue < Tweet > finalPQ = new PriorityQueue < Tweet >( ( a , b ) -> b . time - a . time ); for ( Integer userId : tweetLists . keySet ()) { PriorityQueue < Tweet > tweets = tweetLists . get ( userId ); Tweet top = tweets . poll (); //tweetLists.put(userId, tweets); finalPQ . offer ( top ); } int count = 0 ; while ( count < 10 && ! tweetLists . isEmpty ()) { // similar to question for LC281 k-iterators Tweet curr = finalPQ . poll (); ans . add ( curr . twitterId ); PriorityQueue < Tweet > nextTweetList = tweetLists . get ( curr . userId ); if (! nextTweetList . isEmpty ()) { finalPQ . offer ( nextTweetList . poll ()); } else { tweetLists . remove ( curr . userId ); } count += 1 ; } return ans ; } } class Tweet { int twitterId ; int userId ; int time ; public Tweet ( int userId , int twitterId , int time ) { this . userId = userId ; this . twitterId = twitterId ; this . time = time ; } } class SeqTime { int time ; public SeqTime () { time = 0 ; } public int getTime () { int curTime = time ; time += 1 ; // @note: possible overflow for int return curTime ; } } /** * 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); */ }
```

### Python

```python
''' heapq.nlargest(n, iterable, key=None) is used to find the n largest elements from a dataset defined by iterable. people = [ {"name": "Alice", "age": 30}, {"name": "Bob", "age": 25}, {"name": "Carol", "age": 40}, {"name": "Dave", "age": 20} ] # Using nlargest to find the two oldest people oldest_two = heapq.nlargest(2, people, key=lambda person: person["age"]) print(oldest_two) # Output: [{'name': 'Carol', 'age': 40}, {'name': 'Alice', 'age': 30}] ''' from collections import defaultdict from heapq import nlargest from typing import List class Twitter : def __init__ ( self ): """ Initialize your data structure here. """ self . user_tweets = defaultdict ( list ) self . user_following = defaultdict ( set ) self . tweet_time = defaultdict ( int ) # id => timestamp self . time = 0 def postTweet ( self , userId : int , tweetId : int ) -> None : """ Compose a new tweet. """ self . time += 1 self . user_tweets [ userId ]. append ( tweetId ) self . tweet_time [ tweetId ] = self . time def getNewsFeed ( self , userId : int ) -> List [ int ]: """ 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. """ following = self . user_following [ userId ] users = set ( following ) users . add ( userId ) # should see my own tweets too tweets = [ self . user_tweets [ u ][:: - 1 ][: 10 ] for u in users ] # Get the 10 most recent tweets ''' unconventional way to flatten a list of lists into a single list: lists = [[1, 2, 3], [4, 5], [6]] flattened = sum(lists, []) print(flattened) # Output: [1, 2, 3, 4, 5, 6] or, another way getting flattened tweets: flattened_tweets = [tweet for each_user_tweets in tweets for tweet in each_user_tweets] ''' tweets = sum ( tweets , []) return nlargest ( 10 , tweets , key = lambda tweet : self . tweet_time [ tweet ]) def follow ( self , followerId : int , followeeId : int ) -> None : """ Follower follows a followee. If the operation is invalid, it should be a no-op. """ self . user_following [ followerId ]. add ( followeeId ) def unfollow ( self , followerId : int , followeeId : int ) -> None : """ Follower unfollows a followee. If the operation is invalid, it should be a no-op. """ following = self . user_following [ followerId ] if followeeId in following : following . remove ( followeeId ) # Your Twitter object will be instantiated and called as such: # obj = Twitter() # obj.postTweet(userId,tweetId) # param_2 = obj.getNewsFeed(userId) # obj.follow(followerId,followeeId) # obj.unfollow(followerId,followeeId) ############ import heapq class Twitter ( object ): def __init__ ( self ): """ Initialize your data structure here. """ self . ts = 0 self . tweets = collections . defaultdict ( list ) self . friendship = collections . defaultdict ( set ) def postTweet ( self , userId , tweetId ): """ Compose a new tweet. :type userId: int :type tweetId: int :rtype: void """ tInfo = self . ts , tweetId , userId , len ( self . tweets [ userId ]) self . tweets [ userId ]. append ( tInfo ) self . ts -= 1 def getNewsFeed ( self , userId ): """ 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. :type userId: int :rtype: List[int] """ ret = [] heap = [] if self . tweets [ userId ]: heapq . heappush ( heap , self . tweets [ userId ][ - 1 ]) for followeeId in self . friendship [ userId ]: if self . tweets [ followeeId ]: heapq . heappush ( heap , self . tweets [ followeeId ][ - 1 ]) cnt = 10 while heap and cnt > 0 : # not using nlargest() _ , tid , uid , idx = heapq . heappop ( heap ) ret . append ( tid ) if idx > 0 : heapq . heappush ( heap , self . tweets [ uid ][ idx - 1 ]) cnt -= 1 return ret def follow ( self , followerId , followeeId ): """ Follower follows a followee. If the operation is invalid, it should be a no-op. :type followerId: int :type followeeId: int :rtype: void """ if followerId == followeeId : return self . friendship [ followerId ] |= { followeeId } def unfollow ( self , followerId , followeeId ): """ Follower unfollows a followee. If the operation is invalid, it should be a no-op. :type followerId: int :type followeeId: int :rtype: void """ self . friendship [ followerId ] -= { followeeId } # Your Twitter object will be instantiated and called as such: # obj = Twitter() # obj.postTweet(userId,tweetId) # param_2 = obj.getNewsFeed(userId) # obj.follow(followerId,followeeId) # obj.unfollow(followerId,followeeId)
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/design-twitter/ // Time: // * Twitter: O(1) // * getNewsFeed: O(F) // * follow: O(1) // * unfollow: O(1) // Space: O(F + R) where F is number of feeds, R is count of follower-followee relationships. class Twitter { private: deque < pair < int , int >> feeds ; unordered_map < int , unordered_set < int >> followerToFollowee ; public: Twitter () {} void postTweet ( int userId , int tweetId ) { feeds . push_front ( make_pair ( userId , tweetId )); } vector < int > getNewsFeed ( int userId ) { vector < int > v ; auto it = feeds . begin (); auto & followees = followerToFollowee [ userId ]; int cnt = 0 ; while ( it != feeds . end () && cnt < 10 ) { int posterId = it -> first ; if ( posterId == userId || followees . find ( posterId ) != followees . end ()) { v . push_back ( it -> second ); ++ cnt ; } ++ it ; } return v ; } void follow ( int followerId , int followeeId ) { if ( followerId == followeeId ) return ; followerToFollowee [ followerId ]. insert ( followeeId ); } void unfollow ( int followerId , int followeeId ) { if ( followerId == followeeId ) return ; followerToFollowee [ followerId ]. erase ( followeeId ); } };
```