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

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

What is this problem about?

The Find the City With the Smallest Number of Neighbors at a Threshold Distance interview question is a graph-based reachability problem. You are given a set of cities and weighted edges representing the distances between them. You are also given a distanceThreshold. Your goal is to find the city that can reach the smallest number of other cities within this threshold. If multiple cities tie for the smallest count, you return the one with the largest index.

Why is this asked in interviews?

Companies like Uber, Microsoft, and Google use the Find the City With the Smallest Number of Neighbors coding problem to test a candidate's mastery of "All-Pairs Shortest Path" algorithms. It evaluates your ability to handle weighted graphs and choose the most appropriate algorithm (like Floyd-Warshall or multiple Dijkstra runs) based on the problem constraints. It’s a core Graph interview pattern.

Algorithmic pattern used

This problem is typically solved using the Floyd-Warshall Algorithm.

1. Initialize: Create a 2D distance matrix dist[n][n] initialized to infinity, with dist[i][i] = 0.
2. Edge Mapping: Fill the matrix with the given edge weights.
3. Triple Loop: Iterate through all possible intermediate cities k to find shorter paths between any two cities i and j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
4. Counting: For each city, count how many other cities have dist[i][j] <= distanceThreshold.
5. Comparison: Track the city with the minimum count and handle ties using the city index.

Example explanation

Cities: 0, 1, 2. Threshold: 3. Edges: (0-1, weight 3), (1-2, weight 1).

• City 0: Can reach City 1 (dist 3). Count = 1.
• City 1: Can reach City 0 (dist 3) and City 2 (dist 1). Count = 2.
• City 2: Can reach City 1 (dist 1). It CANNOT reach City 0 because dist(2-0) = $1+3 = 4 > 3$. Count = 1. Tied cities are 0 and 2. Result: 2 (largest index).

Common mistakes candidates make

• Wrong Algorithm: Using BFS for a weighted graph. BFS only finds shortest paths in unweighted graphs.
• Initialization: Forgetting to set dist[i][i] = 0 or using a value for "infinity" that is too small.
• Tie-breaking: Forgetting the rule to return the largest city ID in case of a tie.

Interview preparation tip

Master the Floyd-Warshall algorithm for "All-Pairs" problems. While Dijkstra is better for "One-to-All," Floyd-Warshall's simplicity ($O(N^3)$) makes it the preferred choice for dense graphs or when you need reachability info for every single node.