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
- Store each user's tweets with a monotonically increasing timestamp, which acts as a global ordering.
getNewsFeedmerges the followees' tweet lists; only the last 10 per user can ever be relevant, so that caps the work.- A heap over the merged candidates extracts the 10 most recent in O(k log k).
followmust ignore self-follows, andunfollowmust 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
removeinunfollow: it raises aKeyErrorwhen absent;discardis 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.