Design Twitter

Examples

Input: postTweet(1, 5); getNewsFeed(1)
Output: [5]

User 1's feed contains only their own tweet.

Input: follow(1, 2); postTweet(2, 6); getNewsFeed(1)
Output: [6, 5]

User 1 now follows user 2, so user 2's tweet (6) appears too, ahead of user 1's older tweet (5) since it's more recent.

Input: unfollow(1, 2); getNewsFeed(1)
Output: [5]

After unfollowing user 2, their tweets drop out of user 1's feed again.

Constraints

• 1 <= userId, followerId, followeeId <= 500

• 0 <= tweetId <= 10^4

• All tweetId values are unique

• At most 3 * 10^4 calls total across all four operations

Approach

Give every posted tweet a timestamp using a simple ever-increasing counter, so any two tweets can be compared for recency regardless of who posted them. Store each user's tweets in their own list, in the order they were posted (which is automatically time-sorted).

Building a full news feed is then a merge of several sorted lists (the user's own list, plus one list per followee) - keeping only the top 10. Rather than combining every tweet from every relevant user, a max-heap only needs to hold one "frontier" tweet per relevant user at a time: pop the most recent tweet overall, then push that same user's next-most-recent tweet to take its place, repeating 10 times. This finds the top 10 without ever looking at more than a small number of tweets from any one list.

Solutions

Brute Force - Collect All and Sort

Gather every tweet from the user and everyone they follow into one array, sort all of it by timestamp, and take the 10 most recent.

class Twitter {
  constructor() {
    this.timestamp = 0;
    this.tweets = new Map(); // userId -> [[timestamp, tweetId], ...]
    this.followees = new Map(); // userId -> Set of followeeIds
  }

  postTweet(userId, tweetId) {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId).push([this.timestamp++, tweetId]);
  }

  follow(followerId, followeeId) {
    if (followerId === followeeId) return;
    if (!this.followees.has(followerId)) this.followees.set(followerId, new Set());
    this.followees.get(followerId).add(followeeId);
  }

  unfollow(followerId, followeeId) {
    if (this.followees.has(followerId)) {
      this.followees.get(followerId).delete(followeeId);
    }
  }

  getNewsFeed(userId) {
    const relevant = new Set([userId, ...(this.followees.get(userId) || [])]);
    let all = [];
    for (const uid of relevant) {
      const list = this.tweets.get(uid);
      if (list) all = all.concat(list);
    }
    all.sort((a, b) => b[0] - a[0]);
    return all.slice(0, 10).map((entry) => entry[1]);
  }
}

Time: O(1) for postTweet/follow/unfollow; O(T log T) for getNewsFeed, where T is the total number of tweets from the user and their followees · Space: O(T) total tweets stored, plus O(T) per getNewsFeed call

Optimal - Heap Merge of Per-User Tweet Lists

Each user's tweets are already stored in time order. Instead of combining every tweet, keep just one 'current' tweet per relevant user in a max-heap, always pulling in that same user's next tweet after popping their most recent one - stopping once 10 tweets are collected.

class MaxHeap {
  constructor(compare) {
    this.data = [];
    this.compare = compare;
  }

  size() {
    return this.data.length;
  }

  push(val) {
    this.data.push(val);
    let i = this.data.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(this.data[i], this.data[parent]) > 0) {
        [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
        i = parent;
      } else break;
    }
  }

  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      let i = 0;
      const n = this.data.length;
      while (true) {
        let largest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < n && this.compare(this.data[left], this.data[largest]) > 0) largest = left;
        if (right < n && this.compare(this.data[right], this.data[largest]) > 0) largest = right;
        if (largest === i) break;
        [this.data[i], this.data[largest]] = [this.data[largest], this.data[i]];
        i = largest;
      }
    }
    return top;
  }
}

class Twitter {
  constructor() {
    this.timestamp = 0;
    this.tweets = new Map(); // userId -> [[timestamp, tweetId], ...], oldest first
    this.followees = new Map(); // userId -> Set of followeeIds
  }

  postTweet(userId, tweetId) {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId).push([this.timestamp++, tweetId]);
  }

  follow(followerId, followeeId) {
    if (followerId === followeeId) return;
    if (!this.followees.has(followerId)) this.followees.set(followerId, new Set());
    this.followees.get(followerId).add(followeeId);
  }

  unfollow(followerId, followeeId) {
    if (this.followees.has(followerId)) {
      this.followees.get(followerId).delete(followeeId);
    }
  }

  getNewsFeed(userId) {
    const relevant = [userId, ...(this.followees.get(userId) || [])];
    const heap = new MaxHeap((a, b) => a.time - b.time);

    for (const uid of relevant) {
      const list = this.tweets.get(uid);
      if (list && list.length > 0) {
        const idx = list.length - 1;
        heap.push({ time: list[idx][0], tweetId: list[idx][1], uid, idx });
      }
    }

    const result = [];
    while (result.length < 10 && heap.size() > 0) {
      const top = heap.pop();
      result.push(top.tweetId);

      if (top.idx > 0) {
        const list = this.tweets.get(top.uid);
        const newIdx = top.idx - 1;
        heap.push({ time: list[newIdx][0], tweetId: list[newIdx][1], uid: top.uid, idx: newIdx });
      }
    }

    return result;
  }
}

Time: O(1) for postTweet/follow/unfollow; O((F + 10) log F) for getNewsFeed, where F is how many users are followed · Space: O(T) total tweets stored, plus O(F) per getNewsFeed call for the heap