Core Insight Keep only candidates that may become the next answer, ordered by the priority that matters.
Common Pitfall Push only meaningful candidates and remove stale entries before trusting the root.
Description
Design a simplified version of Twitter.
Constraints
- Time Complexity:
O(n log n) - Space Complexity:
O(n)
Tags
hash-maplinked-listdesignheap
Implementation Plan Translate the invariant into these small, testable moves.
- Choose the priority key.
- Push initial candidates.
- Pop the best valid candidate.
- Add newly eligible candidates and repeat.
class Twitter:
def __init__(self):
self.count = 0
self.tweetMap = collections.defaultdict(list)
self.followMap = collections.defaultdict(set)
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)