#355

Design Twitter

medium· Heap / Priority Queueruns: 0

Design a simplified Twitter where users can post tweets, follow and unfollow other users, and see the 10 most recent tweets in their news feed. Implement Twitter with postTweet, getNewsFeed, follow, and unfollow. The news feed contains the 10 most recent tweets from the user and the users they follow, most recent first.

wpm 0acc 100%time 0:000 / 1248

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)
        self.followees = defaultdict(set)

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

    def getNewsFeed(self, userId: int) -> list[int]:
        feed = []
        users = self.followees[userId] | {userId}
        heap = []
        for user in users:
            if self.tweets[user]:
                i = len(self.tweets[user]) - 1
                time, tweet = self.tweets[user][i]
                heap.append((-time, tweet, user, i - 1))
        heapq.heapify(heap)
        while heap and len(feed) < 10:
            _, tweet, user, i = heapq.heappop(heap)
            feed.append(tweet)
            if i >= 0:
                time, next_tweet = self.tweets[user][i]
                heapq.heappush(heap, (-time, next_tweet, user, i - 1))
        return feed

    def follow(self, followerId: int, followeeId: int) -> None:
        self.followees[followerId].add(followeeId)

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

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.