Skip to main content

Uber

Uber OA-14 2023

Problem Description

Uber has recently introduced the Share Cab Service, which starts at a point and returns to the same point after picking up all passengers from different pickup points. There are n pick-up points in total, labeled from 0 to (n-1). All pick-up points are connected by roads with the same cost of 1 unit. The connected roads are defined by edges of length (n-1), where edges[i] = [a_i, b_i] indicates that there is a road of cost 1 between pick-up points (a_i) and (b_i). This forms a graph of pick-up points connected by roads.

Additionally, you are given an array passengers of size n, where passengers[i] can be either 0 or 1. A value of 1 indicates the presence of a passenger at pick-up point i.

The cab can perform the following two operations any number of times:

  1. Collect Passengers: Collect all the passengers that are at a distance of at most 2 roads from the current pick-up point. This operation costs 0 units.
  2. Move to Adjacent Pick-up Point: Move to an adjacent pick-up point in the graph. This operation costs 1 unit since all roads have the same cost of 1 unit.

The cab starts at any pick-up point, collects all passengers, and must return to the starting point. Your task is to find the minimum cost that Uber needs to go through to collect all the passengers and return back to the starting point.

Input Format:

  • An array passengers of size n, where passengers[i] is either 0 or 1, indicating the presence of a passenger at pick-up point i.
  • A 2D array edges, where each element edges[i] = [a_i, b_i] represents a road of cost 1 between pick-up points (a_i) and (b_i).

Output Format:

  • An integer representing the minimum cost Uber needs to collect all the passengers and return to the starting point.

Constraints:

  • 1 <= n <= 10^4
  • The input forms a valid tree (there are no cycles, and all nodes are connected).
  • If a road is traversed twice, it incurs a cost of 2 units.

Sample Testcase 1:

Input:

passengers = [1, 0, 0, 0, 0, 1]
edges = [[0,1], [1,2], [2,3], [3,4], [4,5]]

Output:

2

Explanation:

  • The cab starts at pick-up point 0, collects the passenger at point 0, and moves through the tree. After collecting all passengers, it returns back to the starting point. The minimal traversal required has a total cost of 4 units.