Frontend School

Connecting Delivery Zones

DSA
easy

Connecting Delivery Zones

Easy
Union Find
Graph
Data Structures

Overview

Zomato operates a complex network of delivery zones. To optimize resource allocation and ensure timely deliveries, it's crucial to understand which zones are interconnected and can effectively share delivery riders. This problem asks you to determine if two specific delivery zones belong to the same interconnected network, given a list of direct connections.

What you need to do / Task

Implement a function canShareResources that takes the total number of delivery zones, a list of direct connections between zones, and a pair of zones to check. Your function should return true if the two specified zones are part of the same interconnected network (meaning resources can be shared between them), and false otherwise.

  • A connection [zoneA, zoneB] implies that zoneA and zoneB can share resources.
  • The relationship is transitive: if zoneA connects to zoneB, and zoneB connects to zoneC, then zoneA, zoneB, and zoneC can all share resources.
  • Zones are represented by 0-indexed integers from 0 to n-1.

Input & output

Input:

  • n: An integer representing the total number of delivery zones. Zones are numbered from 0 to n-1.
  • connections: An array of arrays, where each inner array [zoneA, zoneB] denotes a direct connection between zoneA and zoneB.
  • zone1: An integer representing the first zone to check.
  • zone2: An integer representing the second zone to check.

Output:

  • A boolean value: true if zone1 and zone2 can share resources, false otherwise.

Clarifications

  • A zone is always considered connected to itself.
  • Connections are undirected. If [A, B] is a connection, B is also connected to A.
  • The connections array may contain duplicate connections or connections where zoneA == zoneB. These should be handled gracefully (e.g., ignored or processed without error).
  • If zone1 and zone2 are the same zone, they are considered connected.

Examples

1

Example 1

Input:

n = 4, connections = [[0, 1], [2, 3]], zone1 = 0, zone2 = 1

Output:

true

Note:

Zones 0 and 1 are directly connected. Zones 2 and 3 are directly connected. 0 and 1 are in the same network.

2

Example 2

Input:

n = 4, connections = [[0, 1], [2, 3]], zone1 = 0, zone2 = 2

Output:

false

Note:

Zones 0 and 1 are connected, and zones 2 and 3 are connected. However, there is no path between zone 0 and zone 2. They belong to different networks.

3

Example 3

Input:

n = 5, connections = [[0, 1], [1, 2], [2, 0], [3, 4]], zone1 = 0, zone2 = 2

Output:

true

Note:

Zones 0, 1, and 2 are all interconnected through direct or indirect connections. Zone 0 and Zone 2 are in the same network.

Constraints

Constraints & assumptions

  • 1 <= n <= 10^4
  • 0 <= connections.length <= 10^5
  • 0 <= zoneA, zoneB < n for all [zoneA, zoneB] in connections
  • 0 <= zone1, zone2 < n
  • Time complexity: Aim for O(N + Mα(N)) where N is the number of zones, M is the number of connections, and α is the inverse Ackermann function (nearly constant).
  • Space complexity: Aim for O(N).

What interviewers evaluate

  • Correctness of implementation: Does the solution correctly identify interconnected zones?
  • Algorithm efficiency: Is the chosen approach optimal for the given constraints (e.g., Union-Find with path compression and union by rank/size)?
  • Code structure and readability: Is the code well-organized, clean, and easy to understand?
  • Edge case handling: Does the solution correctly handle cases like an empty connections list or zone1 == zone2?

Loading editor...