FastPrepCheapest Visiting Order with Prerequisites
Problems/Cheapest Visiting Order with Prerequisites

Cheapest Visiting Order with Prerequisites

Indeed logoIndeed● HardFULLTIMEOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The last of four questions in a two-hour test asks for the cheapest way to go through n points, where moving between two points has a known cost that can differ by direction and some points must be reached before others.

The report gives no input format, example or limits. Here, you start at any point for free, visit every point exactly once by moving straight from one to the next, and do not return to the start. Each rule [a, b] means a comes before b, and the rules never form a loop. There are at most 14 points, and each move costs 0 to 10^6.

The judged task matches the report at about 80%.

There are n points numbered 0 to n - 1. Moving directly from point i to point j costs cost[i][j]. The cost can be different in the two directions.

Each rules[k] = [a, b] means point a must be visited before point b.

Choose any starting point, at no cost. Then visit every point exactly once, moving directly from each point to the next one, and stop at the last point without coming back. The total cost is the sum of the costs of these moves.

Return the smallest total cost of a visiting order that follows every rule.

Function

minVisitCost(cost: int[][], rules: int[][]) → int

Examples

Example 1

cost = [[0,4,1],[2,0,6],[3,5,0]]rules = []return = 3

With no rules, every order is allowed. Starting at point 1, moving to point 0 costs 2, and then moving to point 2 costs 1, for a total of 3. No other order is cheaper. The answer is 3.

Example 2

cost = [[0,4,1],[2,0,6],[3,5,0]]rules = [[0,1],[1,2]]return = 10

Point 0 must come before point 1, and point 1 before point 2, so the only allowed order is 0, 1, 2. It costs 4 + 6 = 10. The answer is 10.

Example 3

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

Point 2 must be visited before point 0. The cheapest order overall, 3, 1, 0, 2, costs 1 + 1 + 2 = 4, but it visits point 0 before point 2, so it is not allowed. The best allowed order is 2, 3, 1, 0, which costs 4 + 1 + 1 = 6. The answer is 6.

Constraints

  • 1 <= n == cost.length == cost[i].length <= 14
  • 0 <= cost[i][j] <= 10^6 and cost[i][i] == 0
  • 0 <= rules.length <= n * (n - 1) / 2
  • rules[k] = [a, b] with 0 <= a, b < n and a != b, and no pair appears twice.
  • The rules never form a loop, so at least one order follows all of them.

More Indeed problems

  • Insert into an Unrolled Linked ListPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Course Completion OrderPHONE SCREEN · Seen May 2025
  • Recipes You Can PreparePHONE SCREEN · Seen May 2025
All Indeed interview questionsSee Indeed hiring insights
Saved
class Solution {
    public int minVisitCost(int[][] cost, int[][] rules) {
        // Write your code here.
    }
}
Checking account…