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 Alex Chen, 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)?

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.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Design Twitter and other Shopify interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →