FastPrepFewest Users to Reach Everyone
Problems/Fewest Users to Reach Everyone

Fewest Users to Reach Everyone

Airbnb logoAirbnb● HardINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Airbnb software engineer intern technical interview in the United States in November 2017. After an online coding challenge, the candidate had two technical interviews held online, one straight after the other, and then a cross-functional interview. This question came from the technical interviews.

The question was about a follower network in which every post is reshared by all followers of each user who receives it, and it asked for the fewest users whose posts would reach the whole network. Here, users are numbered 0 to n - 1, each pair [a, b] says that b follows a, and a user who posts a tweet also counts as seeing it. Because many smallest sets can exist, you return the one that comes first in sorted order. The limits and the examples are our own.

Our version is about 80% the same as the reported question.

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 <= 104
  • 0 <= edges.length <= 2 * 104
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] < n
  • edges[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 Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)

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)
All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public List<Integer> findSmallestSeedSet(int n, List<List<Integer>> edges) {
      // Write your code here.
    }
}
Checking account…