How do you solve Design Twitter?

Maintain a global decreasing counter as a timestamp for each tweet to track recency. Store each user's tweets as a list of (timestamp, tweetId) pairs. For news feed retrieval, add the user to their own followee set to include their tweets. Initialize a min-heap with the most recent tweet from each followee. Repeatedly pop the smallest timestamp (most recent tweet) from the heap, add its tweetId to the result, and if the user has older tweets, push the next one onto the heap. Continue until 10 tweets are collected or the heap is empty.

What pattern does Design Twitter use?

The Pattern: Heap / Priority Queue (K-Way Merge of Sorted Lists) The Heuristic: When merging multiple sorted streams to find the top elements efficiently, use a min-heap to always extract the next most recent item and dynamically push the next candidate from the same stream, enabling an O(N log k) merge where k is the number of streams.

Design Twitter — Heap / Priority Queue

Q: What is the time complexity of Design Twitter?

O(N log k). Each tweet is pushed and popped from the heap at most once. The heap size is bounded by k, the number of followees. Each heap operation takes O(log k), so total complexity is O(N log k), where N is the total number of tweets considered.

Problem

Design a simplified Twitter where users can post tweets, follow/unfollow other users, and retrieve the 10 most recent tweet IDs in the user's news feed, which includes tweets from the user and their followees.

All tweet IDs are unique.
Users can follow themselves implicitly.
News feed returns up to 10 most recent tweets.
Number of users and tweets can be large.

Example

Input: postTweet(1, 5), postTweet(1, 3), follow(2, 1), getNewsFeed(2)

Output: [3, 5]

User 1 posts tweets with IDs 5 and 3. User 2 follows user 1. When user 2 requests their news feed, it includes user 1's tweets ordered from most recent to least recent, resulting in [3, 5]. The system maintains a global timestamp counter decreasing with each tweet to track recency.

Approach

Straightforward Solution

A naive approach would collect all tweets from the user and their followees, merge them into one list, and then sort by timestamp. This approach is inefficient because it requires scanning and sorting potentially large tweet lists, leading to high time complexity.

Core Observation

The news feed retrieval problem reduces to merging multiple sorted lists of tweets (each user's tweets sorted by recency) into a single sorted list of the most recent tweets. Each user's tweets are stored in descending order of posting time, and the challenge is efficiently merging these streams to get the top 10 most recent tweets.

Path to Optimal

Preview

The key insight is to use a min-heap (priority queue) to efficiently merge the sorted tweet lists…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Maintain a global decreasing counter as a timestamp for each tweet to track recency. Store each user's tweets as a list of (timestamp, tweetId) pairs…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(N log k)

Each tweet is pushed and popped from the heap at most once. The heap size is bounded by k, the number of followees. Each heap operation takes O(log k), so total complexity is O(N log k), where N is the total number of tweets considered.

Space

O(N + U)

Storing all tweets requires O(N) space, where N is the total number of tweets posted. The follow map requires O(U) space, where U is the number of users, to store follow relationships. The heap uses O(k) space during news feed retrieval, which is at most O(U).

Solution

Python

1import collections
2import heapq
3
4class Twitter:
  def __init__(self):
      self.count = 0
      self.tweet_map = collections.defaultdict(list)
      self.follow_map = collections.defaultdict(set)
9
  def postTweet(self, userId: int, tweetId: int) -> None:
      self.tweet_map[userId].append([self.count, tweetId])
      self.count -= 1
13
  def getNewsFeed(self, userId: int) -> list[int]:
      res = []
      min_heap = []
      
      self.follow_map[userId].add(userId)
      for followeeId in self.follow_map[userId]:
          if followeeId in self.tweet_map:
              index = len(self.tweet_map[followeeId]) - 1
              count, tweetId = self.tweet_map[followeeId][index]
              min_heap.append([count, tweetId, followeeId, index - 1])
      
      heapq.heapify(min_heap)
      while min_heap and len(res) < 10:
          count, tweetId, followeeId, index = heapq.heappop(min_heap)
          res.append(tweetId)
          if index >= 0:
              new_count, new_tweetId = self.tweet_map[followeeId][index]
              heapq.heappush(min_heap, [new_count, new_tweetId, followeeId, index - 1])
      return res
33
  def follow(self, followerId: int, followeeId: int) -> None:
      self.follow_map[followerId].add(followeeId)
36
  def unfollow(self, followerId: int, followeeId: int) -> None:
      if followeeId in self.follow_map[followerId]:
          self.follow_map[followerId].remove(followeeId)

Step-by-Step Solution

1

Initialize Twitter State Maps and Timestamp Counter

5def __init__(self):
  self.count = 0
  self.tweet_map = collections.defaultdict(list)
  self.follow_map = collections.defaultdict(set)

Objective

To initialize the global timestamp, per-user tweet storage, and per-user follow relationship storage.

Key Insight

The design needs three pieces of persistent state: a decreasing timestamp for recency ordering, a tweet list per user, and a followee set per user. These structures support posting, following, unfollowing, and lazy heap-based feed merging.

Interview Quick-Check

Core Logic

Use a global counter so tweets can be compared by recency.

State & Boundaries

Store tweets per user and followees per user to avoid scanning all users.

2

Record Tweets with Global Timestamp to Track Recency

To append each posted tweet with its timestamp and advance the global recency counter.

3

Build News Feed by Merging Followees' Tweet Streams Using a Min-Heap

To retrieve up to 10 newest tweets from the user and their followees by lazily merging tweet lists.

4

Manage Follow and Unfollow Relationships with Sets

To update each user's followee set efficiently for follow and unfollow operations.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 27 Critical

count, tweetId, followeeId, index = heapq.heappop(min_heap)

Pop the tweet with the smallest timestamp (most recent) from the heap.

Extracting the most recent tweet ensures the news feed is ordered correctly by recency.

Line 11 Critical

self.tweet_map[userId].append([self.count, tweetId])

Append the new tweet with its timestamp.

Appending the timestamp and tweet ID stores the tweet in that user's ordered tweet stream.

Line 18 Critical

self.follow_map[userId].add(userId)

Add the user to their own followee set to include their tweets in the news feed.

Including the user ensures their own tweets appear in their news feed without special-case logic.

Full line-by-line criticality + rationale for all 28 lines available on Pro.

Test Your Understanding

Why does using a min-heap to merge the most recent tweets from each followee guarantee efficient retrieval of the top 10 most recent tweets?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Design Twitter from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Design Twitter drill

or drill a free problem

1	`import collections`
2	`import heapq`
3
4	`class Twitter:`
5	`def __init__(self):`
6	`self.count = 0`
7	`self.tweet_map = collections.defaultdict(list)`
8	`self.follow_map = collections.defaultdict(set)`
9
10	`def postTweet(self, userId: int, tweetId: int) -> None:`
11	`self.tweet_map[userId].append([self.count, tweetId])`
12	`self.count -= 1`
13
14	`def getNewsFeed(self, userId: int) -> list[int]:`
15	`res = []`
16	`min_heap = []`
17
18	`self.follow_map[userId].add(userId)`
19	`for followeeId in self.follow_map[userId]:`
20	`if followeeId in self.tweet_map:`
21	`index = len(self.tweet_map[followeeId]) - 1`
22	`count, tweetId = self.tweet_map[followeeId][index]`
23	`min_heap.append([count, tweetId, followeeId, index - 1])`
24
25	`heapq.heapify(min_heap)`
26	`while min_heap and len(res) < 10:`
27	`count, tweetId, followeeId, index = heapq.heappop(min_heap)`
28	`res.append(tweetId)`
29	`if index >= 0:`
30	`new_count, new_tweetId = self.tweet_map[followeeId][index]`
31	`heapq.heappush(min_heap, [new_count, new_tweetId, followeeId, index - 1])`
32	`return res`
33
34	`def follow(self, followerId: int, followeeId: int) -> None:`
35	`self.follow_map[followerId].add(followeeId)`
36
37	`def unfollow(self, followerId: int, followeeId: int) -> None:`
38	`if followeeId in self.follow_map[followerId]:`
39	`self.follow_map[followerId].remove(followeeId)`

5	`def __init__(self):`
6	`self.count = 0`
7	`self.tweet_map = collections.defaultdict(list)`
8	`self.follow_map = collections.defaultdict(set)`