Quick 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.

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

  1. 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.
  2. 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.
  3. 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.

Social Network News Feed from an Operation Log

mediumPinduoduoSoftware Engineer

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

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

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

Examples

Example 1
Input
([['feed', 1]],)
Output
[[]]
Notes
Minimum valid input: one feed request for a user with no posts returns one empty feed.
Example 2
Input
([['post', 5, 9], ['follow', 5, 6], ['unfollow', 5, 6]],)
Output
[]
Notes
No feed request, so the result is an empty list.

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

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def run_feed_operations(operations: list[list[str]]) -> list[list[int]]:
Sample call
run_feed_operations([['feed', 1]])
Language
Case 1
Input
([['feed', 1]],)
Expected
[[]]
Case 2
Input
([['post', 5, 9], ['follow', 5, 6], ['unfollow', 5, 6]],)
Expected
[]

Browse More Questions

Show the approach

Approach

Give every post a publication time equal to the number of posts published before it, and keep a global array from time to post id. For every user keep the list of their own publication times (it only grows, so it stays ascending) and a hash set of the users they follow. A self-follow is never stored, a repeated follow is absorbed by the set, and unfollowing someone who is not in the set changes nothing, so every no-op rule holds by construction.

For a feed request by user u, the qualifying authors are u plus the members of u's follow set at that moment. Keep a buffer of at most 10 publication times, sorted ascending. Scan each qualifying author's times from newest to oldest: insert each time into the buffer and drop the smallest entry when the buffer grows to 11, and stop scanning that author as soon as the buffer is full and the current time is smaller than the buffer's smallest entry.

Invariant: after any prefix of the scan, the buffer holds exactly the min(10, seen) largest times among the posts seen so far. Stopping early is safe because an author's list is sorted: once one of their posts is older than the buffer's smallest entry, every older post of theirs is too and could never enter. Publication times are unique, so there are no ties. Reading the buffer from largest to smallest and mapping times to post ids gives the feed from most recent to least recent, independent of post id values.

Because the follow set is read at request time, posts published before a follow started are included, an unfollowed author's posts (old and new) are excluded, and a refollow restores them. The user's own posts always qualify but still compete for the 10 slots. Edge cases: a user id that never appeared has no posts and no follows, so its feed is empty; a list without feed requests returns an empty list.

Time complexity:
O(n + sum over feed requests of (f + 1)), where n = len(operations) and f is the number of users the requester follows at that moment; each author costs at most 11 insertions into a 10-entry buffer, a constant factor
Space complexity:
O(n)