PPractick

The problem

A delivery company picks a new warehouse city. For each city it counts how many other cities are reachable within a distance threshold, and it wants the city with the fewest such neighbours (the most isolated, so the hub serves an under-covered area). Ties go to the city with the greatest index. All pairs of distances are needed, so run Floyd–Warshall, then count per city.

Example: n = 4, edges 0-1 (3), 1-2 (1), 1-3 (4), 2-3 (1), threshold 4 → 3.

Function signature

int findTheCity(int n, const vector<array<int, 3>>& edges, int distanceThreshold);  // undirected

Test cases

Input (n, edges, threshold)	Output	Explanation
(4, [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 4)	3	Cities 0 and 3 both have 2 neighbours; 3 is larger
(5, [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], 2)	0	City 0 has only 1 neighbour
(3, [[0,1,1],[1,2,1]], 1)	2	Cities 0 and 2 tie with 1 neighbour
(2, [[0,1,5]], 4)	1	Neither reaches the other
(3, [], 5)	2	Everyone has 0 neighbours

(Confirm: edges are undirected and weighted; "within the threshold" means distance ≤ threshold; ties choose the greatest index.)

How interviewers phrase it

• "Return the city with the smallest number of cities reachable within distanceThreshold; if there are multiple, return the one with the greatest number" (LeetCode 1334).

Clarifying questions to ask

1. Is the threshold inclusive? (Yes: ≤.)
2. How are ties broken? (The greatest index.)
3. How large is n? (Up to 100, so O(n³) is fine.)

Follow-ups to expect

1. "Why Floyd–Warshall?"
2. "Alternative?"
3. "How do you implement the tie rule?"
4. "Why can't BFS work?"
5. "Complexity?"

Related questions

• Floyd warshall algorithm Hard
• M Coloring Problem Hard
• Celebrity Problem Hard
• Cycle Detection in Undirected Graph (bfs) Hard
• Detect a cycle in an undirected graph Hard
• Word ladder I Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in