Frontend Beauty
ESC

Type to search the knowledge base.

Design Twitter Lite

postTweet, follow/unfollow, getNewsFeed — hash maps of tweets and follows, merge k recent feeds for top 10.

advanced3 min read
  • dsa
  • design
  • interview
  • Google
  • Meta
  • Amazon

The problem

Design a simplified Twitter:

  • postTweet(userId, tweetId)
  • getNewsFeed(userId) → 10 most recent tweet ids from self + followees
  • follow(followerId, followeeId)
  • unfollow(followerId, followeeId)

Tweets are ordered by a global recency (post time). Users can follow themselves or not — clarify; typically feed includes own tweets regardless.

Data model

// userId → set of followeeIds
// userId → list of { time, tweetId } newest at end or front
// global clock++

Implementation

class Twitter {
  private time = 0;
  private tweets = new Map<number, { id: number; t: number }[]>();
  private follows = new Map<number, Set<number>>();

  private ensureUser(userId: number) {
    if (!this.tweets.has(userId)) this.tweets.set(userId, []);
    if (!this.follows.has(userId)) {
      const s = new Set<number>();
      s.add(userId); // always "follow" self for feed simplicity
      this.follows.set(userId, s);
    }
  }

  postTweet(userId: number, tweetId: number): void {
    this.ensureUser(userId);
    this.tweets.get(userId)!.push({ id: tweetId, t: this.time++ });
  }

  getNewsFeed(userId: number): number[] {
    this.ensureUser(userId);
    const candidates: { id: number; t: number }[] = [];
    for (const uid of this.follows.get(userId)!) {
      const list = this.tweets.get(uid) ?? [];
      // only need last 10 per user for top-10 global
      for (let i = Math.max(0, list.length - 10); i < list.length; i++) {
        candidates.push(list[i]);
      }
    }
    candidates.sort((a, b) => b.t - a.t);
    return candidates.slice(0, 10).map((x) => x.id);
  }

  follow(followerId: number, followeeId: number): void {
    this.ensureUser(followerId);
    this.ensureUser(followeeId);
    this.follows.get(followerId)!.add(followeeId);
  }

  unfollow(followerId: number, followeeId: number): void {
    if (followerId === followeeId) return; // keep self
    this.follows.get(followerId)?.delete(followeeId);
  }
}
op time (this version)
post O(1) amortized
follow/unfollow O(1)
getNewsFeed O(F · 10 + F·10 log) sort small

Heap merge (interview upgrade)

If users have huge tweet lists, merge with a max-heap of pointers into each followee’s newest tweets — classic k-way merge. Mention it; for LC constraints, collect+sort of last 10 each is enough.

// sketch: push {tweet, user, index} for each followee's last tweet
// pop 10 times, each time push previous tweet from same user

Brute design

Store all tweets globally, filter by follow set each feed call. O(total tweets) per feed — fails at scale, fine as “what not to do.”

Edge cases

  • Unfollow self — ignore
  • Follow same user twice
  • Empty feed
  • User posts before ensureUser on followee
  • Exactly 10+ tweets — order by time, not tweetId

Common mistakes

  • Forgetting own tweets in feed
  • Sorting by tweetId instead of time
  • Unfollow deleting self from set permanently
  • Mutating shared follow sets across users

Interview delivery

  1. APIs + recency clock.
  2. Maps for tweets and adjacency of follows.
  3. Feed = merge self+followees, top 10.
  4. Edge cases on unfollow self.
  5. Complexity + heap optimization talk track.

Further reading