codejump
MediumPro challengePythonJavaScriptTypeScript

System Design — News Feed

System DesignHeapHash Map

A tiny Twitter: users post, follow each other, and read a feed of the most recent posts from
themselves and the people they follow.

solve(args, ops) builds new Feed() and replays ops. Time is implicit: later calls are
newer.

  • post(user, postId) — user publishes postId (ids are unique). Returns nothing.
  • follow(follower, followee) / unfollow(follower, followee) — change who follower follows.

Following yourself, following twice or unfollowing someone you do not follow changes nothing.
 Return nothing.

  • feed(user) — return the ids of the 10 most recent posts written by user **or anyone

user currently follows**, newest first. Unfollowing removes that person's posts from the
 feed immediately.

The production designs are *fan-out on read* (merge the followees' timelines with a heap — a
k-way merge) or *fan-out on write* (push each post into every follower's feed). Either is fine
here; know the trade-off.

Example

post(1,5) feed(1) → [5]    follow(1,2) post(2,6) feed(1) → [6,5]
unfollow(1,2) feed(1) → [5]

Sample tests

Test #1Classic example
Input: [[],[["post",1,5],["feed",1],["follow",1,2],["post",2,6],["feed",1],["unfollow",1,2],["feed",1]]]
Output: [null,[5],null,null,[6,5],null,[5]]
Test #2Interleaved authors and no-op follow changes
Input: [[],[["post",1,1],["post",2,2],["post",1,3],["follow",3,1],["follow",3,2],["feed",3],["post",3,4],["feed",3],["unfollow",3,9],["follow",3,3],["feed",3]]]
Output: [null,null,null,null,null,[3,2,1],null,[4,3,2,1],null,null,[4,3,2,1]]
Test #3The feed is capped at 10 posts
Input: [[],[["post",1,1],["post",1,2],["post",1,3],["post",1,4],["post",1,5],["post",1,6],["post",1,7],["post",1,8],["post",1,9],["post",1,10],["post",1,11],["post",1,12],["feed",1]]]
Output: [null,null,null,null,null,null,null,null,null,null,null,null,[12,11,10,9,8,7,6,5,4,3]]
← All challenges