How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Drone Circular Route — Minimum Total Travel Cost

Quick Overview

This question tests a candidate's ability to apply dynamic programming to combinatorial optimization, specifically the Traveling Salesman Problem (TSP) with bitmask DP. It evaluates practical algorithm design for asymmetric weighted graphs with up to 15 nodes, a classic pattern in software engineering interviews assessing graph traversal and optimization under exponential state spaces.

Drone Circular Route — Minimum Total Travel Cost

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

# Drone Circular Route — Minimum Cost Tour A delivery drone must visit every hub in a network exactly once and then return to its starting hub, forming a **closed loop**. The drone may visit the hubs in any order. Travel between hubs is asymmetric: the cost to fly from hub $i$ to hub $j$ may differ from the cost to fly from hub $j$ to hub $i$. You are given: - `n`: the number of hubs, numbered `0` through `n - 1`. - `cost`: an `n × n` integer matrix where `cost[i][j]` is the fuel cost to fly **directly** from hub `i` to hub `j`. The diagonal is zero (`cost[i][i] == 0`). Return the **minimum total fuel cost** to complete a circular tour that starts at hub `0`, visits every other hub exactly once, and returns to hub `0`. ## Example 1 ``` Input: n = 3 cost = [[0, 10, 15], [20, 0, 35], [25, 30, 0]] Output: 65 ``` Visiting in order 0 → 1 → 2 → 0 costs 10 + 35 + 25 = 70. Visiting in order 0 → 2 → 1 → 0 costs 15 + 30 + 20 = 65. The minimum is **65**. ## Example 2 ``` Input: n = 4 cost = [[ 0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]] Output: 80 ``` ## Constraints - $1 \le n \le 15$ - $0 \le \texttt{cost}[i][j] \le 10^4$ - $\texttt{cost}[i][i] = 0$ for all $i$ - The answer fits in a 32-bit signed integer.

Quick Answer: This question tests a candidate's ability to apply dynamic programming to combinatorial optimization, specifically the Traveling Salesman Problem (TSP) with bitmask DP. It evaluates practical algorithm design for asymmetric weighted graphs with up to 15 nodes, a classic pattern in software engineering interviews assessing graph traversal and optimization under exponential state spaces.

A delivery drone must visit every hub in a network exactly once and then return to its starting hub, forming a closed loop. The drone may visit the hubs in any order. Travel is asymmetric: the cost to fly from hub i to hub j may differ from the cost to fly from hub j to hub i. You are given: - `n`: the number of hubs, numbered `0` through `n - 1`. - `cost`: an `n x n` integer matrix where `cost[i][j]` is the fuel cost to fly directly from hub `i` to hub `j`. The diagonal is zero (`cost[i][i] == 0`). Return the minimum total fuel cost to complete a circular tour that starts at hub `0`, visits every other hub exactly once, and returns to hub `0`. This is the asymmetric Traveling Salesman Problem (ATSP). The key trap (called out in the original interview report) is the closing leg: after visiting the last hub you must add the cost of flying back to hub 0 — that final return edge is easy to forget. Example 1: n = 3 cost = [[0, 10, 15], [20, 0, 35], [25, 30, 0]] Output: 65 Tour 0 -> 2 -> 1 -> 0 costs 15 + 30 + 20 = 65 (better than 0 -> 1 -> 2 -> 0 = 70). Example 2: n = 4 cost = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]] Output: 80

Constraints

1 <= n <= 15
0 <= cost[i][j] <= 10^4
cost[i][i] == 0 for all i
The cost matrix may be asymmetric: cost[i][j] need not equal cost[j][i]
The answer fits in a 32-bit signed integer

Examples

Input: (3, [[0, 10, 15], [20, 0, 35], [25, 30, 0]])

Expected Output: 65

Explanation: Tour 0 -> 2 -> 1 -> 0 = 15 + 30 + 20 = 65, beating 0 -> 1 -> 2 -> 0 = 70.

Input: (4, [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])

Expected Output: 80

Explanation: Example 2 from the prompt; the optimal symmetric-ish tour costs 80.

Input: (1, [[0]])

Expected Output: 0

Explanation: Single hub: the drone is already home, so the cost is 0.

Input: (2, [[0, 5], [8, 0]])

Expected Output: 13

Explanation: Only one tour: 0 -> 1 -> 0 = 5 + 8 = 13. The asymmetry (5 out, 8 back) both edges count.

Input: (4, [[0, 3, 1, 5], [2, 0, 7, 4], [6, 8, 0, 9], [3, 2, 6, 0]])

Expected Output: 14

Explanation: Best asymmetric tour is 0 -> 2 -> 3 -> 1 -> 0 = 1 + 9 + 2 + 2 = 14.

Input: (3, [[0, 100, 1], [1, 0, 100], [100, 1, 0]])

Expected Output: 3

Explanation: Direction matters: 0 -> 2 -> 1 -> 0 = 1 + 1 + 1 = 3, while the reverse 0 -> 1 -> 2 -> 0 = 300. This is the wrap-around / asymmetry trap.

Hints

n <= 15 is the giveaway: 2^15 subsets is small enough for an exponential-in-n bitmask DP (Held-Karp), but n! brute force over permutations blows up.
Let dp[mask][i] be the minimum cost of a path that starts at hub 0, visits exactly the hubs in `mask`, and currently sits at hub i. Initialize dp[{0}][0] = 0.
Because the costs are asymmetric, you must respect direction: a transition into hub j adds cost[i][j], not cost[j][i].
Don't forget the closing leg. The answer is min over i of dp[fullMask][i] + cost[i][0] — the original interview report specifically warns that the tail-to-head return edge is the easy thing to miss.
Handle the degenerate n == 1 case (a single hub) separately: the cost is 0.

Last updated: Jun 24, 2026

Loading coding console...

Quick Overview

Drone Circular Route — Minimum Total Travel Cost

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Constraints

1 <= n <= 15
0 <= cost[i][j] <= 10^4
cost[i][i] == 0 for all i
The cost matrix may be asymmetric: cost[i][j] need not equal cost[j][i]
The answer fits in a 32-bit signed integer

Examples

Input: (3, [[0, 10, 15], [20, 0, 35], [25, 30, 0]])

Expected Output: 65

Explanation: Tour 0 -> 2 -> 1 -> 0 = 15 + 30 + 20 = 65, beating 0 -> 1 -> 2 -> 0 = 70.

Input: (4, [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]])

Expected Output: 80

Explanation: Example 2 from the prompt; the optimal symmetric-ish tour costs 80.

Input: (1, [[0]])

Expected Output: 0

Explanation: Single hub: the drone is already home, so the cost is 0.

Input: (2, [[0, 5], [8, 0]])

Expected Output: 13

Explanation: Only one tour: 0 -> 1 -> 0 = 5 + 8 = 13. The asymmetry (5 out, 8 back) both edges count.

Input: (4, [[0, 3, 1, 5], [2, 0, 7, 4], [6, 8, 0, 9], [3, 2, 6, 0]])

Expected Output: 14

Explanation: Best asymmetric tour is 0 -> 2 -> 3 -> 1 -> 0 = 1 + 9 + 2 + 2 = 14.

Input: (3, [[0, 100, 1], [1, 0, 100], [100, 1, 0]])

Expected Output: 3

Explanation: Direction matters: 0 -> 2 -> 1 -> 0 = 1 + 1 + 1 = 3, while the reverse 0 -> 1 -> 2 -> 0 = 300. This is the wrap-around / asymmetry trap.

Hints

n <= 15 is the giveaway: 2^15 subsets is small enough for an exponential-in-n bitmask DP (Held-Karp), but n! brute force over permutations blows up.
Let dp[mask][i] be the minimum cost of a path that starts at hub 0, visits exactly the hubs in `mask`, and currently sits at hub i. Initialize dp[{0}][0] = 0.
Because the costs are asymmetric, you must respect direction: a transition into hub j adds cost[i][j], not cost[j][i].
Don't forget the closing leg. The answer is min over i of dp[fullMask][i] + cost[i][0] — the original interview report specifically warns that the tail-to-head return edge is the easy thing to miss.
Handle the degenerate n == 1 case (a single hub) separately: the cost is 0.

Last updated: Jun 24, 2026

Loading coding console...