FastPrep
Problem · Tree

Uber Circular Shuttle Optimization

● HardUberOA
See Uber hiring insights

Uber has launched a new circular shuttle service that operates on a fixed route, starting and ending at the same location while collecting passengers from various designated stops.

The service area consists of n pickup locations, numbered from 0 to n-1. These locations are interconnected by roads, each with a uniform travel cost of 1 unit. The road network is defined by n-1 edges, where each edge [ai, bi] represents a bidirectional road connecting locations ai and bi. This configuration forms a connected tree structure of pickup locations.

Passenger demand is represented by an array of size n, where passengers[i] equals 1 if there's a passenger waiting at location i, and 0 otherwise.

The shuttle service operates as follows: The shuttle may begin its route at any pickup location. Two operations are available at each stop:

  • Passenger Collection (Cost: 0): Collect all passengers within a radius of 2 roads from the current location. The radius represents the maximum number of road segments the shuttle can reach to pick up passengers without additional cost.
  • Movement (Cost: 1): Travel to any directly connected pickup point, incurring a cost of 1 unit per road segment.

    • Objective: Determine the minimum total cost required to collect all waiting passengers and return the shuttle to its starting location.

    Important Constraints:

  • Each time a road segment is traversed, it contributes 1 unit to the total cost (meaning a round trip on the same road costs 2 units).
  • The pickup locations form a valid tree structure (connected and acyclic).

    • Goal: Find the optimal starting location and route strategy that minimizes the total operational cost.

    Note: If you pass a road 2 times, the cost to traverse that road becomes 2.

    Function Description

    Complete the function minimumShuttleCost in the editor.

    minimumShuttleCost has the following parameters:

    1. int[] passengers: A 1D array of integers where passengers[i] = 1 indicates a passenger at pickup point i, and passengers[i] = 0 indicates no passenger.
    2. int[][] edges: A 2D array of integers where edges[i] = [ai, bi] indicates a bidirectional road connecting ai and bi.

    Returns

    int: Minimum cost incurred to start at a pickup point and return to the same starting point after collecting all the passengers from the pickup points.

    Examples
    01 · Example 1
    passengers = [1, 0, 0, 0, 0, 1]
edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
return = 2
    The Uber shuttle can follow the below steps to reduce the cost to 2 and collect all 2 passengers: Start at pick-up point 2 Collect the passenger from pick-up point 0 Move to adjacent pick-up point 3 Collect the passenger from pick-up point 5 Move back to adjacent pick-up point 2 Cost is incurred only during movement from pick-up points 2 to 3 and 3 to 2. Total cost = 2.
    02 · Example 2
    passengers = [0, 0, 0, 1, 1, 0, 0, 1]
edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
return = 2
    The Uber shuttle can follow the below steps to reduce the cost to 2 and collect all 3 passengers: Start at pick-up point 0 Collect the passengers from pick-up points 3 and 4 Move to adjacent pick-up point 2 Collect the passenger from pick-up point 7 Move back to adjacent pick-up point 0 Cost is incurred only during movement from pick-up points 0 to 2 and 2 to 0. Total cost = 2.
    Constraints
    • 1 ≤ n ≤ 3·10^4
    • passengers.size() equals n.
    • 0 ≤ passengers[i] ≤ 1
    • edges.length equals n-1.
    • edges[i].length equals 2.
    • 0 ≤ ai, bi < n
    • ai ≠ bi
    More Uber problems
    drafts saved locally
    public int minimumShuttleCost(int[] passengers, int[][] edges) {
  // write your code here
}
    passengers[1, 0, 0, 0, 0, 1]
    edges[[0,1],[1,2],[2,3],[3,4],[4,5]]
    expected2
    sign in to submit