Design Twitter

2 min read
LC-Medium
Binary-heap
Design-problem

Oct 21, 2022

3 years ago

LeetCode

Solution

The postTweet, follow, and unfollow functions are pretty simple
In postTweet, make sure to keep track of the tweet count- this is used as sort of the timestamp so that we can order tweets based on when they were posted
- The tweet count starts from -1 and keeps decreasing since in Python we can only use a minheap
In get newsfeed, we iterate through all userIDs of the guy's followees (i.e. people who he follows), also including his own userID, and:
- Add all tweets to a minheap.
  - Doesn't work if we add just the first 10 we see because the timestamp is also a factor
- Pop from minheap until the heap is empty or we've popped 10 tweets

Time	Space	Explanation
`O()`	`O()`

class Twitter: def __init__(self): self.tweet_count = 0 self.user_tweets = defaultdict(list) self.followees = defaultdict(set) def postTweet(self, userId: int, tweetId: int) -> None: self.tweet_count -= 1 self.user_tweets[userId].append((self.tweet_count, tweetId)) def getNewsFeed(self, userId: int) -> List[int]: news_feed = [] min_heap = [] for user_id in list(self.followees[userId]) + [userId]: for user_tweet in self.user_tweets[user_id]: min_heap.append(user_tweet) heapify(min_heap) while min_heap and len(news_feed) < 10: news_feed.append(heappop(min_heap)[1]) return news_feed def follow(self, followerId: int, followeeId: int) -> None: self.followees[followerId].add(followeeId) def unfollow(self, followerId: int, followeeId: int) -> None: if followeeId in self.followees[followerId]: self.followees[followerId].remove(followeeId)