Marauder Bot

Problem

Design a simplified social feed supporting four operations: post a new tweet from a user, have one user follow or unfollow another, and retrieve a user's news feed as the 10 most recent tweet ids from themselves and everyone they follow, most recent first.

Example. If user 1 posts tweet 5, then follows user 2, and user 2 posts tweet 6, user 1's feed returns [6, 5], with 6 first since it is more recent.

Key idea

The naive approach collects every tweet from a user and everyone they follow, then sorts by time for each feed request, repeating the sorting work from scratch every time. Since each user's own tweets are already produced in chronological order, the feed problem is really about merging several already-ordered lists, one per followed user, and taking the top 10 by recency.

Store each user's tweets as a list alongside an increasing timestamp counter so global order is recoverable. To build a feed, gather the most recent tweets from the user and each followed user, and merge those short lists with a max-heap keyed by timestamp: repeatedly pop the most recent tweet across all the lists, advancing that list's pointer, until 10 tweets are collected or every list is exhausted. Following and unfollowing just add or remove an id from a per-user set of followees, and play no part until the next feed request.

Solution

// Minimal binary heap; the comparator (hasPriority) decides min-heap or max-heap order.
class Heap<T> {
  private readonly items: T[] = [];

  constructor(private readonly hasPriority: (a: T, b: T) => boolean) {}

  get size(): number {
    return this.items.length;
  }

  push(item: T): void {
    this.items.push(item);
    let i = this.items.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.hasPriority(this.items[parent], this.items[i])) {
        break;
      }
      [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];
      i = parent;
    }
  }

  pop(): T {
    const top = this.items[0];
    const last = this.items.pop()!;
    if (this.items.length > 0) {
      this.items[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  private bubbleDown(start: number): void {
    let i = start;
    while (true) {
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      let next = i;
      if (left < this.items.length && this.hasPriority(this.items[left], this.items[next])) {
        next = left;
      }
      if (right < this.items.length && this.hasPriority(this.items[right], this.items[next])) {
        next = right;
      }
      if (next === i) {
        break;
      }
      [this.items[i], this.items[next]] = [this.items[next], this.items[i]];
      i = next;
    }
  }
}

interface Tweet {
  tweetId: number;
  timestamp: number;
}

interface FeedCandidate {
  timestamp: number;
  tweetId: number;
  tweets: Tweet[]; // the source user's tweet list this candidate came from
  index: number; // position within that list, walked backward from the end
}

const FEED_SIZE = 10;

class Twitter {
  private timestamp = 0;
  private readonly tweetsByUser = new Map<number, Tweet[]>();
  private readonly followeesByUser = new Map<number, Set<number>>();

  postTweet(userId: number, tweetId: number): void {
    const tweets = this.tweetsByUser.get(userId) ?? [];
    tweets.push({ tweetId, timestamp: this.timestamp++ });
    this.tweetsByUser.set(userId, tweets);
  }

  getNewsFeed(userId: number): number[] {
    const followees = this.followeesByUser.get(userId) ?? new Set<number>();
    const sources = new Set<number>([userId, ...followees]); // feed always includes the user's own tweets
    const heap = new Heap<FeedCandidate>((a, b) => a.timestamp > b.timestamp); // max-heap: most recent tweet first

    for (const source of sources) {
      const tweets = this.tweetsByUser.get(source);
      if (tweets && tweets.length > 0) {
        const index = tweets.length - 1;
        heap.push({ timestamp: tweets[index].timestamp, tweetId: tweets[index].tweetId, tweets, index });
      }
    }

    const feed: number[] = [];
    while (feed.length < FEED_SIZE && heap.size > 0) {
      const candidate = heap.pop();
      feed.push(candidate.tweetId);

      if (candidate.index > 0) {
        const nextIndex = candidate.index - 1; // advance to that source's next-most-recent tweet
        heap.push({
          timestamp: candidate.tweets[nextIndex].timestamp,
          tweetId: candidate.tweets[nextIndex].tweetId,
          tweets: candidate.tweets,
          index: nextIndex,
        });
      }
    }

    return feed;
  }

  follow(followerId: number, followeeId: number): void {
    if (followerId === followeeId) {
      return;
    }
    const followees = this.followeesByUser.get(followerId) ?? new Set<number>();
    followees.add(followeeId);
    this.followeesByUser.set(followerId, followees);
  }

  unfollow(followerId: number, followeeId: number): void {
    this.followeesByUser.get(followerId)?.delete(followeeId);
  }
}

Complexity

Time: O(F log F) to build one feed, where F is the number of followees, since each contributes at most 10 candidates into the heap merge; O(1) for post, follow, and unfollow.
Space: O(users + tweets) to store all posted tweets and follow relationships.

Watch out for

A user's own feed always includes their own tweets, even if they never explicitly follow themselves.
Only the 10 most recent tweets per followee are ever needed as merge candidates, so there is no reason to pull a followee's entire tweet history into the heap.

Pattern

This is a k-way merge problem in disguise: many individually sorted sources, one per followee, must be combined into a single ranked result, and a heap is the standard tool for merging sorted lists without concatenating and re-sorting everything.

Design Twitter