Design a News Feed

Precompute feeds by fan-out on write for ordinary accounts: each new post id is pushed into every follower's feed list. Skip that for accounts with millions of followers and pull their recent posts at read time. On a read, merge the candidate sets, rank them and return the top page. The hybrid keeps reads fast and celebrity posts cheap.

hardPattern: Caching·From Devana's Meta question set

Problem

Design a social network's news feed end to end: how candidate posts are gathered, how they are ranked, how feeds are delivered and how they are stored.

Pay particular attention to the difference between a user with 200 friends and a page with 50 million followers.

POST /posts            {author_id, content}  -> {post_id}
GET  /feed?cursor=...  -> {posts: [...], next_cursor}

This is one of Devana's own questions, written in the style of Meta's interviews. It is not a question leaked from Meta, and Devana is not affiliated with Meta.

Requirements

• 3 × 10^9 users and 10^6 feed requests per second.
• A feed loads in under a second.
• New posts from close friends appear within seconds.
• A single post may need to reach 50 million followers.
• Worth confirming first: the feed is ranked rather than chronological, so a stored feed is a list of candidates, not the final order.

Scenarios

Hints

Open one at a time, and try the problem again after each.

A worked answer

How to say it in the interview

Name both fan-out strategies and how each one fails before choosing, then introduce the hybrid as the answer to the 50-million-follower case the question points at. Put a number on a celebrity post under pure push. When you reach ranking, say how many candidates you rank and why caching the ranked feed matters for frequent refreshes.

The core in code

The read-time merge in code: the user's precomputed feed (pushed post ids) and the recent timelines of the high-fanout accounts they follow, each newest first, merged into one candidate list for ranking without sorting everything.

Python

import heapq

def merge_candidates(pushed, pulled_timelines, limit):
    """Each list holds (timestamp, post_id), newest first. Returns up to
    limit post ids, newest first, without duplicates."""
    streams = [pushed, *pulled_timelines]
    # The heap holds the newest unread entry of each stream.
    heap = [(-s[0][0], s[0][1], i, 0) for i, s in enumerate(streams) if s]
    heapq.heapify(heap)
    out, seen = [], set()
    while heap and len(out) < limit:
        _, post_id, i, j = heapq.heappop(heap)
        if post_id not in seen:               # a post can arrive by both paths
            seen.add(post_id)
            out.append(post_id)
        if j + 1 < len(streams[i]):
            ts, nxt = streams[i][j + 1]
            heapq.heappush(heap, (-ts, nxt, i, j + 1))
    return out

JavaScript

function mergeCandidates(pushed, pulledTimelines, limit) {
  // Each list holds [timestamp, postId], newest first.
  const streams = [pushed, ...pulledTimelines];
  const next = streams.map(() => 0); // index of each stream's newest unread entry
  const out = [];
  const seen = new Set();
  while (out.length < limit) {
    // The newest head across the streams; ties go to the smaller post id.
    let best = -1;
    for (let i = 0; i < streams.length; i++) {
      if (next[i] >= streams[i].length) continue;
      if (best === -1) {
        best = i;
        continue;
      }
      const [ts, id] = streams[i][next[i]];
      const [bestTs, bestId] = streams[best][next[best]];
      if (ts > bestTs || (ts === bestTs && id < bestId)) best = i;
    }
    if (best === -1) break;
    const [, postId] = streams[best][next[best]++];
    if (!seen.has(postId)) { // a post can arrive by both paths
      seen.add(postId);
      out.push(postId);
    }
  }
  return out;
}

Both versions are tested against the same cases, including every example on this page.

• The merge reads only as far as limit, so following many high-fanout accounts does not mean reading all of their history.
• Duplicates are expected: an account can cross the high-fanout threshold while its earlier posts are still in followers' pushed lists.
• The JavaScript version scans the stream heads instead of using a heap, which is just as fast for the few dozen streams a user has; with hundreds, use a heap.

Follow-up questions

Common mistakes

• Pure fan-out on write, then discovering the 50-million-follower post.
• Pure fan-out on read, which makes every refresh query hundreds of timelines.
• Storing whole posts in each feed list instead of ids.
• Ranking every candidate with the heaviest model.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with a whiteboard he can read.

Practice this problem in a mock interview

Related problems

• Select the Top Unseen Feed Posts: Filter with a set lookup, then a bounded heap ordered by score and post id.
• Design Inventory for a Flash Sale: Admission control in front, atomic reservations with expiry, and orders confirmed behind a queue.
• Caching: the pattern guide, with more practice questions.