My accepted Python code

  • 1

    class Twitter(object):

    def __init__(self):
        # Global timestamp
        self.timestamp = 1  
        # Users table
        self.user_data = {}
    def postTweet(self, userId, tweetId):
        if userId not in self.user_data:         
            # Each userId has a tweets list (10 items at most) and a set of followees (include itself)
            self.user_data[userId] = collections.deque(), {userId} 
        # Discard outdated tweet    
        if len(self.user_data[userId][0]) == 10:
        self.user_data[userId][0].appendleft((-self.timestamp, tweetId))
        self.timestamp += 1
    def getNewsFeed(self, userId):
        # Use a heap to store all tweets from followees and pick the 10 most recent ones
        if userId not in self.user_data:
            return []
        heap = []
        for uid in self.user_data[userId][1]:
            if uid in self.user_data:
                for tweet in self.user_data[uid][0]:
                    heapq.heappush(heap, tweet)
        res = []
        while len(res) < 10 and heap:
        return res
    def follow(self, followerId, followeeId):
        if followerId not in self.user_data:
            self.user_data[followerId] = collections.deque(), {followerId} 
    def unfollow(self, followerId, followeeId):
        if followerId not in self.user_data:
        if followerId != followeeId:

  • 0

    I got a similar solution but used a round-ribbon to push to the heap. That may evict some tweet-authors a bit earlier.

    def getNewsFeed(self, userId):
        pushpop to a heap with a round ribbon of users
        LIMIT = 10
        authorQueue = collections.deque( [ (len(self.tweetsByUser[a])-1, self.tweetsByUser[a]) \
            for a in self.followeeByUser[userId] if self.tweetsByUser[a] ] )
        newTweets = []
        while authorQueue:
            i, tweets = authorQueue.popleft()
            if -1<i<len(tweets):
                new = tweets[i]
                i -= 1
            if len(newTweets)>=LIMIT:
                evicted = heapq.heappushpop(newTweets, new)
                heapq.heappush(newTweets, new)
                evicted = None
            if -1<i and new!=evicted:
                authorQueue.append( (i, tweets) )
            # else do not add this author's tweets back to the queue.
        return [id for t, id in heapq.nlargest(LIMIT, newTweets)]

Log in to reply

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