LC 355 — Problem

Design a simplified Twitter with four operations: postTweet(userId, tweetId), follow(followerId, followeeId), unfollow(followerId, followeeId), and getNewsFeed(userId) which returns the 10 most recent tweet ids posted by the user or anyone they follow, newest first.

Example: postTweet(1, 5); getNewsFeed(1) ⟶ [5]
… follow(1, 2); postTweet(2, 6); getNewsFeed(1) ⟶ 65

Constraints: at most 3·10⁴ total calls; all ids in [1, 500].

You open Twitter. You scroll. Tweets from 47 accounts interleave seamlessly — newest first, regardless of who posted it. You've never wondered how.

Here's what your feed is NOT doing: it's not collecting every tweet from every account, dumping them in a pile, and re-ordering from scratch. That would work for 4 accounts. For 4,000 accounts posting 10 tweets each, it's 40,000 items touched per refresh. Your phone would melt.

Phase 1: Set up your world. Post, follow, unfollow.

Three users: A, B, C. Your job: post three tweets as A, follow B, unfollow C. Watch the global timestamp counter and the follows[A] chip change.

timestampt = 0
follows[A]
{}
Each tap prepends a tweet at index 0 of User A's timeline.
What the three handlers look like in code
1
let timestamp = 0;
2
const userTweets = new Map<number, { time: number, id: number }[]>();
3
const follows = new Map<number, Set<number>>();
4
5
function postTweet(userId: number, tweetId: number) {
6
  timestamp += 1;
7
  const list = userTweets.get(userId) ?? [];
8
  list.unshift({ time: timestamp, id: tweetId });  // prepend → newest at index 0
9
  userTweets.set(userId, list);
10
}
11
12
function follow(a: number, b: number) {
13
  const set = follows.get(a) ?? new Set<number>();
14
  set.add(b);
15
  follows.set(a, set);
16
}
17
18
function unfollow(a: number, b: number) {
19
  follows.get(a)?.delete(b);
20
}

You're about to post 3 tweets as User A. Each call is postTweet(A, tweetId) with no timestamp argument. Where does each tweet's ordering come from?