Fewest Users to Reach Everyone
Updated
Problem statement
A social network has n users, numbered from 0 to n - 1. You are given edges, where edges[i] = [a, b] means that user b follows user a.
When a user posts a tweet, every follower of that user retweets it. A retweet spreads the same way: every follower of a user who retweets the tweet retweets it too. A user sees a tweet if they post it or retweet it.
Choose a set of users, as small as possible, such that when every user in the set posts a tweet, every user in the network sees at least one of these tweets.
If there is more than one smallest set, return the one that comes first when each set is written as a list in increasing order and the lists are compared element by element. Return the ids of the chosen users in increasing order.
Function
findSmallestSeedSet(n: int, edges: List<List<Integer>>) → List<Integer>Examples
Example 1
n = 6edges = [[0,1],[1,2],[2,0],[3,2],[4,5]]return = [3,4]User 1 follows user 0, user 2 follows user 1 and user 0 follows user 2, so a tweet from any of these three reaches all three. User 2 also follows user 3, so a tweet from user 3 reaches users 2, 0 and 1. User 5 follows user 4. Users 3 and 4 follow nobody, so each of them sees a tweet only if they post it: both must be in the set. Tweets from users 3 and 4 already reach all six users.
Example 2
n = 4edges = [[1,2],[2,1],[2,3],[3,0]]return = [1]Users 1 and 2 follow each other, user 3 follows user 2 and user 0 follows user 3. A tweet from user 1 reaches user 2, then user 3, then user 0: everyone. A tweet from user 2 also reaches everyone. So [1] and [2] are both smallest sets, and [1] comes first.
Example 3
n = 3edges = []return = [0,1,2]Nobody follows anybody, so each user sees only the tweets they post. All three users must post.
Constraints
1 <= n <= 1040 <= edges.length <= 2 * 104edges[i].length == 20 <= edges[i][0], edges[i][1] < nedges[i][0] != edges[i][1]- All pairs
edges[i]are different.
More Airbnb Phone Screen questions
- Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
- Text JustificationPHONE SCREEN · Seen Nov 2026
- Decode and Store StringsPHONE SCREEN · Seen Oct 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
- Smallest Common RegionPHONE SCREEN · Seen Aug 2026
- Longest Chain BookingPHONE SCREEN · Seen Aug 2026
- Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
- Parse Query StringPHONE SCREEN · Seen May 2026
- Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023
Similar questions at other companies
- Course Order and CycleAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Evaluate DivisionApple · PHONE SCREENApple interview questions
- Possible BipartitionByteDance · PHONE SCREENByteDance interview questions
- Route Graph Reachability with a Broken LinkFigma · PHONE SCREENFigma interview questions
- Count Friend CirclesOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Number of IslandsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Count Connected IslandsUber · PHONE SCREENUber interview questions
- Course ScheduleNykaa · PHONE SCREENNykaa interview questions
- Number of IslandsSpaceX · PHONE SCREENSpaceX interview questions
- Pacific Atlantic Water FlowAnduril · PHONE SCREENAnduril interview questions
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
- Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)