Two simple solutions with either MaxHeap or MinHeap.


  • 0
    A

    Solution 1:

    1. Use max heap for retrieving the 10 most recent tweet ids.
    2. Append negative time for max heap because the most recent time is displayed first. Python use min heap (heapq) by default.
    class Twitter(object):
        def __init__(self):
            self.userFollowees = dict()
            self.userTimeTweets = dict()
            self.time = 0
    
        def postTweet(self, userId, tweetId):
            self.time += 1
            # Append negative time for max heap because the most recent time is displayed first. Python use min heap (heapq) by default.
            self.userTimeTweets.setdefault(userId, []).append((-self.time, tweetId))
            
        def getNewsFeed(self, userId):
            result = []
            # Union user's followees and the user himself.
            followees = self.userFollowees.get(userId, set()) | set([userId])
            maxHeap = []
            
            for followee in followees:
                if followee in self.userTimeTweets:
                    for timeTweet in self.userTimeTweets[followee]:
                        maxHeap.append(timeTweet)
            heapq.heapify(maxHeap)
            for _ in range(10):
                if len(maxHeap) > 0:
                    time, tweet = heapq.heappop(maxHeap)
                    result.append(tweet)
            return result
            
        def follow(self, followerId, followeeId):
            self.userFollowees.setdefault(followerId, set()).add(followeeId)
          
        def unfollow(self, followerId, followeeId):
            if followerId in self.userFollowees and followeeId in self.userFollowees[followerId]:
                self.userFollowees[followerId].remove(followeeId)
    

    Solution 2:

    1. Use min heap to dynamically maintain top 10 largest value: if new value > 10th largest value (minHeap[0]), heappop(minHeap) and heappush(minHeap, new value).
    2. Reverse the result list because min heap is used for appending tweets.
    def __init__(self):
            self.userFollowees = dict()
            self.userTimeTweets = dict()
            self.time = 0
            
            
        def postTweet(self, userId, tweetId):
            self.time += 1
            # Python use min heap (heapq) by default.
            self.userTimeTweets.setdefault(userId, []).append((self.time, tweetId))
            
    
        def getNewsFeed(self, userId):
            result = []
            # Union user's followees and the user himself. CARE: set([userId]) not set(userId).
            followees = self.userFollowees.get(userId, set()) | set([userId])
            minHeap = []
            
            for followee in followees:
                if followee in self.userTimeTweets:
                    for timeTweet in self.userTimeTweets[followee]:
                        if len(minHeap) < 10:
                            heapq.heappush(minHeap, timeTweet)
                        else:
                            if timeTweet[0] > minHeap[0][0]:
                                heapq.heappop(minHeap)
                                heapq.heappush(minHeap, timeTweet)
            
            while len(minHeap) > 0:
                time, tweet = heapq.heappop(minHeap)
                result.append(tweet)
            result.reverse()
            return result
            
    
        def follow(self, followerId, followeeId):
            self.userFollowees.setdefault(followerId, set()).add(followeeId)
            
    
        def unfollow(self, followerId, followeeId):
            if followerId in self.userFollowees and followeeId in self.userFollowees[followerId]:
                self.userFollowees[followerId].remove(followeeId)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.