355. Design Twitter

Design a simplified Twitter: postTweet(userId, tweetId), follow/unfollow(followerId, followeeId), and getNewsFeed(userId), which returns the 10 most recent tweet ids from the user and the people they follow, newest first.

Each user's tweets are already in time order. Put the newest tweet of every followed user in a max-heap and pop 10 times, pushing the next older tweet from the same user each time.

1class Twitter {
2  time = 0; tweets = new Map<number, [number, number][]>(); follows = new Map<number, Set<number>>();
3  postTweet(u: number, id: number) { (this.tweets.get(u) ?? this.tweets.set(u, []).get(u)!).push([this.time++, id]); }
4  getNewsFeed(u: number): number[] {
5    const heap = new MaxPriorityQueue<[number, number, number]>((e) => e[0]); // [time, user, index]
6    for (const x of [u, ...(this.follows.get(u) ?? [])]) {
7      const ts = this.tweets.get(x);
8      if (ts?.length) heap.enqueue([ts.at(-1)![0], x, ts.length - 1]);
9    }
10    const feed: number[] = [];
11    while (heap.size() && feed.length < 10) {
12      const [, x, i] = heap.dequeue(); feed.push(this.tweets.get(x)![i][1]);
13      if (i > 0) heap.enqueue([this.tweets.get(x)![i - 1][0], x, i - 1]);
14    }
15    return feed;
16  }
17  follow(a: number, b: number) { if (a !== b) (this.follows.get(a) ?? this.follows.set(a, new Set()).get(a)!).add(b); }
18  unfollow(a: number, b: number) { this.follows.get(a)?.delete(b); }
19}

op = Twitter()

tweets (user → time:id)

empty

follows

empty

output

null

Empty network.

1 / 0

Space: play/pause · ←/→: step