Katkat
Back

Drone Circular Route — Minimum Total Travel Cost

AmazonSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to solve a variation of the Traveling Salesman Problem using bitmask dynamic programming to optimize route costs in a small, weighted graph.

Problem Description

You are tasked with designing a flight controller for a delivery drone that must visit a set of n charging stations, numbered 0 to n-1, exactly once before returning to the starting station (station 0). You are given an n x n matrix dist where dist[i][j] represents the cost to travel from station i to station j.

Since the drone consumes battery differently based on wind patterns and elevation, the cost dist[i][j] is not necessarily equal to dist[j][i]. Your goal is to find the minimum total travel cost to complete the circuit.

Implement the following function: int findMinRouteCost(int[][] dist)

Constraints

  • 2 <= n <= 15
  • 0 <= dist[i][j] 1 -> 3 -> 2 -> 0. Cost: 10 + 25 + 30 + 15 = 80.

Edge Cases

  • n=2: The route is simply 0 -> 1 -> 0.
  • Non-symmetrical graphs where dist[i][j] != dist[j][i].
  • The path must be a complete cycle starting and ending at 0.

Hints

Hint 1

Since the number of stations is small (up to 15), consider representing the set of visited stations using an integer bitmask.

Hint 2

Define a DP state as `dp[mask][last_node]`, representing the minimum cost to have visited the set of stations in `mask`, ending at `last_node`.

Hint 3

The transitions involve iterating through all possible unvisited next nodes and updating the DP table using the recurrence: `dp[mask | (1 << next)][next] = min(dp[mask | (1 << next)][next], dp[mask][curr] + dist[curr][next])`.

Follow-up questions

  • How would the time complexity change if you were required to visit only a subset of stations?
  • If `n` increased to 50, would this dynamic programming approach still be viable? If not, what heuristic strategies would you suggest?
  • How would you modify the algorithm if the drone had a limited battery capacity that restricts the total path cost?