MediumHash TableLinked ListDesignHeap (Priority Queue)

Design Twitter

1 approach, code in every language

Design a simplified version of Twitter where users can post tweets, follow and unfollow other users, and pull a personalized feed of the newest tweets from themselves and the people they follow.

Implement the class Twitter. postTweet(userId, tweetId) publishes a new tweet by the given user. getNewsFeed(userId) returns the ids of the ten most recent tweets in the user's feed, ordered from most recent to least recent, where the feed contains tweets posted by the user and by everyone the user follows. follow(followerId, followeeId) makes the follower start following the followee. unfollow(followerId, followeeId) makes the follower stop following the followee.

A user does not follow themselves, and following someone twice or unfollowing someone you do not follow has no effect.

Example 1

Input: operations = ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] args = [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]

Output: [null, null, [5], null, null, [6, 5], null, [5]]

User 1 posts tweet 5, so the feed is [5]. User 1 follows user 2, who posts tweet 6, so the feed becomes [6, 5] with the newest first. After user 1 unfollows user 2, the feed returns to [5].

Example 2

Input: operations = ["Twitter", "postTweet", "postTweet", "getNewsFeed"] args = [[], [1, 101], [1, 102], [1]]

Output: [null, null, null, [102, 101]]

User 1 posts tweet 101 then tweet 102. The feed lists them newest first as [102, 101].

Constraints

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 10^4 and all tweetId values are unique.
At most 3 * 10^4 total calls will be made to postTweet, getNewsFeed, follow, and unfollow.

Global Timestamps with a Heap Merge

Stamp every tweet with a monotonically increasing time, store tweets per user and follows as sets, then merge the newest tweets of the user and followees by time.

Loading animation…

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

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.
2For postTweet, append a tweet stamped with the current timer to the user's list and then increment the timer.
3For getNewsFeed, form the set of relevant accounts as the user together with everyone they follow.
4From each relevant account take only its last ten tweets, since earlier ones can never reach the top ten overall.
5Push those candidates into a max-heap keyed by timestamp (or sort them descending) and pop the ten most recent tweet ids.
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)

Time

postTweet, follow, and unfollow are O(1); getNewsFeed is O(f log f) where f is the number of followed accounts, since each contributes at most ten candidate tweets.

Space

O(u + t) for the follow sets and stored tweets, where u is users and t is total tweets.

Capping each account to its last ten tweets keeps the merge small regardless of how much history a user has.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free