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 (If total number of tweets in news feed is less than 10, then return all). 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 1:
Input:
postTweet(1, 5);
getNewsFeed(1);
follow(1, 2);
postTweet(2, 6);
getNewsFeed(1);
unfollow(1, 2);
getNewsFeed(1);
Output:
[5]
[6, 5]
[5]
Explanation: 
postTweet(1,5): User 1 posts a new tweet (id=5)
getNewsFeed(1): Return a list with 1 tweet [5]
follow(1,2)   : User 1 follows user 2.
postTweet(2,6): User 2 posts a new tweet (id=6)
getNewsFeed(1): Return a list with 2 tweets 
[6,5]. One his own tweet and one followee's tweet
(sorted from most recent to least recent).
unfollow(1,2) : User 1 unfollows user 2
getNewsFeed(1): Return a list with 1 tweet [5],
because user 1 is no longer following anyone.
Example 2:
Input:
follow(1, 2);
postTweet(1, 3);
getNewsFeed(2);
Output:
[]
Explanation:
follow(1,2)   : User 1 follows user 2.
postTweet(1,3): User 1 posts a new tweet (id=3)
getNewsFeed(2): Return a list with 0 tweet [],
because user2 have no tweets and don't follow
anyone (user1 follows user 2 but user 2 don't
follow anyone)
Your Task:  
You don't need to read input or print anything. Your task is to design your data structure inside the class Twitter and complete the functions postTweet(), getNewsFeed(), follow(), unfollow(), and the constructor.
Constraints:
1 <= no. of queries <= 1000
1 <= userId, tweetId, followerId, followeeId <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Twitter:

    # Compose a new tweet

    def postTweet(self, userId: int, tweetId: int):

        # Code here

        

    # Retrieve the 10 most recent tweet ids as mentioned in question

    def getNewsFeed(self, userId: int):

        # Code here

        

    # Follower follows a followee. If the operation is invalid, it should be a no-op.

    def follow(self, followerId: int, followeeId: int):

        # Code here

        

    # Follower unfollows a followee. If the operation is invalid, it should be a no-op.

    def unfollow(self, followerId: int, followeeId: int):

        # Code here

Solutions:
from collections import defaultdict
import heapq

class Twitter:

	def __init__(self):
		self.count = 0
		self.tweetMap = defaultdict(list)
		self.followMap = defaultdict(set)

	def postTweet(self, userId: int, tweetId: int):
		self.tweetMap[userId].append([self.count, tweetId])
		self.count -= 1

	def getNewsFeed(self, userId: int):
		res = []
		minheap = []
		self.followMap[userId].add(userId)
		for followeeId in self.followMap[userId]:
			if followeeId in self.tweetMap:
				index = len(self.tweetMap[followeeId]) - 1
				(count, tweetId) = self.tweetMap[followeeId][index]
				minheap.append([count, tweetId, followeeId, index - 1])
		heapq.heapify(minheap)
		while minheap and len(res) < 10:
			(count, tweetId, followeeId, index) = heapq.heappop(minheap)
			res.append(tweetId)
			if index >= 0:
				(count, tweetId) = self.tweetMap[followeeId][index]
				heapq.heappush(minheap, [count, tweetId, followeeId, index - 1])
		return res

	def follow(self, followerId: int, followeeId: int):
		self.followMap[followerId].add(followeeId)

	def unfollow(self, followerId: int, followeeId: int):
		if followeeId in self.followMap[followerId]:
			self.followMap[followerId].remove(followeeId)


from collections import defaultdict

class Twitter:

	def __init__(self):
		self.followers = defaultdict(set)
		self.tweets = defaultdict(list)
		self.counter = 0

	def postTweet(self, userId: int, tweetId: int):
		self.counter += 1
		self.tweets[userId].append((self.counter, tweetId))

	def getNewsFeed(self, userId: int):
		ans = []
		for post in self.tweets[userId]:
			ans.append(post)
		for follower in self.followers[userId]:
			for post in self.tweets[follower]:
				ans.append(post)
		ans = sorted(ans, key=lambda x: x[0], reverse=True)
		final = []
		for a in ans[:10]:
			final.append(a[-1])
		return final

	def follow(self, followerId: int, followeeId: int):
		self.followers[followerId].add(followeeId)

	def unfollow(self, followerId: int, followeeId: int):
		if followeeId in self.followers[followerId]:
			self.followers[followerId].remove(followeeId)


import itertools
import collections
from collections import deque
from collections import defaultdict
import heapq

class Twitter:

	def __init__(self):
		self.timer = itertools.count(step=-1)
		self.tweets = collections.defaultdict(deque)
		self.followees = collections.defaultdict(set)

	def postTweet(self, userId: int, tweetId: int) -> None:
		self.tweets[userId].appendleft((next(self.timer), tweetId))
		if len(self.tweets[userId]) > 10:
			self.tweets[userId].pop()

	def getNewsFeed(self, userId: int):
		tweets = list(heapq.merge(*(self.tweets[followee] for followee in self.followees[userId] | {userId})))
		return [tweetId for (_, tweetId) in tweets[:10]]

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

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


from collections import defaultdict
import heapq as hp

class Twitter:

	def __init__(self):
		self.meFollows = defaultdict(list)
		self.currentUsers = dict()
		self.userTweets = defaultdict(list)
		self.postCount = 0

	def createUser(self, userId):
		self.currentUsers[userId] = True

	def postTweet(self, userId: int, tweetId: int):
		if userId in self.currentUsers:
			self.postCount += 1
			self.userTweets[userId].append([self.postCount, tweetId])
		else:
			self.createUser(userId)
			self.postTweet(userId, tweetId)

	def getNewsFeed(self, userId: int):
		N = 10
		if userId not in self.currentUsers:
			return []
		tweets = self.userTweets[userId][-1:-(N + 1):-1]
		hp.heapify(tweets)
		for ifollow in self.meFollows[userId]:
			for tempTweet in reversed(self.userTweets[ifollow]):
				if len(tweets) < N:
					hp.heappush(tweets, tempTweet)
				elif tempTweet[0] > tweets[0][0]:
					hp.heappushpop(tweets, tempTweet)
				else:
					break
		result = []
		while tweets:
			result.append(hp.heappop(tweets)[1])
		return reversed(result)

	def follow(self, followerId: int, followeeId: int):
		if followerId not in self.currentUsers:
			self.createUser(followerId)
		if followeeId not in self.currentUsers:
			self.createUser(followeeId)
		if followeeId not in self.meFollows[followerId]:
			self.meFollows[followerId].append(followeeId)

	def unfollow(self, followerId: int, followeeId: int):
		try:
			self.meFollows[followerId].remove(followeeId)
		except:
			pass


import heapq
from collections import defaultdict

class Twitter:

	def __init__(self):
		self.count = 1
		self.followD = defaultdict(set)
		self.tweet = defaultdict(list)

	def postTweet(self, userId: int, tweetId: int):
		self.tweet[userId].append([self.count, tweetId])
		self.count += 1

	def getNewsFeed(self, userId: int):
		self.followD[userId].add(userId)
		heap = []
		s = self.followD[userId]
		for i in s:
			t = self.tweet[i]
			for ele in t:
				heap.append([ele[0], ele[1]])
		heapq._heapify_max(heap)
		res = []
		while heap and len(res) < 10:
			p = heapq._heappop_max(heap)
			res.append(p[1])
		heap.clear()
		return res

	def follow(self, followerId: int, followeeId: int):
		self.followD[followerId].add(followeeId)

	def unfollow(self, followerId: int, followeeId: int):
		if followeeId in self.followD[followerId]:
			self.followD[followerId].remove(followeeId)


class Twitter:

	def __init__(self):
		self.dp = []
		self.f_data = dict()

	def postTweet(self, userId: int, tweetId: int):
		self.dp.append([userId, tweetId])

	def getNewsFeed(self, userId: int):
		if self.f_data.get(userId) == None:
			self.f_data[userId] = []
		return [x[1] for x in self.dp if x[0] in [userId, *self.f_data[userId]]][-10:][::-1]

	def follow(self, followerId: int, followeeId: int):
		if self.f_data.get(followerId) == None:
			self.f_data[followerId] = []
		self.f_data[followerId].append(followeeId)

	def unfollow(self, followerId: int, followeeId: int):
		self.f_data[followerId].remove(followeeId)


from collections import defaultdict
import heapq

class Twitter:

	def __init__(self):
		self.count = 0
		self.follower = defaultdict(set)
		self.user_tweet = defaultdict(list)

	def postTweet(self, userID: int, tweetID: int):
		self.user_tweet[userID].append([self.count, tweetID])
		self.count -= 1

	def getNewsFeed(self, userID: int):
		self.follower[userID].add(userID)
		res = []
		hp = []
		for f in self.follower[userID]:
			if f in self.user_tweet:
				index = len(self.user_tweet[f]) - 1
				(count, tweet) = self.user_tweet[f][index]
				heapq.heappush(hp, (count, tweet, f, index - 1))
		while hp and len(res) < 10:
			(count, tweet, f, index) = heapq.heappop(hp)
			res.append(tweet)
			if index >= 0:
				(count, tweet) = self.user_tweet[f][index]
				heapq.heappush(hp, (count, tweet, f, index - 1))
		return res

	def follow(self, followerID: int, followeeID: int):
		self.follower[followerID].add(followeeID)

	def unfollow(self, followerID: int, followeeID: int):
		if followeeID in self.follower[followerID]:
			self.follower[followerID].remove(followeeID)


from collections import defaultdict
import heapq

class Twitter:

	def __init__(self):
		self.timer = 0
		self.tweetMap = defaultdict(list)
		self.followerslist = defaultdict(set)

	def postTweet(self, userId: int, tweetId: int):
		self.tweetMap[userId].append([self.timer, tweetId])
		self.timer -= 1

	def getNewsFeed(self, userId: int):
		tweets = []
		heap = []
		self.followerslist[userId].add(userId)
		for followeeId in self.followerslist[userId]:
			if followeeId in self.tweetMap:
				index = len(self.tweetMap[followeeId]) - 1
				(timer, tweetId) = self.tweetMap[followeeId][index]
				heapq.heappush(heap, [timer, tweetId, followeeId, index - 1])
		while heap and len(tweets) < 10:
			(timer, tweetId, followeeId, index) = heapq.heappop(heap)
			tweets.append(tweetId)
			if index >= 0:
				(timer, tweetId) = self.tweetMap[followeeId][index]
				heapq.heappush(heap, [timer, tweetId, followeeId, index - 1])
		return tweets

	def follow(self, followerId: int, followeeId: int):
		self.followerslist[followerId].add(followeeId)

	def unfollow(self, followerId: int, followeeId: int):
		if followeeId in self.followerslist[followerId]:
			self.followerslist[followerId].remove(followeeId)


from collections import defaultdict

class Twitter:

	def __init__(self):
		self.users = defaultdict(set)
		self.tweets = []

	def postTweet(self, userId: int, tweetId: int):
		self.tweets.append((userId, tweetId))

	def getNewsFeed(self, userId: int):
		res = []
		i = len(self.tweets) - 1
		while i >= 0 and len(res) < 10:
			if self.tweets[i][0] in self.users[userId] or self.tweets[i][0] == userId:
				res.append(self.tweets[i][1])
			i -= 1
		return res

	def follow(self, followerId: int, followeeId: int):
		self.users[followerId].add(followeeId)

	def unfollow(self, followerId: int, followeeId: int):
		if followeeId in self.users[followerId]:
			self.users[followerId].remove(followeeId)


import collections

class Twitter(object):

	def __init__(self):
		self.tweets = collections.defaultdict(list)
		self.following = collections.defaultdict(set)
		self.order = 0

	def postTweet(self, userId, tweetId):
		self.tweets[userId] += ((self.order, tweetId),)
		self.order -= 1

	def getNewsFeed(self, userId):
		tw = sorted((tw for i in self.following[userId] | {userId} for tw in self.tweets[i]))[:10]
		return [news for (i, news) in tw]

	def follow(self, followerId, followeeId):
		self.following[followerId].add(followeeId)

	def unfollow(self, followerId, followeeId):
		self.following[followerId].discard(followeeId)


import heapq

class Twitter:
	lastTweetId = 0
	followersGraph = {}
	feedGraph = {}

	def postTweet(self, userId: int, tweetId: int):
		v = (self.lastTweetId, userId, tweetId)
		if userId not in self.feedGraph:
			self.feedGraph[userId] = [v]
		else:
			self.feedGraph[userId].append(v)
		self.lastTweetId -= 1

	def getNewsFeed(self, userId: int):
		res = [userId]
		if userId in self.followersGraph:
			res += self.followersGraph[userId]
		fd = []
		for i in res:
			if i in self.feedGraph:
				fd += self.feedGraph[i]
		heapq.heapify(fd)
		feedCount = 0
		feed = []
		while feedCount < 10 and len(fd) > 0:
			v = heapq.heappop(fd)
			feed.append(v[2])
			feedCount += 1
		return feed

	def follow(self, followerId: int, followeeId: int):
		if followerId not in self.followersGraph:
			self.followersGraph[followerId] = [followeeId]
		else:
			self.followersGraph[followerId].append(followeeId)

	def unfollow(self, followerId: int, followeeId: int):
		followed = self.followersGraph[followerId]
		for (ix, f) in enumerate(followed):
			if f == followeeId:
				del self.followersGraph[followerId]
				break