Find the City With the Smallest Number of Neighbors at a Threshold Distance

MediumGraphsfloyd warshall

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

There are n cities labeled 0 to n - 1. Each edges[i] = [a, b, w] is a two-way road of length w between cities a and b. You are also given an integer distanceThreshold. For each city, count how many **other** cities can be reached from it by a path whose total length is at most distanceThreshold. Return the city with the smallest such count. If several cities tie for the smallest count, return the one with the **largest** label.

Examples

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Within distance 4: city 0 reaches `{1,2}`, city 1 reaches `{0,2,3}`, city 2 reaches `{0,1,3}`, and city 3 reaches `{1,2}`. Cities 0 and 3 tie with 2, so the larger label `3` wins.
Input: n = 3, edges = [[0,1,2],[1,2,5]], distanceThreshold = 3
Output: 2
City 0 reaches `{1}`, city 1 reaches `{0}`, city 2 reaches nothing. City 2 has the fewest.

Constraints

  • 2 <= n <= 100
  • 0 <= edges.length <= n * (n - 1) / 2
  • `edges[i] = [a, b, w]`, `a != b`, `1 <= w <= 10^4`
  • At most one road between any pair of cities
  • 1 <= distanceThreshold <= 10^4

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.