City With Fewest Reachable Neighbors Under a Threshold

Reported in interviews at Akuna Capital

Problem statement

There are $n$ cities labeled $0 \dots n-1$ connected by weighted bidirectional roads given as $\mathrm{edges}[j] = [u, v, w]$ with weight $w$. Given an integer $\mathrm{distanceThreshold}$, for each city count how many other cities are reachable with a total path distance at most $\mathrm{distanceThreshold}$. Return the city with the smallest such count; if several tie, return the one with the greatest label.

Constraints:

  • $2 \le n \le 100$
  • Edge weights and $\mathrm{distanceThreshold}$ are non-negative integers.

Examples:

  • $n = 4$, $\mathrm{edges} = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]]$, $\mathrm{distanceThreshold} = 4 \to 3$. Cities $0$ and $3$ each reach $2$ others; the tie breaks toward the larger label $3$.
  • $n = 5$, $\mathrm{edges} = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]]$, $\mathrm{distanceThreshold} = 2 \to 0$.
Show hint

What does reachable within the threshold mean when two cities can be linked through other cities, not just by one road?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems