How should I practice Cities on Shortest Delivery Routes?

Start by reading the full statement, solve the visible examples, then compare the pattern against related MathWorks online assessment problems in FastPrep.

Is Cities on Shortest Delivery Routes associated with MathWorks?

FastPrep tags this as a MathWorks online assessment coding practice problem when the problem catalog has that company and stage context.

Cities on Shortest Delivery Routes

MathWorks● MediumNEW GRADOA

Problem statement

Source note: This is another coding question from the same MathWorks new-grad online assessment, shared as photos. The photos give the task: a connected map with two-way roads of different lengths, packages sent from the capital along any shortest route, and, for every city, a count of the other cities a delivery to it could go through, leaving out the capital and that city. They also show the example map with the capital at city 2. The expected output, the function signature and the limits were not in the photos.

Practice choices: the function name and the input shape (n, a list of [a, b, w] roads, and the capital), cities numbered from 1, the answer array in city order, and all limits. Every city on any shortest route counts, not only the one right before the target; that is our reading of the photo, which asks about every city a package could pass through on its way. We worked out the expected output of the first example ourselves, and the other two examples are ours.

The judged task matches the report at about 85%.

A country has n cities numbered 1 to n, joined by two-way roads. roads[i] = [a, b, w] is a road of length w between cities a and b.

Packages start at the capital city capital and always travel along a shortest route. When several routes tie for the shortest length, any of them may be used.

For each city i, count the cities that a package for city i might pass through on the way. A city counts if it lies on at least one shortest route from the capital to city i. Do not count the capital or city i itself, so the capital's own count is 0.

Return an array answer of length n, where answer[i - 1] is the count for city i.

Function

countDeliveryPredecessors(n: int, roads: int[][], capital: int) → int[]

Examples

Example 1

n = 6roads = [[3,2,2],[3,5,2],[3,6,2],[5,4,1],[2,4,1],[2,1,1],[6,4,1],[6,1,1]]capital = 2return = [0,0,0,0,1,2]

This is the map from the report, with the capital at city 2. Cities 1, 3, and 4 are reached directly from the capital by their shortest routes, so their counts are 0. The only shortest route to city 5 is 2 → 4 → 5 (length 2), which passes city 4. City 6 has two shortest routes of length 2, 2 → 4 → 6 and 2 → 1 → 6, so cities 4 and 1 both count. The capital's own count is 0.

Example 2

n = 5roads = [[1,2,1],[2,3,1],[3,4,1],[1,4,5],[4,5,2]]capital = 1return = [0,0,1,2,3]

The road 1 - 4 (length 5) is longer than going 1 → 2 → 3 → 4 (length 3), so it is never used. City 5 is reached by 1 → 2 → 3 → 4 → 5, which passes cities 2, 3, and 4, so its count is 3. Every city on the route counts, not only the one just before city 5.

Example 3

n = 4roads = [[1,2,1],[1,3,1],[2,4,1],[3,4,1]]capital = 1return = [0,0,0,2]

City 4 has two shortest routes, 1 → 2 → 4 and 1 → 3 → 4, so both cities 2 and 3 count. Cities 2 and 3 are next to the capital, so their counts are 0.

Constraints

2 <= n <= 1000
n - 1 <= roads.length <= 3000
roads[i].length == 3 and roads[i] = [a, b, w] with 1 <= a, b <= n and a != b
1 <= w <= 1000
No two roads join the same pair of cities, and every city can be reached from every other city.
1 <= capital <= n

Source note: Photos of the original assessment screen: the statement with its notes, and the example map. Margins were cropped. The rest of the question was not photographed.