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. Your design should support the following methods:



postTweet(userId, tweetId): Compose a new tweet.
getNewsFeed(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.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.



Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// 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.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

Difficulty: interview

Starter code:

class Twitter:
    def __init__(self):
        """
        Initialize your data structure here.
        """
    def postTweet(self, userId: int, tweetId: int) -> None:
        """
        Compose a new tweet.
        """
    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.
        """
    def follow(self, followerId: int, followeeId: int) -> None:
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        """
    def unfollow(self, followerId: int, followeeId: int) -> None:
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        """
# 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)

Solutions:
from collections import defaultdict, deque
 from heapq import merge
 from itertools import islice
 
 class Twitter:
 
     def __init__(self):
         """
         Initialize your data structure here.
         """
         self.id2tweets = defaultdict(deque)
         self.id2follows = defaultdict(set)
         self.uid = 0
 
     def postTweet(self, userId, tweetId):
         """
         Compose a new tweet.
         :type userId: int
         :type tweetId: int
         :rtype: void
         """
         self.id2tweets[userId].appendleft((self.uid, tweetId))
         self.uid -= 1
         #print(userId, 'POST', tweetId, self.id2tweets)
 
     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]
         """
         #print('GET', userId, self.id2tweets, self.id2follows)
         tweets = heapq.merge(*(self.id2tweets[u] for u in self.id2follows[userId] | {userId}))
         return [tweet_id for _, tweet_id in islice(tweets, 10)]
 
     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
         """
         self.id2follows[followerId].add(followeeId)
         #print(followerId, 'FOLLOW', followeeId, self.id2follows)
 
     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.id2follows[followerId].discard(followeeId)
         #print(followerId, 'UNFOLLOW', followeeId, self.id2follows)
 
 # 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)

class Twitter(object):
 
     def __init__(self):
         self.timer = itertools.count(step=-1)
         self.tweets = collections.defaultdict(collections.deque)
         self.followees = collections.defaultdict(set)
 
     def postTweet(self, userId, tweetId):
         self.tweets[userId].appendleft((next(self.timer), tweetId))
 
     def getNewsFeed(self, userId):
         tweets = heapq.merge(*(self.tweets[u] for u in self.followees[userId] | {userId}))
         return [t for _, t in itertools.islice(tweets, 10)]
 
     def follow(self, followerId, followeeId):
         self.followees[followerId].add(followeeId)
 
     def unfollow(self, followerId, followeeId):
         self.followees[followerId].discard(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)


class User:
     
     def __init__(self,uid):
         self.uid=uid
         self.news =[]
         self.followee=set()
         
     def follow(self,followId):
         self.followee.add(followId)
     
     def unfollow(self,followId):
         if followId in self.followee:
             self.followee.remove(followId)
             
     def post(self,newsId):
         
         self.news.append(newsId)
         
 class Twitter:
 
     def __init__(self):
         """
         Initialize your data structure here.
         """
         self.user={}
         self.tweet={}
         self.tweetOrder=0
         
 
     def postTweet(self, userId, tweetId):
         """
         Compose a new tweet.
         :type userId: int
         :type tweetId: int
         :rtype: void
         """
         if userId not in self.user:
             self.user[userId]=User(userId)
         self.tweet[self.tweetOrder]=tweetId
         self.user[userId].post(self.tweetOrder)
         self.tweetOrder+=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]
         """
         if userId not in self.user:
             return []
         newsFeed=[]
         relatedUser=[self.user[userId]]+[self.user[id] for id in self.user[userId].followee]
         for person in relatedUser:
             length=len(person.news)
             for i in range(min(10,length)):
                 if len(newsFeed)<10:
                     heapq.heappush(newsFeed,person.news[length-1-i])
                 else:
                     heapq.heappushpop(newsFeed,person.news[length-1-i])
         res=[]
         while newsFeed:
             res.append(heapq.heappop(newsFeed))
         return [self.tweet[tweetOrder] for tweetOrder in res[::-1]]
         
 
     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:
             if followerId not in self.user:
                 self.user[followerId]=User(followerId)
             if followeeId not in self.user:
                 self.user[followeeId]=User(followeeId)
             self.user[followerId].follow(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
         """
         if followerId in self.user and followeeId in self.user:
             self.user[followerId].unfollow(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:
 
     def __init__(self):
         """
         Initialize your data structure here.
         """
         self.users = {}
         self.twitters = {}
         self.time = 0
 
     def postTweet(self, userId, tweetId):
         """
         Compose a new tweet.
         :type userId: int
         :type tweetId: int
         :rtype: void
         """
         if userId in self.twitters:
             self.twitters[userId].append([-self.time, tweetId])
             self.time += 1
         else:
             self.twitters[userId] = [[-self.time, tweetId]]
             self.time+= 1
        
         if userId not in self.users:
             self.users[userId] = set([])
 
     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]
         """
         
         if userId not in self.users:
             return([])
             
         userIds = self.users[userId]
         
         if not userIds:
             userIds = set([])
         userIds.add(userId)
         newsArr = []
         for uId in userIds:
             if uId not in self.twitters:
                 newsArr.append([])
             else:
                 newsArr.append(self.twitters[uId][::-1])
         out = []
         heap = []
         for i in range(len(newsArr)):
             if newsArr[i]:
                 heapq.heappush(heap, [newsArr[i][0][0], newsArr[i][0][1], i, 0])
         while len(out) < 10:
             if len(heap) == 0:
                 break
             time,tId, arr, index = heapq.heappop(heap)
             out.append(tId)
             if index+1 < len(newsArr[arr]):
                 heapq.heappush(heap, [newsArr[arr][index+1][0],newsArr[arr][index+1][1],arr, index+1])
                 
         
         return([num for num in out])
         
 
     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 in self.users:
             self.users[followerId].add(followeeId)        
         else:
             self.users[followerId] = set([])
             self.users[followerId].add(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
         """
         if followerId in self.users:
             if followeeId in self.users[followerId]:
                 self.users[followerId].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)

from heapq import heappush, heappop
 
 class Twitter:
     time_stamp = 0
     class User:
         def __init__(self, user_id):
             self.user_id = user_id
             self.followers = set()
             self.follow(user_id)
             self.tweet_head = None
             
         def follow(self, follower_id):
             self.followers.add(follower_id)
         
         def unfollow(self, follower_id):
             if follower_id in self.followers:
                 self.followers.remove(follower_id)
                 
         def post(self, new_tweet):
             nxt = self.tweet_head
             self.tweet_head, new_tweet.next = new_tweet, nxt
     
     class Tweet:
         def __init__(self, tw_id, ts):
             self.tweet_id = tw_id
             self.timestamp = ts
             self.next = None            
     
     def __init__(self):
         """
         Initialize your data structure here.
         """
         self.user_map = {}
         
 
     def postTweet(self, userId, tweetId):
         """
         Compose a new tweet.
         :type userId: int
         :type tweetId: int
         :rtype: void
         """
         if userId not in self.user_map:
             self.user_map[userId] = self.User(userId)
         user = self.user_map[userId]
         user.post(self.Tweet(tweetId, self.time_stamp))
         self.time_stamp += 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]
         """
         ans, pq = [], []
         if userId not in self.user_map:
             return ans
         user = self.user_map[userId]
         for follower in user.followers:
             tw = self.user_map[follower].tweet_head
             if tw:
                 heappush(pq, (-tw.timestamp, tw))
         n = 10
         while pq and n > 0:
             ts, tw = heappop(pq)
             ans.append(tw.tweet_id)
             nxt = tw.next
             if nxt:                
                 heappush(pq, (-nxt.timestamp, nxt))
             n -= 1
         return ans
             
 
     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 not in self.user_map:
             self.user_map[followerId] = self.User(followerId)            
         if followeeId not in self.user_map:
             self.user_map[followeeId] = self.User(followeeId)
         self.user_map[followerId].follow(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
         """
         if followerId not in self.user_map or followeeId not in self.user_map or followerId == followeeId:
             return
         self.user_map[followerId].unfollow(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 queue
 import heapq
     
 class Twitter:
     def _addUser(self, userId):
         if userId not in self.tweets:
             self.tweets[userId] = []
         if userId not in self.graph:
             self.graph[userId] = set([userId])
 
     def __init__(self):
         """
         Initialize your data structure here.
         """
         self.graph = {}
         self.tweets = {}
         self.now = 0
         
 
     def postTweet(self, userId, tweetId):
         """
         Compose a new tweet.
         :type userId: int
         :type tweetId: int
         :rtype: void
         """
         self.now -= 1
         self._addUser(userId)
         self.tweets[userId].append((self.now, tweetId))
         self.follow(userId, userId)
         
 
     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]
         """
         self._addUser(userId)
         h = []
         for followee in self.graph[userId]:
             numtweets = len(self.tweets[followee])
             if numtweets > 10:
                 for tweet in self.tweets[followee][numtweets - 10:]:
                     h.append(tweet)
             else:
                 for tweet in self.tweets[followee]:
                     h.append(tweet)
         heapq.heapify(h)
         lst = []
         while len(h) > 0 and len(lst) < 10:
             elem = heapq.heappop(h)
             lst.append(elem[1])
         return lst
                 
 
     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
         """
         self._addUser(followerId)
         self._addUser(followeeId)
         self.graph[followerId].add(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._addUser(followerId)
         if followeeId != followerId:
             self.graph[followerId].discard(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)

## Basic Ideas: Two hashmap + PriorityQueue
 ##     tweet_dict. id -> tweet_list
 ##     follow_dict: id -> id set
 ##
 ## Notice: people may follow themselves
 ##
 ## Assumption: people tweet with post id always grows
 ##
 ## Complexity: getNewsFeed
 ##       Time O(n*log(n)) Space O(n). n = total tweets involved
 import collections, copy
 class Twitter:
 
     def __init__(self):
         """
         Initialize your data structure here.
         """
         self.id = 0
         self.tweet_dict = collections.defaultdict(lambda: [])
         self.follow_dict = collections.defaultdict(lambda: set([]))
 
     def postTweet(self, userId, tweetId):
         """
         Compose a new tweet.
         :type userId: int
         :type tweetId: int
         :rtype: void
         """
         self.tweet_dict[userId].append((self.id, tweetId))
         self.id += 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]
         """
         q = []
         # min heap
         heapq.heapify(q)
         for (id, tweetId) in self.tweet_dict[userId]:
             heapq.heappush(q, (id, tweetId))
             if len(q) > 10: heapq.heappop(q)
         for followee in self.follow_dict[userId]:
             for (id, tweetId) in self.tweet_dict[followee]:
                 heapq.heappush(q, (id, tweetId))
                 if len(q) > 10: heapq.heappop(q)
         res = []
         while len(q) != 0:
             (id, tweetId) = heapq.heappop(q)
             res.insert(0, tweetId)
         return res
 
     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
         if followeeId not in self.follow_dict[followerId]:
             self.follow_dict[followerId].add(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
         """
         if followerId == followeeId: return
         if followeeId in self.follow_dict[followerId]:
             self.follow_dict[followerId].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)

class Twitter:
 
     def __init__(self):
         """
         Initialize your data structure here.
         """
         # e.g. [{"user1":"tweet1"}, {"user2":"tweet2"},...] - fast tweets access
         self.tweets = []
         
         # e.g. {"user1":[0,2,4,5], "user2":[1,3]} - fast user-tweets access
         self.userTweets = {}
         
         # e.g. {"user1":[0,1,2,3,4,5]}
         self.feeds = {}
         
         # e.g. {user2:[1]}
         self.followers = {}
         self.followees = {}
         # eg. {(user1,user2):True}
         self.relations = {}
 
     def postTweet(self, userId, tweetId):
         """
         Compose a new tweet.
         :type userId: int
         :type tweetId: int
         :rtype: void
         """
         # create tweet
         self.tweets.append({"userId":userId, "tweetId":tweetId})
         lastIndex = len(self.tweets)-1
         
         # create user tweet list
         if userId not in self.userTweets:
             self.userTweets[userId] = []
         self.userTweets[userId].append(lastIndex)
         
         # update feeds
         followers = self.followers.get(userId, [])
         for followerId in [userId]+followers:
             # add tweet, reverse sort, cut recent 10
             self.feeds[followerId] = ([tweetId] + self.feeds.get(followerId, []))[:10]
 
     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]
         """
         return self.feeds.get(userId, [])
         
 
     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
         """        
         # no-op case
         if (followerId, followeeId) in self.relations or followerId == followeeId:
             return
         else:
             self.relations[(followerId, followeeId)] = True
         
         #  add follower, create new list if not exist
         if followeeId not in self.followers:
             self.followers[followeeId] = []
         self.followers[followeeId].append(followerId)
         
         # add followee
         if followerId not in self.followees:
             self.followees[followerId] = []
         self.followees[followerId].append(followeeId)
          
         # update user's feed
         self.updateFeed(followerId)        
 
     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
         """
         # no-op case
         if (followerId, followeeId) not in self.relations:
             return
         else:
             del self.relations[(followerId, followeeId)]
         
         # remove relation        
         self.followers[followeeId].remove(followerId)
         self.followees[followerId].remove(followeeId)
         
         # skip update if followee didn't tweet
         if not self.userTweets.get(followeeId, []):
             return
         
         # full rebuild feed
         self.updateFeed(followerId)
         
     def updateFeed(self, userId):
         # full rebuild feed
         followers = self.followees.get(userId, [])
         indexes = []
         for followeeId in [userId]+followers:
             if self.userTweets.get(followeeId, []):
                 indexes += self.userTweets.get(followeeId, [])
                 indexes = sorted(indexes, reverse=True)[0:10]        
                 
         # set new feed
         self.feeds[userId] = [self.tweets[idx]['tweetId'] for idx in indexes]     
         
 
 # 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)