My accepted Python code


  • 1
    G

    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].pop()
            
        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:
            res.append(heapq.heappop(heap)[1])
        return res
        
    
    def follow(self, followerId, followeeId):
    
        if followerId not in self.user_data:
            self.user_data[followerId] = collections.deque(), {followerId} 
            
        self.user_data[followerId][1].add(followeeId)
        
    
    def unfollow(self, followerId, followeeId):
    
        if followerId not in self.user_data:
            return
        
        if followerId != followeeId:
            self.user_data[followerId][1].discard(followeeId)

  • 0
    J

    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)
            else:
                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.