Katkat
Back

Find the Nearest Supply Location in a Road Network

LinkedInDevOps Engineer · Onsite
MediumDevOps EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model a road network as a graph and compute the shortest distance from a source node to any target node in a set using a Breadth-First Search (BFS) approach.

Problem Statement

You are given a road network represented as an undirected graph where nodes are intersections and edges are roads. Each road has an equal length (1 unit). You are provided with a starting intersection name, a list of intersection names that contain supply depots, and an adjacency list representing the connections.

Write a function find_nearest_supply(start_node, supply_nodes, adjacency_list) that returns the minimum number of roads (hops) required to travel from the start_node to the nearest supply_node. If no supply node is reachable or if the supply list is empty, return -1.

Constraints

  • The network can contain up to 100,000 intersections.
  • The graph may be disconnected.
  • adjacency_list is provided as a dictionary where keys are node names and values are lists of connected neighbors.

Examples

Example 1:

  • start_node: "A"
  • supply_nodes: ["D", "E"]
  • adjacency_list: {"A": ["B"], "B": ["C", "D"], "C": ["E"], "F": ["G"]}
  • Output: 2 (Path A -> B -> D)

Example 2:

  • start_node: "A"
  • supply_nodes: ["A"]
  • Output: 0 (Supply found at start)

Edge Cases

  • The start node is itself a supply location.
  • The graph is disconnected and the target is in a different component.
  • The supply list is empty.

Hints

Hint 1

Since the graph is unweighted, what algorithm is most efficient for finding the shortest path?

Hint 2

Instead of running a search from the start node to every supply node, consider initializing your BFS queue with all supply nodes or the start node to find the distance efficiently.

Hint 3

Using a set for `supply_nodes` will allow for O(1) lookups during your traversal.

Follow-up questions

  • How would your approach change if the roads had different weights (e.g., travel time)?
  • If the network is massive and cannot fit into memory, how would you store and query the graph?
  • How would you optimize the search if there are millions of nodes but you only need to check the nearest supply point daily?