LeetCode 355. Design Twitter

relevant: system design of twitter

Problem Clarification

Design a simplified version of Twitter with methods:

• postTweet(userId, tweetId): here tweetId is not necessarily incremental
• follow(followerId, followeeId)
• unfollow(followerId, followeeId)
• getNewsFeed(userId): Retrieve the 10 most recent tweet ids (ordered from most recent to least recent) posted by the user and his/her followees.

Analysis

• User follow-relationship: dictionary of sets {followerId: {followeeIds}}
• Tweet Logs:
  1. Log the tweets sequentially in a single list. When retrieve the news feed, loop through the list from the end and filter by the poster’s userId – time complexity $O(N)$, $N$ is the total number of tweets.
  2. Log the tweets separately by the poster’s userId, and add a timer to record the sequence of tweets. When retrieve the news feed, just loop throught the lists of relevant posters – time complexity $O(K\log{M})$, where $K$ is 10 here, $\log{M}$ comes from merging $M$ sorted lists using the heap queue algorithm.

Code

code example from https://leetcode.com/problems/design-twitter/discuss/82863/Python-solution

class Twitter(object):

    def __init__(self):
        self.timer = itertools.count(step=-1)
        self.tweets = collections.defaultdict(collections.deque)
        self.followees = collections.defaultdict(set)

    def postTweet(self, userId, tweetId):
        self.tweets[userId].appendleft((next(self.timer), tweetId))

    def getNewsFeed(self, userId):
        tweets = heapq.merge(*(self.tweets[u] for u in self.followees[userId] | {userId}))
        return [t for _, t in itertools.islice(tweets, 10)]

    def follow(self, followerId, followeeId):
        self.followees[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        self.followees[followerId].discard(followeeId)

Implementation tricks

• itertools.count(start=0, step=1): iterator that returns evenly spaced values starting with number start.
• collections.defaultdict([default_factory[, ...]]): dict subclass that calls a factory function to supply missing values. When calling __getitem__() method of the dict class and the requested key is not found, default_factory() is called to provide a default value for the key.
• collections.deque([iterable[, maxlen]]): double-ended queue, list-like container with fast appends and pops on either end. list objects incur $O(n)$ memory movement costs for pop(0) and insert(0, v), while deque objects support thread-safe, memory efficient appends and pops with approximately the same $O(1)$ performance in either direction.
• set: remove(elem) raises KeyError if elem is not contained in the set, while discard(elem) removes elem only when it is present. union(*others) is equivalent to set | other.
• heapq.merge(*iterables, key=None, reverse=False): Merge multiple sorted inputs into a single sorted output. Returns an iterator over the sorted values. Similar to sorted(itertools.chain(*iterables) but does not pull the data into memory all at once.
• itertools.islice(iterable, stop): similar to regular slicing list[:10] (except that islice does not support negative values). However we cannot use regular slicing here, since heapq.merge return a generator and generator object is not subscriptable.

Edge Test Cases

1. follow self. wrong: list(self.followees[userId]) + [userId]; right: self.followee[userId] | {userId}

   Input: ["Twitter","postTweet","follow","getNewsFeed"]
           [[],[1,5],[1,1],[1]]
   Output: wrong: [null,null,null,[5,5]]
            right: [null,null,null,[5]]
   

2. more than 10 tweets in total

   Input: ["Twitter","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","postTweet","getNewsFeed"]
           [[],[1,5],[1,3],[1,101],[1,13],[1,10],[1,2],[1,94],[1,505],[1,333],[1,22],[1,11],[1]]
   Output: wrong: [null,null,null,null,null,null,null,null,null,null,null,null,[11,22,333,505,94,2,10,13,101,3,5]]
           right: [null,null,null,null,null,null,null,null,null,null,null,null,[11,22,333,505,94,2,10,13,101,3]]