941. Mini Social Feed

Medium3.5 points estimatedDesignHash TableHeap4 hints
RPby Rohit Parihar

Build the backend of a tiny microblog as the class MiniFeed. Users and posts are plain integers.

  • postTweet(userId, tweetId) publishes a post. Posts are numbered in the order of the calls, later calls being newer.
  • getNewsFeed(userId) returns the ids of the 10 newest posts written by the user or by anyone the user currently follows, newest first. If fewer than 10 such posts exist, return all of them; the array may be empty.
  • follow(followerId, followeeId) makes the first user follow the second. Following an already followed user, or oneself, changes nothing.
  • unfollow(followerId, followeeId) stops following; if the user was not followed, nothing happens.

Feeds are always computed with the follow relations at the time of the call, including old posts.

Example 1

Input:
operations = ["MiniFeed","postTweet","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"]arguments = [[],[4,9101],[8,9102],[4],[4,8],[8,9103],[4],[4,8],[4]]
Output:
[null,null,null,[9101],null,null,[9103,9102,9101],null,[9101]]
Explanation:

User 4 first sees only their own post. After following user 8 the feed shows 9103 (newest), then 9102, then 9101. Unfollowing removes user 8's posts again.

Example 2

Input:
operations = ["MiniFeed","getNewsFeed","follow","postTweet","getNewsFeed"]arguments = [[],[12],[12,12],[12,77],[12]]
Output:
[null,[],null,null,[77]]
Explanation:

An empty feed is an empty array, and following yourself has no effect: your own post appears once.

Constraints

1 ≤ userId, followerId, followeeId ≤ 500

1 ≤ tweetId ≤ 106, values unique

At most 20000 calls in total

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(F log F + 10 log F) per getNewsFeed, O(1) per other call
Space
O(posts + follows)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.