Frontend School

Myntra Delivery: Optimal Route with Fuel Constraints

DSA
medium

Myntra Delivery: Optimal Route with Fuel Constraints

Medium
Graph
Shortest Path
Dijkstra

Overview

Myntra relies on an efficient delivery network to get products to customers. Delivery agents navigate a complex city grid, where each road has a specific distance and consumes a certain amount of fuel. Optimizing routes is crucial for timely deliveries and cost efficiency. This problem challenges you to find the most optimal delivery path under realistic fuel constraints.

What you need to do / Task

Your task is to implement a function that determines the shortest possible total distance for a delivery vehicle to travel from a startNode to an endNode. The vehicle begins with a fixed initialFuel capacity. It cannot traverse a road if its current fuel level is less than the fuelCost of that road. The goal is to minimize the total distance traveled while ensuring the vehicle never runs out of fuel mid-journey.

Input & output

Function Signature:

function findOptimalRoute(n: number, edges: number[][], startNode: number, endNode: number, initialFuel: number): number

Parameters:

  • n: An integer representing the number of intersections in the city, labeled from 0 to n-1.
  • edges: A 2D array of integers, where each edge[i] is [u, v, distance, fuelCost]. This indicates a bidirectional road between intersection u and intersection v with a given distance and fuelCost.
  • startNode: An integer representing the starting intersection for the delivery.
  • endNode: An integer representing the destination intersection for the delivery.
  • initialFuel: An integer representing the total amount of fuel the vehicle starts with.

Return Value:

  • An integer representing the minimum total distance to reach endNode from startNode while respecting fuel constraints. If endNode is unreachable, return -1.

Clarifications

  • Intersections are 0-indexed.
  • Roads are bidirectional, meaning if there's an edge [u, v, distance, fuelCost], you can travel from u to v or v to u with the same distance and fuelCost.
  • The initialFuel represents the maximum fuel capacity. You cannot exceed this capacity, and you cannot traverse an edge if the current fuel in your tank is less than the fuelCost of that edge.
  • There are no fuel stations; the vehicle must complete the journey with its initialFuel capacity.

Examples

1

Example 1

Input:

n = 3, edges = [[0,1,10,1],[1,2,10,1]], startNode = 0, endNode = 2, initialFuel = 5

Output:

20

Note:

Path 0 -> 1 -> 2: Total distance = 10 + 10 = 20. Total fuel consumed = 1 + 1 = 2. Since initialFuel (5) is sufficient (5 >= 2), this path is valid and optimal.

2

Example 2

Input:

n = 3, edges = [[0,1,10,1],[1,2,10,1],[0,2,30,5]], startNode = 0, endNode = 2, initialFuel = 1

Output:

-1

Note:

Path 0 -> 1 -> 2: Requires 2 fuel (1 for 0-1, 1 for 1-2). Initial fuel is 1, so 1-2 leg is impossible. Path 0 -> 2: Requires 5 fuel. Initial fuel is 1, so this path is impossible. No valid path exists.

3

Example 3

Input:

n = 4, edges = [[0,1,10,1],[1,2,10,1],[0,3,5,1],[3,2,5,3]], startNode = 0, endNode = 2, initialFuel = 3

Output:

20

Note:

Path 0 -> 1 -> 2: Distance = 10 + 10 = 20. Fuel consumed = 1 + 1 = 2. Remaining fuel after 0->1 is 2. Remaining fuel after 1->2 is 1. This path is valid. Path 0 -> 3 -> 2: Distance = 5 + 5 = 10. Fuel consumed = 1 + 3 = 4. After 0->3, 2 fuel remains. For 3->2, 3 fuel is needed, but only 2 is available. This path is invalid due to insufficient fuel for the 3->2 leg. Therefore, the only valid path is 0 -> 1 -> 2, with a distance of 20.

Constraints

Constraints & assumptions

  • 2 <= n <= 100
  • 0 <= edges.length <= n * (n - 1) / 2 (maximum number of unique bidirectional edges)
  • 0 <= u, v < n, u != v for any edge.
  • 1 <= distance <= 1000 for any edge.
  • 1 <= fuelCost <= 100 for any edge.
  • 0 <= startNode, endNode < n
  • 0 <= initialFuel <= 500
  • There are no self-loops (an edge from a node to itself).
  • There are no duplicate edges between the same two nodes.

What interviewers evaluate

  • Algorithm Selection: Correctly identifying and adapting a suitable graph traversal algorithm (e.g., Dijkstra's).
  • State Management: Effectively incorporating the fuel constraint into the algorithm's state representation.
  • Correctness: Handling all edge cases, including unreachable destinations and paths where fuel becomes a limiting factor.
  • Efficiency: Achieving optimal time and space complexity for the given constraints.
  • Code Quality: Writing clean, readable, and well-structured code with appropriate data structures.

Loading editor...