Design Twitter

Intuition

Ordering the feed by recency is really a matter of comparing when each tweet was posted, so we attach a global counter that increases with every post. Each user keeps their own list of stamped tweets, and each user keeps a set of who they follow. To build a feed we only ever need the last ten tweets from any single account, because no account can contribute more than ten to a ten-item result. We gather those recent tweets from the user plus every followee and pick the ten with the largest timestamps, which a max-heap or a sort by time makes straightforward.

Algorithm walkthrough

1. 1Keep a global timer, a map from user to their list of (time, tweetId) tweets, and a map from user to a set of followees.
2. 2For postTweet, append a tweet stamped with the current timer to the user's list and then increment the timer.
3. 3For getNewsFeed, form the set of relevant accounts as the user together with everyone they follow.
4. 4From each relevant account take only its last ten tweets, since earlier ones can never reach the top ten overall.
5. 5Push those candidates into a max-heap keyed by timestamp (or sort them descending) and pop the ten most recent tweet ids.
6. 6For follow and unfollow, simply add or remove the followee in the follower's set, guarding against a user following themselves.

Implementation

from collections import defaultdict
from typing import List

class Twitter:
    def __init__(self):
        self.timer = 0
        self.tweets = defaultdict(list)
        self.following = defaultdict(set)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.timer, tweetId))
        self.timer += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        users = self.following[userId] | {userId}
        candidates = []
        for uid in users:
            candidates.extend(self.tweets[uid][-10:])
        candidates.sort(reverse=True)
        return [tweetId for _, tweetId in candidates[:10]]

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)