#69 Medium Time O(n log n) Space O(n) Animated
Design Twitter
Design a simplified version of Twitter.
Approach: Hash Map + Max-Heap
Click play to start
Step 0 / 0
Press play to start the visualization.
1×
Steps
Description
Design a simplified version of Twitter.
Constraints
- Time Complexity:
O(n log n) - Space Complexity:
O(n)
Tags
hash-maplinked-listdesignheap
Solution — Hash Map + Max-Heap
O(n log n) O(n)
class Twitter:
def __init__(self):
self.count = 0
self.tweetMap = collections.defaultdict(list) # userId -> list of [count, tweetIds]
self.followMap = collections.defaultdict(set) # userId -> set of followeeIds
def postTweet(self, userId: int, tweetId: int) -> None:
self.tweetMap[userId].append([self.count, tweetId])
self.count -= 1
def getNewsFeed(self, userId: int) -> List[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) -> None:
self.followMap[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
if followeeId in self.followMap[followerId]:
self.followMap[followerId].remove(followeeId)