355. Design Twitter

Q: Why a heap and not just sort all relevant tweets?

Sorting all relevant tweets is O(T log T) where T is the total tweets across followees. The heap only pops the 10 newest, so it's O(K log F) where K = 10. For high-fanout users (1000 followees, 1M total tweets), that's a massive win.

Q: How do you handle the celebrity problem (one user followed by millions)?

Hybrid fanout: low-fanout users push to their followers' feeds at post time (write-heavy, read-fast). Celebrities don't push; their followers pull at read time (read-heavy, write-cheap). Senior Shopify candidates are expected to bring this up.

mediumAsked at Shopify

Shopify maps this to 'design a merchant activity feed': merge K time-ordered streams (posts, orders, reviews) into one feed. The interviewer wants you to combine hash maps for the follow graph with a heap for the merged-feed read.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Shopify loops.

Glassdoor (2026-Q1)— Shopify Senior Backend onsites cite Design Twitter as a recurring composite-data-structure question.
Reddit r/cscareerquestions (2025-12)— Shopify L4+ reports include Design Twitter framed as 'activity feed'.

Problem

Design a simplified Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user's news feed. Implement postTweet(userId, tweetId), getNewsFeed(userId), follow(followerId, followeeId), and unfollow(followerId, followeeId).

Constraints

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 10^4
All the tweets have unique IDs.
At most 3 * 10^4 calls will be made to the methods.

Examples

Example 1

Input

postTweet(1,5); getNewsFeed(1); follow(1,2); postTweet(2,6); getNewsFeed(1); unfollow(1,2); getNewsFeed(1)

Output

[null,null,[5],null,null,[6,5],null,[5]]

Approaches

1. Naive: scan all tweets on every getNewsFeed

Store a global list of tweets. On getNewsFeed, filter by followee set, sort by timestamp, take top 10.

Time: O(T log T) per feed, O(1) per post
Space: O(T)

class TwitterNaive {
  constructor() {
    this.tweets = [];
    this.followGraph = new Map();
    this.time = 0;
  }
  postTweet(userId, tweetId) {
    this.tweets.push({ userId, tweetId, t: this.time++ });
  }
  follow(a, b) {
    if (!this.followGraph.has(a)) this.followGraph.set(a, new Set());
    this.followGraph.get(a).add(b);
  }
  unfollow(a, b) {
    if (this.followGraph.has(a)) this.followGraph.get(a).delete(b);
  }
  getNewsFeed(userId) {
    const followees = this.followGraph.get(userId) || new Set();
    return this.tweets
      .filter(t => t.userId === userId || followees.has(t.userId))
      .sort((a, b) => b.t - a.t)
      .slice(0, 10)
      .map(t => t.tweetId);
  }
}

Tradeoff: Easy to write but O(T log T) per feed read. At Shopify's scale, this dies. Mention as the baseline before going to per-user lists + heap.

2. Per-user tweet list + heap merge (optimal)

Store each user's tweets in a list (newest first). On getNewsFeed, merge top tweets from the user + each followee using a max-heap keyed by timestamp.

Time: O(K log F) per feed where F = followees, K = feed size
Space: O(total tweets)

class MaxHeap {
  constructor() { this.h = []; }
  size() { return this.h.length; }
  push(v) { this.h.push(v); this._up(this.h.length - 1); }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) { this.h[0] = last; this._down(0); }
    return top;
  }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p].t < this.h[i].t) {
        [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
        i = p;
      } else break;
    }
  }
  _down(i) {
    const n = this.h.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let largest = i;
      if (l < n && this.h[l].t > this.h[largest].t) largest = l;
      if (r < n && this.h[r].t > this.h[largest].t) largest = r;
      if (largest === i) break;
      [this.h[largest], this.h[i]] = [this.h[i], this.h[largest]];
      i = largest;
    }
  }
}

class Twitter {
  constructor() {
    this.tweets = new Map();
    this.follows = new Map();
    this.time = 0;
  }
  postTweet(userId, tweetId) {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId).push({ tweetId, t: this.time++ });
  }
  follow(a, b) {
    if (a === b) return;
    if (!this.follows.has(a)) this.follows.set(a, new Set());
    this.follows.get(a).add(b);
  }
  unfollow(a, b) {
    if (this.follows.has(a)) this.follows.get(a).delete(b);
  }
  getNewsFeed(userId) {
    const sources = new Set([userId]);
    if (this.follows.has(userId)) for (const f of this.follows.get(userId)) sources.add(f);
    const heap = new MaxHeap();
    for (const u of sources) {
      const list = this.tweets.get(u);
      if (!list || !list.length) continue;
      const idx = list.length - 1;
      heap.push({ ...list[idx], user: u, idx });
    }
    const result = [];
    while (heap.size() && result.length < 10) {
      const top = heap.pop();
      result.push(top.tweetId);
      if (top.idx > 0) {
        const next = this.tweets.get(top.user)[top.idx - 1];
        heap.push({ ...next, user: top.user, idx: top.idx - 1 });
      }
    }
    return result;
  }
}

Tradeoff: Each feed read is O(K log F) where K = 10 and F = number of followees. Mirrors the K-way merge from Merge K Sorted Lists. Shopify's preferred answer for senior candidates.

Shopify-specific tips

Shopify wants you to explicitly name the connection to Merge K Sorted Lists. Senior candidates also get 'how do you scale this to 100M users?' — answer: shard by user_id, denormalize the feed (write-time fanout for low-fanout users, read-time fanout for celebrities). Volunteer the 'celebrity problem' before being asked.

Common mistakes

Storing a global tweet list and filtering — explodes the feed read cost.
Letting a user follow themselves — guard with a == b check in follow.
Returning more or fewer than 10 tweets — be precise about the top-N requirement.
Forgetting to handle unfollow when the user doesn't follow the target (.delete on a missing key is a no-op in JS, but be defensive).

Follow-up questions

An interviewer at Shopify may pivot to one of these next:

Scale to 100M users — shard, denormalize, push vs pull fanout.
Add likes + count likes per tweet (separate counter map).
Add retweets — when a user retweets, does the timestamp reset?
Make getNewsFeed pageable — cursor-based pagination.
Add a mute feature — exclude certain users from the feed but keep following them.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why a heap and not just sort all relevant tweets?

Sorting all relevant tweets is O(T log T) where T is the total tweets across followees. The heap only pops the 10 newest, so it's O(K log F) where K = 10. For high-fanout users (1000 followees, 1M total tweets), that's a massive win.

How do you handle the celebrity problem (one user followed by millions)?