Simulate a Social Feed With Follows, Unfollows and the 10 Most Recent Posts
Company: Pinduoduo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement the core of a small social network in which users publish posts, follow and unfollow other users, and read a news feed. A user's news feed shows the 10 most recent posts written by the user or by anyone the user currently follows. So that the result can be checked as a single function, the operations arrive as one list, and you return the output of every feed request in order.
### Function Signature
```python
def run_feed_operations(operations: list[list[str | int]]) -> list[list[int]]:
```
### Rules
- Each operation has one of four forms:
- `["post", user_id, post_id]`: user `user_id` publishes a new post with id `post_id`.
- `["follow", follower_id, followee_id]`: `follower_id` starts following `followee_id`.
- `["unfollow", follower_id, followee_id]`: `follower_id` stops following `followee_id`.
- `["feed", user_id]`: request the news feed of `user_id`.
- Operations are applied in list order. A post is more recent than every post published by an earlier operation.
- The feed of user `u` contains the posts written by `u` and by every user `u` follows at the moment of the request, including posts published before the follow started. Posts by a user whom `u` no longer follows are excluded.
- The feed lists at most 10 post ids, from most recent to least recent. If fewer than 10 posts qualify, it lists all of them; if none qualify, it is an empty list.
- A user always sees their own posts. Following or unfollowing oneself has no effect. Following a user who is already followed, or unfollowing a user who is not followed, has no effect.
- Users need no registration: any id may appear in any operation, and a user who has never posted or followed anyone has an empty feed.
- Return a list with one entry per `"feed"` operation, in the order those operations appear.
### Constraints
- `1 <= len(operations) <= 3 * 10^4`
- `1 <= user id <= 10^4`
- `0 <= post_id <= 10^9`, and no two `"post"` operations use the same post id.
- Every operation is well formed: its first element is one of the four names above, followed by the stated number of integers.
### Examples
**Example 1**
```text
Input: operations = [["post", 1, 101], ["post", 2, 202], ["follow", 1, 2], ["post", 3, 303],
["feed", 1], ["feed", 3], ["follow", 1, 3], ["feed", 1],
["unfollow", 1, 2], ["feed", 1]]
Output: [[202, 101], [303], [303, 202, 101], [303, 101]]
```
User 1 starts following user 2 after post 202 was published, and that post still appears. Post 303 by user 3 enters user 1's feed only once user 1 follows user 3. After user 1 unfollows user 2, post 202 disappears from the feed.
**Example 2**
```text
Input: operations = [["post", 7, 40], ["post", 7, 5], ["post", 7, 33], ["post", 7, 12],
["post", 7, 90], ["post", 7, 7], ["post", 7, 61], ["post", 7, 28],
["post", 7, 19], ["post", 7, 74], ["post", 7, 3], ["post", 7, 50],
["feed", 7]]
Output: [[50, 3, 74, 19, 28, 61, 7, 90, 12, 33]]
```
Twelve posts qualify. The feed keeps the 10 most recent, ordered by when they were published rather than by id, so the two oldest posts, 40 and 5, are left out.
**Example 3**
```text
Input: operations = [["feed", 4], ["follow", 4, 4], ["unfollow", 4, 4], ["post", 4, 0],
["feed", 4], ["unfollow", 4, 9], ["follow", 4, 9], ["follow", 4, 9],
["post", 9, 50], ["feed", 4], ["feed", 9]]
Output: [[], [0], [50, 0], [50]]
```
User 4's first feed is empty. Unfollowing themselves does not hide their own post 0. Unfollowing user 9 before following has no effect, and the repeated follow is harmless. User 9's feed does not include user 4's post, because user 9 does not follow user 4.
Overview: Simulate a small social network in which users publish posts, follow and unfollow other users, and request a news feed of the 10 most recent posts by themselves and the users they follow. Tests choosing data structures for follow sets and per-user post histories, and merging recent posts efficiently by recency.
Implement the core of a small social network in which users publish posts, follow and unfollow other users, and read a news feed. A user's news feed shows the 10 most recent posts written by that user or by anyone that user currently follows.
So that the whole session can be checked as one function call, the operations arrive as one list, `operations`, and `run_feed_operations(operations)` returns the output of every feed request in order.
### Operations
Each operation has one of four forms:
- `["post", user_id, post_id]`: user `user_id` publishes a new post with id `post_id`.
- `["follow", follower_id, followee_id]`: `follower_id` starts following `followee_id`.
- `["unfollow", follower_id, followee_id]`: `follower_id` stops following `followee_id`.
- `["feed", user_id]`: request the news feed of `user_id`.
### Rules
- Operations are applied in list order. A post is more recent than every post published by an earlier operation, so recency comes from the order of the operations, not from the post id.
- The feed of user `u` contains the posts written by `u` and by every user `u` follows at the moment of the request, including posts published before the follow started. Posts by a user whom `u` no longer follows are excluded. Only direct follows count: if `u` follows `v` and `v` follows `w`, the posts of `w` are not in the feed of `u` unless `u` also follows `w`.
- A feed lists at most 10 post ids, from most recent to least recent. If fewer than 10 posts qualify, it lists all of them; if none qualify, it is an empty list.
- A user always sees their own posts: they always qualify for that user's feed, under the same 10-post limit. Following or unfollowing oneself has no effect. Following a user who is already followed, or unfollowing a user who is not followed, has no effect.
- Users need no registration: any id may appear in any operation, and a user who has never posted or followed anyone has an empty feed.
- Return a list with one entry per `"feed"` operation, in the order those operations appear. With no `"feed"` operation the result is an empty list.
No value exceeds 2^31 - 1, so every id fits in a 32-bit `int` in Java and C++.
### Input format by language
- Python and JavaScript: each operation is a list holding the operation name as a string followed by integers.
- Java: `operations` is a `java.util.List<java.util.List<Object>>`. The first element of each operation is a `String` and every id is a `java.lang.Number`, so read ids with `((Number) value).intValue()`.
- C++: `operations` is a `std::vector<std::vector<std::string>>`. Every element arrives as a string, ids written in decimal (for example `{"post", "1", "101"}`), so convert ids with `std::stoi`.
### Example 1
```text
Input: operations = [["post", 1, 101], ["post", 2, 202], ["follow", 1, 2], ["post", 3, 303],
["feed", 1], ["feed", 3], ["follow", 1, 3], ["feed", 1],
["unfollow", 1, 2], ["feed", 1]]
Output: [[202, 101], [303], [303, 202, 101], [303, 101]]
```
User 1 starts following user 2 after post 202 was published, and that post still appears. Post 303 by user 3 enters the feed of user 1 only once user 1 follows user 3. After user 1 unfollows user 2, post 202 disappears from the feed.
### Example 2
```text
Input: operations = [["post", 7, 40], ["post", 7, 5], ["post", 7, 33], ["post", 7, 12],
["post", 7, 90], ["post", 7, 7], ["post", 7, 61], ["post", 7, 28],
["post", 7, 19], ["post", 7, 74], ["post", 7, 3], ["post", 7, 50],
["feed", 7]]
Output: [[50, 3, 74, 19, 28, 61, 7, 90, 12, 33]]
```
Twelve posts qualify. The feed keeps the 10 most recent, ordered by when they were published rather than by id, so the two oldest posts, 40 and 5, are left out.
### Constraints
- `1 <= len(operations) <= 3 * 10^4`
- `1 <= user id <= 10^4` for every `user_id`, `follower_id` and `followee_id`
- `0 <= post_id <= 10^9`, and no two `"post"` operations use the same post id
- Every operation is well formed: its first element is one of `"post"`, `"follow"`, `"unfollow"`, `"feed"`, followed by the stated number of integers
Constraints
- 1 <= len(operations) <= 3 * 10^4
- 1 <= user id <= 10^4 for every user_id, follower_id and followee_id
- 0 <= post_id <= 10^9, and no two "post" operations use the same post id
- Every operation is well formed: its first element is one of "post", "follow", "unfollow", "feed", followed by the stated number of integers
Examples
Input: ([['feed', 1]],)
Expected Output: [[]]
Explanation: Minimum valid input: one feed request for a user with no posts returns one empty feed.
Input: ([['post', 5, 9], ['follow', 5, 6], ['unfollow', 5, 6]],)
Expected Output: []
Explanation: No feed request, so the result is an empty list.
Hints
- Recency is decided by the position of each "post" operation in the list, not by the post id, so you need to remember when each post was published.
- Whom a user follows is checked at the moment of the feed request, so a follow or unfollow affects that author's whole history, older posts included.
- Only the 10 newest qualifying posts are returned, and each author's posts already arrive in publication order: consider how much of each author's history a single feed request really needs to look at.