Skip to main content

355. Design Twitter

mediumAsked at Airbnb

Build a follow graph with a merged activity feed — Airbnb's host-community product uses an identical follow/feed design to let guests subscribe to hosts and see their latest listings, reviews, and availability updates.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design a simplified version of Twitter where users can post tweets, follow/unfollow others, and retrieve the 10 most recent tweets in their news feed (own + followees). Implement: postTweet(userId, tweetId), getNewsFeed(userId), follow(followerId, followeeId), unfollow(followerId, followeeId).

Constraints

  • 1 <= userId, followerId, followeeId <= 500
  • 0 <= tweetId <= 10^4
  • All tweetIds are unique
  • At most 3 * 10^4 calls in total

Examples

Example 1

Input
twitter = Twitter(); postTweet(1,5); getNewsFeed(1); follow(1,2); postTweet(2,6); getNewsFeed(1); unfollow(1,2); getNewsFeed(1);
Output
null; [5]; null; null; [6,5]; null; [5]

Explanation: After following user 2, user 1's feed includes both tweet 6 (user 2) and tweet 5 (user 1), most recent first.

Approaches

1. Timestamp + sort on getNewsFeed

Assign a global timestamp to every tweet. On getNewsFeed, collect all tweets from user and followees, sort by timestamp descending, return top 10.

Time
O(n log n) per getNewsFeed
Space
O(total tweets)
class Twitter {
  constructor() {
    this.ts = 0;
    this.tweets = new Map();
    this.follows = new Map();
  }
  postTweet(userId, tweetId) {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId).push({ ts: this.ts++, tweetId });
  }
  getNewsFeed(userId) {
    const users = new Set([userId]);
    if (this.follows.has(userId)) this.follows.get(userId).forEach(f => users.add(f));
    const all = [];
    for (const uid of users) {
      const t = this.tweets.get(uid) || [];
      all.push(...t);
    }
    return all.sort((a, b) => b.ts - a.ts).slice(0, 10).map(t => t.tweetId);
  }
  follow(followerId, followeeId) {
    if (!this.follows.has(followerId)) this.follows.set(followerId, new Set());
    this.follows.get(followerId).add(followeeId);
  }
  unfollow(followerId, followeeId) {
    if (this.follows.has(followerId)) this.follows.get(followerId).delete(followeeId);
  }
}

Tradeoff:

2. Min-heap k-way merge (top-10)

Keep each user's tweets in insertion order. Use a pointer-based min-heap to merge the most-recent tweet from each followed user. O(k log k) per getNewsFeed where k = followee count.

Time
O(k log k) per getNewsFeed
Space
O(total tweets + k)
class Twitter {
  constructor() {
    this.ts = 0;
    this.tweets = new Map();
    this.follows = new Map();
  }
  postTweet(userId, tweetId) {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    this.tweets.get(userId).push([this.ts++, tweetId]);
  }
  getNewsFeed(userId) {
    const users = [userId, ...(this.follows.get(userId) || [])];
    const candidates = [];
    for (const uid of users) {
      const t = this.tweets.get(uid);
      if (t && t.length) candidates.push([t[t.length-1][0], t[t.length-1][1], uid, t.length-1]);
    }
    candidates.sort((a, b) => b[0] - a[0]);
    const result = [];
    while (candidates.length && result.length < 10) {
      const [, tweetId, uid, idx] = candidates.shift();
      result.push(tweetId);
      if (idx > 0) {
        const t = this.tweets.get(uid);
        const next = [t[idx-1][0], t[idx-1][1], uid, idx-1];
        let pos = 0;
        while (pos < candidates.length && candidates[pos][0] > next[0]) pos++;
        candidates.splice(pos, 0, next);
      }
    }
    return result;
  }
  follow(followerId, followeeId) {
    if (!this.follows.has(followerId)) this.follows.set(followerId, new Set());
    this.follows.get(followerId).add(followeeId);
  }
  unfollow(followerId, followeeId) {
    if (this.follows.has(followerId)) this.follows.get(followerId).delete(followeeId);
  }
}

Tradeoff:

Airbnb-specific tips

Airbnb asks this to test system-design instincts in a coding wrapper. Talk through data structure choices before writing code: why a Map of arrays for tweets, why a Set for follows. Interviewers specifically probe what happens if a user follows thousands of accounts — the heap merge approach shines here because you only look at the latest tweet per user, not the whole history. Mention that in prod you would add pagination and discuss fanout-on-write vs fanout-on-read tradeoffs.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →