How should I practice Uber Circular Shuttle Optimization?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Uber online assessment problems in FastPrep.

Is Uber Circular Shuttle Optimization associated with Uber?

FastPrep tags this as a Uber online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Uber Circular Shuttle Optimization

Learn this problem

● Hard

UberOA

See Uber hiring insights

Problem statement

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

minimumShuttleCost(passengers: int[], edges: int[][]) → int

Complete the function minimumShuttleCost in the editor.

minimumShuttleCost has the following parameters:

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.
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

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.

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