⚡Flashcard Drill➔
NeetCode #534LC-355MediumHeap / Priority QueueNC 150NC 250
← Back to All Problems

#534 · #355 · Design Twitter(设计推特)

📌 Problem Statement & Constraints

Design a simplified Twitter with postTweet, getNewsFeed (the 10 most recent tweets from the user and their followees), follow and unfollow. Constraints: 1 <= userId, tweetId <= 10^4; at most 3 * 10^4 calls.

💡 Core Algorithmic Approaches

  1. Store each user's tweets with a monotonically increasing timestamp, which acts as a global ordering.
  2. getNewsFeed merges the followees' tweet lists; only the last 10 per user can ever be relevant, so that caps the work.
  3. A heap over the merged candidates extracts the 10 most recent in O(k log k).
  4. follow must ignore self-follows, and unfollow must be a no-op for non-followees.

💻 Benchmark Python3 Implementation

class Twitter:
    def __init__(self):
        from collections import defaultdict
        self.time = 0
        self.tweets = defaultdict(list)    # user -> [(time, tweetId)]
        self.following = defaultdict(set)  # user -> followees

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

    def getNewsFeed(self, userId: int) -> List[int]:
        import heapq
        users = self.following[userId] | {userId}
        h = []
        for u in users:
            for t, tid in self.tweets[u][-10:]:   # only the 10 newest matter
                h.append((-t, tid))
        heapq.heapify(h)
        res = []
        while h and len(res) < 10:
            res.append(heapq.heappop(h)[1])
        return res

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

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)   # no-op if absent

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) for postTweet/follow/unfollow; O(k log k) for getNewsFeed with k at most 10 * (followees + 1).
💾 Space Complexity
O(total tweets + total follow relations).

⚠️ Interview Pitfalls & Follow-ups

  • Scanning all of a followee's tweets: only the newest 10 can appear in the feed, so the rest can be ignored.
  • Forgetting to include the user's own tweets: the feed includes them.
  • Allowing self-follow to create a duplicate entry: the set would absorb it, but the explicit guard documents the intent.
  • Using remove in unfollow: it raises a KeyError when absent; discard is the safe version.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems