FastPrepMinimum Wizard Referral Cost

Minimum Wizard Referral Cost

Airbnb logoAirbnb● MediumFULLTIMEOA
Learn

Problem statement

There are n wizards ranked from 0 through n - 1. The string referrals[i] contains the space-separated ranks of the wizards whom wizard i can introduce. An empty string means that wizard i has no referrals.

You are wizard 0. You already know every wizard listed by wizard 0, so following an edge from wizard 0 costs 0. For every other directed referral from wizard i to wizard j, the introduction costs (j - i)2.

Return the minimum total cost needed to meet the highest-ranked wizard, n - 1. Return -1 if that wizard cannot be reached. The referral graph may contain cycles.

Function

minimumWizardReferralCost(referrals: String[]) → int

Examples

Example 1

referrals = ["1 2","3","3",""]return = 1

Wizards 1 and 2 are both known for free. Asking wizard 2 to introduce wizard 3 costs (3 - 2)^2 = 1, which is cheaper than the cost 4 route through wizard 1.

Example 2

referrals = ["3","","",""]return = 0

Wizard 0 already knows the highest-ranked wizard directly, so no paid introduction is needed.

Example 3

referrals = ["1","0",""]return = -1

The cycle between wizards 0 and 1 never reaches wizard 2.

Constraints

  • 2 <= referrals.length <= 500.
  • Each non-empty row contains distinct integer ranks separated by one space.
  • Every listed rank is in [0, referrals.length - 1].
  • The graph may contain directed cycles.

More Airbnb problems

See Airbnb hiring insights
public int minimumWizardReferralCost(String[] referrals) {
    // Write your code here.
}
referrals["1 2","3","3",""]
expected1
Checking account…