Design Twitter

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.

Q: 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.

Medium Heaps

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

The key insight is to use a min-heap (priority queue) to efficiently merge the sorted tweet lists. By pushing the most recent tweet from each followee onto the heap, the algorithm repeatedly extracts the tweet with the highest recency and then pushes the next most recent tweet from the same user. This approach merges k sorted lists in O(N log k) time, where k is the number of followees and N is the total number of tweets considered.

Optimal Approach

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.

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).

Pattern Spotlight

Heap / Priority Queue (K-Way Merge of Sorted Lists)

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.

Solution

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)

1class Twitter {
  private int count;
  private Map<Integer, List<int[]>> tweetMap;
  private Map<Integer, Set<Integer>> followMap;
5
  public Twitter() {
      count = 0;
      tweetMap = new HashMap<>();
      followMap = new HashMap<>();
  }
11
  public void postTweet(int userId, int tweetId) {
      tweetMap.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[] {count, tweetId});
      count--;
  }
16
  public List<Integer> getNewsFeed(int userId) {
      List<Integer> res = new ArrayList<>();
      PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
      followMap.computeIfAbsent(userId, k -> new HashSet<>()).add(userId);
21
      for (int followeeId : followMap.get(userId)) {
          List<int[]> tweets = tweetMap.get(followeeId);
          if (tweets != null) {
              int index = tweets.size() - 1;
              int[] tweet = tweets.get(index);
              minHeap.offer(new int[] {tweet[0], tweet[1], followeeId, index - 1});
          }
      }
30
      while (!minHeap.isEmpty() && res.size() < 10) {
          int[] item = minHeap.poll();
          int tweetId = item[1];
          int followeeId = item[2];
          int index = item[3];
          res.add(tweetId);
          if (index >= 0) {
              int[] tweet = tweetMap.get(followeeId).get(index);
              minHeap.offer(new int[] {tweet[0], tweet[1], followeeId, index - 1});
          }
      }
      return res;
  }
44
  public void follow(int followerId, int followeeId) {
      followMap.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
  }
48
  public void unfollow(int followerId, int followeeId) {
      if (followMap.containsKey(followerId)) {
          followMap.get(followerId).remove(followeeId);
      }
  }
54}

Step-by-Step Solution

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.

Record Tweets with Global Timestamp to Track Recency

10def postTweet(self, userId: int, tweetId: int) -> None:
11    self.tweet_map[userId].append([self.count, tweetId])
12    self.count -= 1

Objective

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

Key Insight

Each user’s tweets stay in chronological list order, while the decreasing timestamp lets a min-heap treat newer tweets as smaller values during feed retrieval.

Interview Quick-Check

Core Logic

Append the tweet with its current timestamp before decrementing the counter.

Common Pitfalls & Bugs

A decreasing timestamp lets Python's min-heap pop the newest tweet first.

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

14def 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

Objective

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

Key Insight

Each followee’s tweet list is already ordered by posting time. Pushing the newest tweet from each followed user into a heap lets the algorithm repeatedly take the global newest tweet and then add the next older tweet from that same user.

Interview Quick-Check

Core Logic

Add the user to their own followee set so their tweets appear in their feed.

State & Boundaries

The heap stores one candidate tweet per followee stream, plus the index of the next older tweet.

State & Boundaries

Stop after 10 tweets or when no candidates remain.

Manage Follow and Unfollow Relationships with Sets

34def follow(self, followerId: int, followeeId: int) -> None:
35    self.follow_map[followerId].add(followeeId)
37def unfollow(self, followerId: int, followeeId: int) -> None:
38    if followeeId in self.follow_map[followerId]:
39        self.follow_map[followerId].remove(followeeId)

Objective

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

Key Insight

A set prevents duplicate followees and gives efficient membership checks and removals. Safe membership checking prevents errors when unfollowing someone who is not currently followed.

Interview Quick-Check

Core Logic

Use a set so duplicate follows do not create duplicate feed sources.

Common Pitfalls & Bugs

Check membership before removing during unfollow.

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.

Line 23 Critical

min_heap.append([count, tweetId, followeeId, index - 1])

Add the most recent tweet from the followee to the min-heap.

Pushing the tweet with its timestamp and metadata enables the heap to track the next candidate tweets for merging.

Line 31 Critical

heapq.heappush(min_heap, [new_count, new_tweetId, followeeId, index - 1])

Push the next tweet onto the heap for future extraction.

Adding the next tweet maintains the heap's invariant of containing the next candidates from each followee.

Line 6 Core

self.count = 0

Initialize a global counter to assign timestamps to tweets.

The global counter decreasing with each tweet ensures a unique, comparable timestamp that reflects recency, enabling efficient ordering in the min-heap.

Line 8 Core

self.follow_map = collections.defaultdict(set)

Initialize the mapping from users to followed users.

The follow map stores each user's followees as a set, enabling efficient follow, unfollow, and feed lookup.

Line 15 Core

res = []

Initialize a min-heap to merge tweets from followees.

The min-heap enables efficient retrieval of the most recent tweets across multiple users by timestamp.

Line 22 Core

count, tweetId = self.tweet_map[followeeId][index]

Read the followee's most recent tweet entry.

Retrieving the timestamp and tweet ID gives the heap the exact recency key and output value for this followee's newest candidate.

Line 25 Core

heapq.heapify(min_heap)

Transform the list into a heap structure.

Heapifying prepares the data structure for efficient extraction of the most recent tweet across all followees.

Line 35 Core

self.follow_map[followerId].add(followeeId)

Add the followee to the follower's followee set.

Adding to a set records the relationship while avoiding duplicate followees.

Line 39 Core

self.follow_map[followerId].remove(followeeId)

Remove the followee from the follower's followee set.

Removing the followee updates the follower's feed sources for future news feed requests.

Line 7 Core

self.tweet_map = collections.defaultdict(list)

Initialize a dictionary mapping user IDs to their list of tweets.

Storing tweets per user in a list preserves chronological order and allows efficient appending and retrieval.

Line 12 Core

self.count -= 1

Advance the global timestamp counter.

Decrementing the counter makes future tweets have smaller timestamps, so they are treated as more recent by the min-heap.

Line 20 Core

if followeeId in self.tweet_map:

Check if the followee has posted any tweets.

Skipping followees without tweets avoids unnecessary heap operations and errors.

Line 21 Core

index = len(self.tweet_map[followeeId]) - 1

Get the index of the most recent tweet for the followee.

Starting from the most recent tweet allows the heap to merge tweets in descending order of recency.

Line 26 Core

while min_heap and len(res) < 10:

Loop while the heap is not empty and fewer than 10 tweets have been collected.

This loop extracts the top tweets until the news feed size limit is reached or no more tweets remain.

Line 28 Core

res.append(tweetId)

Append the tweet ID to the result list.

Collecting tweet IDs in order builds the final news feed output.

Line 29 Core

if index >= 0:

Check if the followee has older tweets to add to the heap.

If older tweets exist, pushing them maintains the heap's role in merging all tweets in order.

Line 30 Core

new_count, new_tweetId = self.tweet_map[followeeId][index]

Retrieve the next most recent tweet from the followee.

Accessing the next tweet allows the heap to continue merging the followee's tweet stream.

Line 38 Core

if followeeId in self.follow_map[followerId]:

Check whether the followee is currently followed.

Checking membership before removal prevents errors when the relationship does not exist.

Line 5 Standard

def __init__(self):

Define the Twitter constructor.

The constructor creates the persistent state needed by all Twitter operations.

Line 10 Standard

def postTweet(self, userId: int, tweetId: int) -> None:

Define the postTweet method.

This method records a new tweet for a user.

Line 32 Standard

return res

Return the list of up to 10 most recent tweet IDs.

Returning the collected tweets completes the news feed retrieval operation.

Line 34 Standard

def follow(self, followerId: int, followeeId: int) -> None:

Define the follow method.

This method updates the follow graph by adding one followee to one follower.

Line 37 Standard

def unfollow(self, followerId: int, followeeId: int) -> None:

Define the unfollow method.

This method updates the follow graph by removing one follow relationship when present.

Line 19 Standard

for followeeId in self.follow_map[userId]:

Iterate over each followee of the user.

This loop prepares to merge tweets from all followees by accessing their tweet lists.

Line 14 Basic

def getNewsFeed(self, userId: int) -> list[int]:

Initialize the result list for the news feed.

This list accumulates the tweet IDs to be returned, respecting the maximum size constraint.

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?

Because each user's tweets are sorted by recency, the min-heap always contains the next most recent tweet candidates from each followee. Extracting the smallest timestamp (most recent) and then pushing the next tweet from that user ensures the heap dynamically maintains the next best candidates, enabling efficient merging without sorting all tweets together.

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)`

1	`class Twitter {`
2	`private int count;`
3	`private Map<Integer, List<int[]>> tweetMap;`
4	`private Map<Integer, Set<Integer>> followMap;`
5
6	`public Twitter() {`
7	`count = 0;`
8	`tweetMap = new HashMap<>();`
9	`followMap = new HashMap<>();`
10	`}`
11
12	`public void postTweet(int userId, int tweetId) {`
13	`tweetMap.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[] {count, tweetId});`
14	`count--;`
15	`}`
16
17	`public List<Integer> getNewsFeed(int userId) {`
18	`List<Integer> res = new ArrayList<>();`
19	`PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));`
20	`followMap.computeIfAbsent(userId, k -> new HashSet<>()).add(userId);`
21
22	`for (int followeeId : followMap.get(userId)) {`
23	`List<int[]> tweets = tweetMap.get(followeeId);`
24	`if (tweets != null) {`
25	`int index = tweets.size() - 1;`
26	`int[] tweet = tweets.get(index);`
27	`minHeap.offer(new int[] {tweet[0], tweet[1], followeeId, index - 1});`
28	`}`
29	`}`
30
31	`while (!minHeap.isEmpty() && res.size() < 10) {`
32	`int[] item = minHeap.poll();`
33	`int tweetId = item[1];`
34	`int followeeId = item[2];`
35	`int index = item[3];`
36	`res.add(tweetId);`
37	`if (index >= 0) {`
38	`int[] tweet = tweetMap.get(followeeId).get(index);`
39	`minHeap.offer(new int[] {tweet[0], tweet[1], followeeId, index - 1});`
40	`}`
41	`}`
42	`return res;`
43	`}`
44
45	`public void follow(int followerId, int followeeId) {`
46	`followMap.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);`
47	`}`
48
49	`public void unfollow(int followerId, int followeeId) {`
50	`if (followMap.containsKey(followerId)) {`
51	`followMap.get(followerId).remove(followeeId);`
52	`}`
53	`}`
54	`}`

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

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Twitter State Maps and Timestamp Counter

Record Tweets with Global Timestamp to Track Recency

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

Manage Follow and Unfollow Relationships with Sets

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.