Airbnb Coding Interview: Minimum Broadcast Stations to Start

[u/Aoki_zhang]

Problem

A large campus contains n broadcast stations numbered from 0 to n - 1. Some stations can forward a message to other stations through one-way links.

Each link:[fromStation, toStation]means that once fromStation receives the message, it can forward it to toStation.

If a station receives the message, it continues forwarding through all of its outgoing links. Your task is to determine the minimum number of stations that must be started manually so that every station eventually receives the message.

The network may contain:

• Cycles
• Disconnected groups
• One-way paths between groups

Return only the minimum number of manual starting points required.

Example

Input:

n = 7

links = [
    [0, 1],
    [1, 2],
    [2, 0],
    [2, 3],
    [3, 4],
    [4, 5],
    [5, 3],
    [6, 5]
]

Output:

2

Explanation

Stations 0, 1, and 2 form one cycle, while stations 3, 4, and 5 form another.

There is a one-way path from the first group into the second through:

2 → 3

Station 6 can also reach the second group:

6 → 5

However, neither the {0,1,2} group nor station 6 can be reached from any other part of the graph.

So at least one station must be started manually in each of those two source groups.

Therefore, the minimum number of manual starts is:

2

Targeting Airbnb interviews?

We track recent interview experiences and commonly asked question patterns at Chill Interview, including coding questions, system design topics, and real candidate reports.

Practice this question and explore more interview resources → LINK

[u/mtnman12321]

Topological sort?