How should I practice Minimum Traveling Salesperson Tour?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Goldman Sachs phone screen problems in FastPrep.

Is Minimum Traveling Salesperson Tour associated with Goldman Sachs?

FastPrep tags this as a Goldman Sachs phone screen coding practice problem when the problem catalog has that company and stage context.

Minimum Traveling Salesperson Tour

Goldman Sachs● MediumFULLTIMEPHONE SCREEN

Learn

Problem statement

You are given a complete directed graph as a square matrix cost. A traveler starts at vertex0, visits every other vertex exactly once, and returns to vertex0.

Return the minimum total edge cost of such a tour. Costs may be asymmetric or zero. The diagonal is zero. With one vertex, the tour has cost zero.

Use subset dynamic programming with a bitmask for the visited vertices.

Function

minimumTourCost(cost: int[][]) → long

Examples

Example 1

cost = [[0,3,8],[5,0,2],[4,7,0]]return = 9

The tour0 to1 to2 to0 costs3+2+4=9; the other ordering costs20.

Example 2

cost = [[0]]return = 0

There is no edge to traverse with a single vertex.

Constraints

1 <= cost.length <= 14.
Every row has the same length as the number of vertices.
0 <= cost[i][j] <= 10^6, and cost[i][i] = 0.