leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

design-twitterV1.py (2350B)

      1 # This approach uses a simple list based approach with sorting.
      2 # while there is a nice heap + hashmap based approach, given the limited
      3 # number of insturctions, this approach works quite well given the low
      4 # asymptotic coefficients.
      5 
      6 
      7 class Tweet:
      8     def __init__(self, time, tweetId):
      9         self.time = time
     10         self.tweetId = tweetId
     11 
     12     def __lt__(self, other):
     13         return self.time < other.time
     14 
     15 
     16 class Twitter:
     17 
     18     def __init__(self):
     19         self.tweets = {}
     20         self.following = {}
     21         self.current_time = 0
     22 
     23     def _add_tweet(self, tweetId, userId):
     24         tweet = Tweet(self.current_time, tweetId)
     25         self.current_time += 1
     26         self.tweets[userId].add(tweet)
     27 
     28     def postTweet(self, userId: int, tweetId: int) -> None:
     29 
     30         tweets = self.tweets
     31         following = self.following
     32 
     33         if userId in tweets:
     34             self._add_tweet(tweetId, userId)
     35 
     36         else:
     37             tweets[userId] = set()
     38             self._add_tweet(tweetId, userId)
     39 
     40     def getNewsFeed(self, userId: int) -> List[int]:
     41 
     42         tweets = self.tweets
     43         following = self.following
     44 
     45         tweet_ls = []
     46 
     47         # or current user posts...
     48         if userId in following:
     49             ls = list(following[userId])
     50             for id in ls:
     51                 if id in tweets:
     52                     tweet_ls.extend(tweets[id])
     53 
     54         if userId in tweets:
     55             tweet_ls.extend(tweets[userId])
     56 
     57         tweet_ls.sort(reverse=True)
     58 
     59         if len(tweet_ls) > 0:
     60             return [tweet.tweetId for tweet in tweet_ls[0:10]]
     61 
     62         return []
     63 
     64     def follow(self, followerId: int, followeeId: int) -> None:
     65 
     66         tweets = self.tweets
     67         following = self.following
     68 
     69         if followerId in following:
     70             following[followerId].add(followeeId)
     71         else:
     72             following[followerId] = set()
     73             following[followerId].add(followeeId)
     74 
     75     def unfollow(self, followerId: int, followeeId: int) -> None:
     76 
     77         tweets = self.tweets
     78         following = self.following
     79 
     80         if followerId in following:
     81             following[followerId].remove(followeeId)
     82 
     83 
     84 # Your Twitter object will be instantiated and called as such:
     85 # obj = Twitter()
     86 # obj.postTweet(userId,tweetId)
     87 # param_2 = obj.getNewsFeed(userId)
     88 # obj.follow(followerId,followeeId)
     89 # obj.unfollow(followerId,followeeId)