The problem
Design a small Twitter. postTweet(userId, tweetId) posts a tweet; follow(followerId, followeeId) and unfollow(followerId, followeeId) change who follows whom.
getNewsFeed(userId) returns the ids of the 10 most recent tweets posted by the user or by anyone they follow, newest first.
Examples
- Input
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
- Output
[null, null, [5], null, null, [6, 5], null, [5]]
Constraints
- 1 ≤ userId, followerId, followeeId ≤ 500
- 0 ≤ tweetId ≤ 10⁴
- Every tweet has a different id.
- At most 3 × 10⁴ calls in total.
The idea
Give every tweet a time from a counter that rises by one per post. Each user keeps their own tweets in posting order, so each list is already sorted by time.
A feed is then the newest 10 across several sorted lists — the Merge k Sorted Lists problem, stopped after 10. Put each relevant user’s newest tweet in a max-heap by time; take the top, and push that user’s next older tweet in its place. With f users followed, a feed costs 10 heap steps, not a sort of everything they ever posted.
- Time
- O(1) to post or follow; O(f + 10 log f) per feed
- Space
- O(tweets + follows)
Solution · every language run against every case
class Twitter: def __init__(self): self.time = 0 # rises with every tweet: larger is more recent self.tweets = defaultdict(list) # user -> [(time, tweetId)], oldest first self.follows = defaultdict(set) # user -> the users they follow 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]: # Merge the users' lists newest-first with a heap holding each list's next tweet. heap = [] for u in self.follows[userId] | {userId}: if self.tweets[u]: i = len(self.tweets[u]) - 1 t, tid = self.tweets[u][i] heap.append((-t, tid, u, i)) heapify(heap) feed = [] while heap and len(feed) < 10: _, tid, u, i = heappop(heap) feed.append(tid) if i > 0: # that user's next older tweet t, nid = self.tweets[u][i - 1] heappush(heap, (-t, nid, u, i - 1)) return feed def follow(self, followerId: int, followeeId: int) -> None: if followerId != followeeId: self.follows[followerId].add(followeeId) def unfollow(self, followerId: int, followeeId: int) -> None: self.follows[followerId].discard(followeeId)