How should I practice Shortest Round Trip Through All Deliveries?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Shortest Round Trip Through All Deliveries associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Shortest Round Trip Through All Deliveries

Google● HardFULLTIMEONSITE INTERVIEW

Problem statement

You are given a rectangular grid containing one start, open cells, obstacles, and delivery points:

S is the unique start.
D is a delivery point.
. is an open cell.
# is an obstacle.

From an open cell, the courier may move one cell up, down, left, or right at unit cost. The courier must start at S, visit every D at least once in any order, and return to S.

Return the minimum total travel distance. Return -1 when no such round trip exists. Only the distance is required, so equally short routes need no tie-breaker.

Function

shortestDeliveryRoundTrip(grid: String[]) → int

Examples

Example 1

grid = ["S.D","...","D.."]return = 8

Each delivery is two steps from the start, and the two deliveries are four steps apart. Visiting them in either order and returning costs 2 + 4 + 2 = 8.

Example 2

grid = ["S..#","##.#","D..D"]return = 14

The start-to-left-delivery distance is 6, the delivery-to-delivery distance is 3, and the right delivery is 5 steps from the start. The minimum round trip therefore costs 14.

Constraints

1 <= grid.length <= 30.
1 <= grid[i].length <= 30, and every row has the same length.
Each cell is S, D, ., or #.
The grid contains exactly one S and from 1 through 9 cells marked D.