85. Design Social Network News Feed

Design Social Network News Feed
Your aim is to write an in-memory console program that can simulate a social network news feed. Users can sign up, follow other users, create posts, reply (comment) on posts, upvote/downvote posts, and view a personalized news feed.

All data must be stored in-memory (no database).

Key Definitions

  • User: identified uniquely by userId.
  • Post: a feed item created by a user; uniquely identified by postId.
  • Comment: a reply created by a user on a post; uniquely identified by commentId.
  • Score: upvotes - downvotes for a post.
  • Comment count: number of direct comments on a post (replies to the post itself, not replies-to-comments).

Functional Requirements

1) Sign up

boolean signUp(String userId)
  • Creates a new user with id userId.
  • Returns false if userId already exists; otherwise returns true.

2) Follow

boolean follow(String followerUserId, String followeeUserId)
  • Records that followerUserId follows followeeUserId.
  • Returns false if either user does not exist or if followerUserId equals followeeUserId.
  • Idempotent: following again keeps state and returns true.

3) Post

boolean post(String postId, String userId, String content, long timestampMillis)
  • Creates a post with unique id postId by userId with text content at time timestampMillis.
  • Returns false if userId does not exist or if postId already exists; otherwise returns true.

4) Reply (comment on a post)

boolean replyToPost(String commentId, String userId, String postId, String commentText, long timestampMillis)
  • Creates a new comment with unique id commentId by userId on the post postId.
  • Returns false if userId does not exist, postId does not exist, or commentId already exists; otherwise returns true.

5) Upvote / Downvote (posts)

boolean votePost(String userId, String postId, int voteType)
  • voteType must be +1 for upvote and -1 for downvote.
  • Returns false if userId does not exist, postId does not exist, or voteType is not +1/-1.
  • Note: A user may vote multiple times on the same post as long as after each votePost() method call, final total sum of votes by them on the post is either -1, 0 or 1, else return false.
  • Returns true otherwise.

6) Show news feed

List<String> showNewsFeed(String viewerUserId, int limit)
  • Returns up to limit feed entries for viewerUserId sorted by the ranking rules.
  • Returns an empty list if viewerUserId does not exist or if limit <= 0.
  • Each returned entry must be a single string representing a post in a human-readable format.
  • Ranking rules (highest to lowest priority):
    • Followed users first: posts by users that viewerUserId follows appear before posts by users they do not follow.
    • Score: higher (upvotes - downvotes) appears first.
    • Number of comments: higher number of direct comments appears first.
    • Timestamp: more recent (timestampMillis higher) appears first.
      If still tied, smaller postId lexicographically first.

Output Format for each row

postId=<id> | user=<userId> | score=<score> (up=<u>, down=<d>) | comments=<count> | time=<timestampMillis> | text=<content>

Example single entry:
postId=p2 | user=tom | score=0 (up=0, down=0) | comments=1 | time=1100 | text=I am lord Voldemort btw 3:)

Constraints

  • 1 <= userId.length() <= 50
  • 1 <= postId.length() <= 50
  • 1 <= commentId.length() <= 50
  • 1 <= content.length() <= 5000
  • 1 <= commentText.length() <= 2000
  • timestampMillis >= 0
  • limit should be reasonably small for display (e.g., 1 <= limit <= 100), but your code may support larger values.
  • All operations must be in-memory; do not use a database.

Examples

Example 1: Followed users appear first (even if non-followed has higher score)

  • signUp(userId="tom") => true
  • signUp(userId="lucius") => true
  • signUp(userId="albus") => true
  • signUp(userId="snape") => true
  • signUp(userId="draco") => true
  • post(postId="p1", userId="tom", content="first tom post", timestampMillis=1000) => true
  • post(postId="p2", userId="tom", content="second tom post", timestampMillis=1100) => true
  • post(postId="p3", userId="albus", content="albus post with higher score", timestampMillis=1200) => true
  • follow(followerUserId="lucius", followeeUserId="tom") => true
  • votePost(userId="lucius", postId="p1", voteType=+1) => true
  • votePost(userId="snape", postId="p3", voteType=+1) => true
  • votePost(userId="draco", postId="p3", voteType=+1) => true
  • showNewsFeed(viewerUserId="lucius", limit=10) => List<String>:
    • postId=p1 | user=tom | score=1 (up=1, down=0) | comments=0 | time=1000 | text=first tom post
    • postId=p2 | user=tom | score=0 (up=0, down=0) | comments=0 | time=1100 | text=second tom post
    • postId=p3 | user=albus | score=2 (up=2, down=0) | comments=0 | time=1200 | text=albus post with higher score
    Explanation: posts by followed user tom come first. Within Tom's posts, higher score ranks first (p1 before p2). Even though p3 has the highest score, it appears after followed users' posts.

Example 2: Score tie, then comment count, then timestamp

  • signUp(userId="viewer") => true
  • signUp(userId="author") => true
  • signUp(userId="c1") => true
  • signUp(userId="c2") => true
  • signUp(userId="c3") => true
  • follow(followerUserId="viewer", followeeUserId="author") => true
  • post(postId="p10", userId="author", content="post with more comments but older", timestampMillis=2000) => true
  • post(postId="p11", userId="author", content="post with fewer comments but newer", timestampMillis=3000) => true
  • replyToPost(commentId="c100", userId="c1", postId="p10", commentText="one", timestampMillis=2100) => true
  • replyToPost(commentId="c101", userId="c2", postId="p10", commentText="two", timestampMillis=2200) => true
  • replyToPost(commentId="c102", userId="c3", postId="p11", commentText="only one", timestampMillis=3100) => true
  • showNewsFeed(viewerUserId="viewer", limit=10) => List<String>:
    • postId=p10 | user=author | score=0 (up=0, down=0) | comments=2 | time=2000 | text=post with more comments but older
    • postId=p11 | user=author | score=0 (up=0, down=0) | comments=1 | time=3000 | text=post with fewer comments but newer
    Explanation: both posts are by a followed user. Scores tie (0), so comment count breaks the tie: p10 (2 comments) ranks above p11 (1 comment), even though p11 is newer.

Example 3: Validation failures + cumulative vote rule (-1/0/1 per user per post)

  • signUp(userId="x") => true
  • signUp(userId="y") => true
  • post(postId="p20", userId="missing", content="should fail", timestampMillis=1) => false (user does not exist)
  • post(postId="p20", userId="x", content="valid post", timestampMillis=100) => true
  • post(postId="p20", userId="x", content="duplicate postId", timestampMillis=200) => false (postId already exists)
  • replyToPost(commentId="c200", userId="y", postId="p20", commentText="first comment", timestampMillis=150) => true
  • replyToPost(commentId="c200", userId="y", postId="p20", commentText="duplicate commentId", timestampMillis=160) => false (commentId already exists)
  • replyToPost(commentId="c201", userId="y", postId="missingPost", commentText="should fail", timestampMillis=170) => false (postId does not exist)
  • votePost(userId="x", postId="p20", voteType=+2) => false (invalid voteType)
  • votePost(userId="x", postId="p20", voteType=+1) => true (x's running sum becomes +1)
  • votePost(userId="x", postId="p20", voteType=+1) => false (would make x's running sum +2, not allowed)
  • votePost(userId="x", postId="p20", voteType=-1) => true (x's running sum becomes 0)
  • votePost(userId="x", postId="p20", voteType=-1) => true (x's running sum becomes -1)
  • votePost(userId="x", postId="p20", voteType=-1) => false (would make x's running sum -2, not allowed)
  • showNewsFeed(viewerUserId="missing", limit=10) => List<String> empty
  • showNewsFeed(viewerUserId="x", limit=0) => List<String> empty
  • showNewsFeed(viewerUserId="y", limit=10) => List<String>:
    • postId=p20 | user=x | score=-1 (up=1, down=2) | comments=1 | time=100 | text=valid post
    Explanation: there is 1 direct comment on p20. Votes recorded on the post are one upvote and two downvotes, so score is 1 - 2 = -1.




Please use Laptop/Desktop or any other large screen to add/edit code.