Frontend School

Delivery Zone Hop Count

DSA
easy

Delivery Zone Hop Count

Easy
Graph
Breadth-First Search
Shortest Path

Overview

At Zomato, optimizing delivery routes is crucial for efficiency and customer satisfaction. Imagine a city mapped out into various "delivery zones," each representing a distinct area like a restaurant hub or a residential locality. Drivers navigate between these zones using direct road segments. To ensure quick deliveries, we need to determine the minimum number of road segments (hops) a driver must traverse to get from a starting delivery zone to a target delivery zone.

What you need to do / Task

Your task is to implement a function that calculates the minimum number of direct road segments (hops) required to travel from a given startZone to a targetZone within a city's delivery network.

Input & output

The function minDeliveryHops takes three arguments:

  • graph: A 2D array (adjacency list) representing the delivery network. graph[i] is an array of integers, where each integer j indicates that there's a direct road segment from zone i to zone j. The graph is unweighted and undirected (if i connects to j, j connects to i).
  • startZone: An integer representing the ID of the starting delivery zone.
  • targetZone: An integer representing the ID of the target delivery zone.

The function should return:

  • An integer representing the minimum number of hops required to reach targetZone from startZone.
  • Return -1 if the targetZone is unreachable from the startZone.

Clarifications

  • Zone IDs: Zone IDs are 0-indexed integers.
  • Self-loops: A zone may have a direct connection to itself, but this should not count as a "hop" if startZone == targetZone.
  • Start equals Target: If startZone is the same as targetZone, the number of hops is 0.
  • Graph Type: The graph is undirected. If graph[i] contains j, assume graph[j] contains i. However, the input graph will be provided such that both directions are explicitly listed (e.g., if i connects to j, then j connects to i in the input adjacency list).

Examples

1

Example 1

Input:

graph = [[1], [0, 2], [1, 3], [2]], startZone = 0, targetZone = 3

Output:

3

Note:

Path: 0 -> 1 -> 2 -> 3. This takes 3 hops.

2

Example 2

Input:

graph = [[1, 2], [0, 3], [0, 4], [1], [2]], startZone = 0, targetZone = 3

Output:

2

Note:

Path 1: 0 -> 1 -> 3 (2 hops). Path 2: 0 -> 2 -> 4 (2 hops, but not to target 3). The shortest path is 0 -> 1 -> 3, which is 2 hops.

3

Example 3

Input:

graph = [[1], [0], [3], [2]], startZone = 0, targetZone = 3

Output:

-1

Note:

Zone 0 is connected to zone 1. Zone 2 is connected to zone 3. There is no path between the component {0,1} and {2,3}. Therefore, target zone 3 is unreachable from start zone 0.

4

Example 4

Input:

graph = [[1], [0, 2], [1]], startZone = 1, targetZone = 1

Output:

0

Note:

The start zone is already the target zone, so 0 hops are needed.

Constraints

Constraints & assumptions

  • 1 <= N <= 100 (Number of delivery zones/nodes)
  • 0 <= M <= N * (N - 1) / 2 (Number of road segments/edges)
  • 0 <= startZone, targetZone < N
  • Each element in graph[i] will be a valid zone ID (0 to N-1).
  • The graph is unweighted.
  • The input graph will always be a valid adjacency list representation where graph[i] lists neighbors of i.

Out of scope

  • Weighted edges (e.g., varying road segment lengths or traffic).
  • Complex routing algorithms considering real-time traffic or multiple delivery agents.

What interviewers evaluate

  • Correctness: The solution must accurately return the minimum number of hops, including handling unreachable targets and self-loops.
  • Algorithm Choice: Demonstrate understanding of appropriate graph traversal algorithms for unweighted shortest paths.
  • Edge Cases: Ability to handle startZone == targetZone and disconnected components.
  • Efficiency: Implement an algorithm with optimal time and space complexity for the given constraints.

Loading editor...