design_twitter
1from heapq import heapify, heappop 2from collections import defaultdict 3 4 5# @leet start 6class Twitter: 7 """ 8 This class designs a simplified version of twitter, where users 9 post tweets, follow/unfollow each other, and can see the 10 most recent 10 tweets in their news feed, based on who they follow. 11 12 To design this class, we need to have a key value mapping of userId -> following 13 As well, that should also support fast removal, since unfollows should be quick. 14 So, we have a defaultdict(set) for that. 15 16 For the tweets, we want to order them chronologically, but there is no timestamp provided. 17 We use a monotonically increasing timestamp for this. 18 As well, we want to be able to access a user's tweets quickly. We can use a dict for this 19 and place tuples of timestamp, tweet_id into it. Since we know that timestamps are 20 increasing, this is always sorted without needing to use a tree data structure. 21 22 Finally, in getNewsFeed, we iterate through all of the users that userId is following 23 and the userId itself, and add the 10 latest tweets to a heap. 24 We then pop the heap up to 10 times, and return the tweet_ids in the heap. 25 26 This means that all operations are constant time except for getting the news feed, 27 which is $O(n\log{}m)$. 28 29 Twitter in reality uses a background worker to write a newsfeed in the background, 30 so accessing the news feed would be constant time, and updating is still constant time, 31 but fires off these background workers to materialize a news feed for a given user. 32 """ 33 34 def __init__(self): 35 self.followers = defaultdict(set) 36 self.tweets = defaultdict(list) 37 self.timestamp = 0 38 39 def postTweet(self, userId: int, tweetId: int) -> None: 40 self.tweets[userId].append((-self.timestamp, tweetId)) 41 self.timestamp += 1 42 43 def getNewsFeed(self, userId: int) -> list[int]: 44 heap = [] 45 46 for following in self.followers[userId]: 47 heap.extend(self.tweets[following][-10:]) 48 49 # add in the user's own tweets 50 heap.extend(self.tweets[userId][-10:]) 51 heapify(heap) 52 res = [] 53 for _ in range(min(len(heap), 10)): 54 res.append(heappop(heap)) 55 return [tweet_id for _, tweet_id in res] 56 57 def follow(self, followerId: int, followeeId: int) -> None: 58 self.followers[followerId].add(followeeId) 59 60 def unfollow(self, followerId: int, followeeId: int) -> None: 61 if followeeId in self.followers[followerId]: 62 self.followers[followerId].remove(followeeId) 63 64 65def test(): 66 assert 2 + 2 == 4
7class Twitter: 8 """ 9 This class designs a simplified version of twitter, where users 10 post tweets, follow/unfollow each other, and can see the 10 most recent 11 tweets in their news feed, based on who they follow. 12 13 To design this class, we need to have a key value mapping of userId -> following 14 As well, that should also support fast removal, since unfollows should be quick. 15 So, we have a defaultdict(set) for that. 16 17 For the tweets, we want to order them chronologically, but there is no timestamp provided. 18 We use a monotonically increasing timestamp for this. 19 As well, we want to be able to access a user's tweets quickly. We can use a dict for this 20 and place tuples of timestamp, tweet_id into it. Since we know that timestamps are 21 increasing, this is always sorted without needing to use a tree data structure. 22 23 Finally, in getNewsFeed, we iterate through all of the users that userId is following 24 and the userId itself, and add the 10 latest tweets to a heap. 25 We then pop the heap up to 10 times, and return the tweet_ids in the heap. 26 27 This means that all operations are constant time except for getting the news feed, 28 which is $O(n\log{}m)$. 29 30 Twitter in reality uses a background worker to write a newsfeed in the background, 31 so accessing the news feed would be constant time, and updating is still constant time, 32 but fires off these background workers to materialize a news feed for a given user. 33 """ 34 35 def __init__(self): 36 self.followers = defaultdict(set) 37 self.tweets = defaultdict(list) 38 self.timestamp = 0 39 40 def postTweet(self, userId: int, tweetId: int) -> None: 41 self.tweets[userId].append((-self.timestamp, tweetId)) 42 self.timestamp += 1 43 44 def getNewsFeed(self, userId: int) -> list[int]: 45 heap = [] 46 47 for following in self.followers[userId]: 48 heap.extend(self.tweets[following][-10:]) 49 50 # add in the user's own tweets 51 heap.extend(self.tweets[userId][-10:]) 52 heapify(heap) 53 res = [] 54 for _ in range(min(len(heap), 10)): 55 res.append(heappop(heap)) 56 return [tweet_id for _, tweet_id in res] 57 58 def follow(self, followerId: int, followeeId: int) -> None: 59 self.followers[followerId].add(followeeId) 60 61 def unfollow(self, followerId: int, followeeId: int) -> None: 62 if followeeId in self.followers[followerId]: 63 self.followers[followerId].remove(followeeId)
This class designs a simplified version of twitter, where users post tweets, follow/unfollow each other, and can see the 10 most recent tweets in their news feed, based on who they follow.
To design this class, we need to have a key value mapping of userId -> following As well, that should also support fast removal, since unfollows should be quick. So, we have a defaultdict(set) for that.
For the tweets, we want to order them chronologically, but there is no timestamp provided. We use a monotonically increasing timestamp for this. As well, we want to be able to access a user's tweets quickly. We can use a dict for this and place tuples of timestamp, tweet_id into it. Since we know that timestamps are increasing, this is always sorted without needing to use a tree data structure.
Finally, in getNewsFeed, we iterate through all of the users that userId is following and the userId itself, and add the 10 latest tweets to a heap. We then pop the heap up to 10 times, and return the tweet_ids in the heap.
This means that all operations are constant time except for getting the news feed, which is $O(n\log{}m)$.
Twitter in reality uses a background worker to write a newsfeed in the background, so accessing the news feed would be constant time, and updating is still constant time, but fires off these background workers to materialize a news feed for a given user.
44 def getNewsFeed(self, userId: int) -> list[int]: 45 heap = [] 46 47 for following in self.followers[userId]: 48 heap.extend(self.tweets[following][-10:]) 49 50 # add in the user's own tweets 51 heap.extend(self.tweets[userId][-10:]) 52 heapify(heap) 53 res = [] 54 for _ in range(min(len(heap), 10)): 55 res.append(heappop(heap)) 56 return [tweet_id for _, tweet_id in res]