Frontend School

Prerequisite-Aware Delivery Route

DSA
hard

Prerequisite-Aware Delivery Route

Hard
Graph
Dijkstra
BFS
Bitmasking
Shortest Path

Overview

Flipkart's logistics network is vast and complex, often involving critical delivery hubs that handle specialized items or require specific routing procedures. Optimizing routes to minimize delivery time is crucial for efficiency and customer satisfaction. This problem challenges you to find the shortest possible route through a delivery network, ensuring all designated critical hubs are visited while respecting specific visit order prerequisites.

What you need to do / Task

Implement the function findMinPrerequisiteAwareRoute that calculates the minimum total distance to travel from a startNode to an endNode in a given directed, weighted graph. The path must satisfy the following conditions:

  1. All specified criticalHubs must be visited at least once along the route.
  2. For any prerequisite pair [idxA, idxB], criticalHubs[idxA] must be visited before criticalHubs[idxB] on the path.

Your solution should return the minimum total distance. If no such valid path exists, return -1.

Input & output

Function Signature: function findMinPrerequisiteAwareRoute(n: number, edges: number[][], startNode: number, endNode: number, criticalHubs: number[], prerequisites: number[][]): number

Parameters:

  • n: An integer representing the number of nodes in the graph, labeled from 0 to n-1.
  • edges: An array of arrays, where each inner array [u, v, weight] represents a directed edge from node u to node v with a non-negative weight (distance).
  • startNode: The starting node for the route.
  • endNode: The final destination node for the route.
  • criticalHubs: An array of unique node IDs that must be visited. These nodes are part of the graph (0 to n-1). The order of nodes in this array defines their indices for prerequisites (e.g., criticalHubs[0] is the first critical hub).
  • prerequisites: An array of arrays, where each inner array [idxA, idxB] means that criticalHubs[idxA] must be visited before criticalHubs[idxB]. idxA and idxB are valid indices into the criticalHubs array.

Return Value:

  • An integer representing the minimum total distance of a valid route, or -1 if no such route exists.

Clarifications

  • Empty criticalHubs: If criticalHubs is empty, the task simplifies to finding the shortest path from startNode to endNode without any additional requirements.
  • startNode or endNode as criticalHubs: If startNode or endNode are among the criticalHubs, they are considered 'visited' at the very beginning or end of the path respectively, and their prerequisite constraints must still be met.
  • Cyclic Prerequisites: You can assume that the prerequisites do not form a cycle (e.g., A before B, B before C, C before A).
  • Duplicate Edges/Self-loops: Assume no duplicate edges between the same pair of nodes and no self-loops (u == v for an edge [u, v, weight]).

Examples

1

Example 1

Input:

n = 3, edges = [[0,1,10],[1,2,10],[0,2,25]], startNode = 0, endNode = 2, criticalHubs = [1], prerequisites = []

Output:

20

Note:

The shortest path from 0 to 2 that visits node 1 is 0 -> 1 (cost 10) -> 2 (cost 10), total 20. The direct path 0 -> 2 (cost 25) is longer.

2

Example 2

Input:

n = 4, edges = [[0,1,10],[1,2,10],[2,3,10],[0,3,100],[0,2,25],[1,3,20]], startNode = 0, endNode = 3, criticalHubs = [1, 2], prerequisites = [[0, 1]]

Output:

30

Note:

Critical hubs: criticalHubs[0] = node 1, criticalHubs[1] = node 2. Prerequisite: node 1 must be visited before node 2. Path 0 -> 1 (cost 10, visits criticalHubs[0]). Current mask indicates criticalHubs[0] visited. Then 1 -> 2 (cost 10, visits criticalHubs[1]). Prerequisite for criticalHubs[1] (criticalHubs[0]) is met. Current mask indicates both visited. Then 2 -> 3 (cost 10). Total cost: 10 + 10 + 10 = 30. Attempting 0 -> 2 (cost 25) directly would visit criticalHubs[1] before criticalHubs[0], violating the prerequisite, hence this path is invalid.

3

Example 3

Input:

n = 3, edges = [[0,1,10],[1,2,10]], startNode = 0, endNode = 2, criticalHubs = [0, 1], prerequisites = [[1, 0]]

Output:

-1

Note:

Critical hubs: criticalHubs[0] = node 0, criticalHubs[1] = node 1. Prerequisite: node 1 must be visited before node 0. Starting at node 0 means criticalHubs[0] is considered visited. However, the prerequisite states that criticalHubs[1] must be visited before criticalHubs[0]. This creates an immediate violation at the start, as criticalHubs[0] is 'visited' first by being the start node, but its prerequisite (criticalHubs[1]) has not been met yet. Thus, no valid path exists.

Constraints

Constraints & assumptions

  • 1 <= n <= 50
  • 0 <= edges.length <= n * (n - 1)
  • 0 <= u, v < n for all edges
  • 1 <= weight <= 1000 for all edges
  • 0 <= startNode, endNode < n
  • 0 <= criticalHubs.length <= 10 (This constraint is crucial for performance)
  • All nodes in criticalHubs are unique and within 0 to n-1.
  • 0 <= prerequisites.length <= criticalHubs.length * (criticalHubs.length - 1) / 2
  • 0 <= idxA, idxB < criticalHubs.length for all prerequisites.
  • idxA != idxB for all prerequisites.
  • Edge weights are non-negative.

What interviewers evaluate

  • Correctness and Completeness: Does the solution correctly identify the shortest path while strictly adhering to all critical hub visits and prerequisite constraints across various scenarios?
  • Algorithmic Efficiency: Is the chosen algorithm optimal for the given constraints? (e.g., Dijkstra's on a state-space graph, proper complexity analysis).
  • State Management: Effective use of data structures (e.g., bitmasking) to represent and manage the 'visited critical hubs' state.
  • Edge Case Handling: Robustness in handling scenarios like unreachable nodes, empty critical hubs, or cases where no valid path exists.
  • Code Quality: Readability, modularity, and clarity of the implementation.

Loading editor...