You're building the back end of a small social app. Users publish short posts and follow each other, and each user's home screen shows the newest posts from themselves and the people they follow.
Build a class SocialFeed:
SocialFeed()starts with no users, posts or follows. Users exist as soon as they're mentioned.post(user_id, post_id)publishes a new post. Post ids are unique, and each call is newer than every earlier one.follow(follower_id, followee_id)makes the follower see the followee's posts (including ones published earlier). Following someone you already follow, or yourself, changes nothing.unfollow(follower_id, followee_id)undoes a follow. If there's no such follow (or it names yourself), nothing changes.feed(user_id) -> list[int]returns the ids of the 10 most recent posts written by the user or anyone they currently follow, newest first. Return fewer if there aren't 10.
A user always sees their own posts.
app = SocialFeed()
app.post(1, 101)
app.post(2, 201)
app.feed(1) # [101]
app.follow(1, 2)
app.feed(1) # [201, 101]
app.post(1, 102)
app.post(3, 301)
app.feed(1) # [102, 201, 101]
app.unfollow(1, 2)
app.feed(1) # [102, 101]
app.feed(4) # []
Constraints:
- User ids and post ids are integers in
[0, 10^9]; up to2 * 10^5calls in total. - A user may follow up to a few thousand others, each with thousands of posts, and
feedis called often. Collecting and sorting every post from everyone followed on each call is far too slow. - Aim for O(1)
post,followandunfollow, and O(F + 10 log F) perfeed, whereFis the number of people the user follows.
Show hint
Each followed user's posts are already in time order, so only the newest unread post of each one can be the next item on the timeline. Keep those candidates in a structure that always gives you the newest one, and replace it with that author's previous post when you take it.