Python Solution


  • 0
    class Twitter(object):
        follows = tweets = timestamp = None
    
        def __init__(self):
            self.follows = collections.defaultdict(set)
            self.tweets = collections.defaultdict(list)
            self.timestamp = 0
    
        def postTweet(self, userId, tweetId):
            self.tweets[userId].append((self.timestamp, tweetId))
            self.timestamp += 1
    
        def getNewsFeed(self, userId):
            followees = self.follows[userId]
            followees.add(userId)
            res, stack = [], []
            for i in range(10):
                latest = (-1, -1, -1)
                # loop over first tweet of all followees and find most recent tweet (greatest timestamp)
                for p in followees:
                    if self.tweets[p] and self.tweets[p][-1][0] > latest[0]:
                        latest = (self.tweets[p][-1][0], self.tweets[p][-1][1], p)
                # pop this tweet off the tweet dict
                # print latest
                if latest[2] != -1:
                    self.tweets[latest[2]].pop()
                    # push it into stack for storage until we find 10, and then push tweet ID to res
                    stack.append(latest)
                    res.append(latest[1])
            # restore tweet table
            while stack:
                popped_tweet = stack.pop()
                self.tweets[popped_tweet[2]].append((popped_tweet[0], popped_tweet[1]))
            return res
    
        def follow(self, followerId, followeeId):
            self.follows[followerId].add(followeeId)
            
    
        def unfollow(self, followerId, followeeId):
            if followeeId == followerId or followeeId not in self.follows[followerId]:
                return
            self.follows[followerId].remove(followeeId)
    

Log in to reply
 

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