Frontend School

Shortest Route to Charging Station

DSA
easy

Shortest Route to Charging Station

Easy
Graph
BFS
Shortest Path

Overview

Ola's electric vehicle (EV) fleet relies on efficient navigation to charging stations. Drivers often need to find the quickest route to recharge, especially when battery levels are low. This problem simulates a core part of our navigation system, focusing on finding the shortest path to any available charging station in a city, while accounting for temporary road closures.

What you need to do / Task

Implement a function findShortestChargingRoute that determines the minimum number of road segments a driver needs to traverse to reach any charging station from a given starting point. You must avoid any roads that are currently marked as blocked due to maintenance or events.

Input & output

Your function will receive the following parameters:

  • n: An integer representing the total number of intersections (nodes) in the city, indexed from 0 to n-1.
  • roads: An array of [u, v] pairs, where each pair denotes a bidirectional road connecting intersection u and intersection v.
  • startNode: An integer representing the driver's current intersection.
  • chargingStations: An array of integers, where each integer is the index of an intersection that hosts a charging station.
  • blockedRoads: An array of [u, v] pairs, where each pair denotes a bidirectional road that is currently unusable.

The function should return:

  • An integer representing the minimum number of road segments required to reach any charging station.
  • Return -1 if no charging station is reachable from the startNode without using blockedRoads.

Clarifications

  • All roads are bidirectional, meaning if there's a road [u, v], you can travel from u to v and from v to u.
  • A blockedRoad [u, v] means neither u -> v nor v -> u can be used.
  • If the startNode itself is a charging station, the distance is 0.
  • The 'shortest path' refers to the path with the minimum number of road segments.

Examples

1

Example 1

Input:

n = 5, roads = [[0,1],[0,2],[1,3],[2,4]], startNode = 0, chargingStations = [3,4], blockedRoads = []

Output:

2

Note:

From node 0, both paths to 3 (via 1) and 4 (via 2) take 2 road segments. The shortest is 2.

2

Example 2

Input:

n = 5, roads = [[0,1],[0,2],[1,3],[2,4]], startNode = 0, chargingStations = [3], blockedRoads = [[0,1]]

Output:

-1

Note:

Road (0,1) is blocked. There is no alternative path from node 0 to node 3. Node 4 is not a charging station in this case.

3

Example 3

Input:

n = 3, roads = [[0,1],[1,2]], startNode = 0, chargingStations = [0,2], blockedRoads = []

Output:

0

Note:

The driver is already at a charging station (node 0), so 0 segments are needed.

Constraints

Constraints & assumptions

  • 1 <= n <= 1000
  • 0 <= roads.length <= n * (n - 1) / 2
  • 0 <= startNode < n
  • 0 <= chargingStations.length <= n
  • 0 <= blockedRoads.length <= roads.length
  • All intersection indices (u, v, startNode, chargingStations elements) are between 0 and n-1 inclusive.
  • There are no self-loops (e.g., [0,0]) or multiple roads between the same two intersections in roads.
  • blockedRoads will only contain pairs that exist in roads.

Out of scope

  • Real-time traffic conditions or variable road weights.
  • Optimizing for fuel consumption or other factors beyond minimum segments.
  • Handling dynamic changes to blockedRoads during traversal.

What interviewers evaluate

  • Correct application of graph traversal algorithms (e.g., BFS) for shortest path in an unweighted graph.
  • Efficient handling of blockedRoads to prevent invalid path segments.
  • Thorough consideration of edge cases, such as the startNode being a charging station or no path existing.
  • Overall code structure, readability, and time/space complexity.

Loading editor...