How should I practice Global Charger Assignment?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Spotify onsite interview problems in FastPrep.

Is Global Charger Assignment associated with Spotify?

FastPrep tags this as a Spotify onsite interview coding practice problem when the problem catalog has that company and stage context.

Global Charger Assignment

Spotify● HardFULLTIMEONSITE INTERVIEW

Problem statement

Source note: The post says: "pair every vehicle with a unique charger so the total driving distance is minimized. If there are more vehicles than chargers, the assignment is impossible. Given a target vehicle index, return which charger that vehicle receives in the globally optimal assignment." The post gathers several reports.

The post disagrees with itself on the method. It twice describes dynamic programming over sorted indices, one preparation line mentions a heap of nearest pairs, and one note says some reports use greedy nearest-pair matching. Here, the goal is the smallest total distance, so dynamic programming is right and the heap can give a wrong answer. The post does not give the input layout, the result for an impossible case, or a rule for ties. Here, the line is a {0, 1, 2} array of at most 2000 cells, the target and the answer are array indices, an impossible case returns -1, and among tied assignments you list the chargers in vehicle order and take the smallest list.

The judged task matches the post at about 85%.

A line of cells is given as an array cells, where 0 is an empty cell, 1 is a vehicle and 2 is a charger. The distance between two cells is the difference of their indices.

Give every vehicle its own charger so that the total distance over all vehicles is as small as possible. No two vehicles share a charger, and a charger may stay unused. Vehicles and chargers do not block each other.

You are also given targetVehicle, the index of one vehicle. Return the index of the charger that this vehicle gets. If there are more vehicles than chargers, the assignment is impossible, so return -1.

Several assignments may tie for the smallest total. To pick one, write down each assignment's charger indices in the order of the vehicles from left to right, and use the assignment whose list is smallest, comparing the first entry that differs.

Function

assignedCharger(cells: int[], targetVehicle: int) → int

Examples

Example 1

cells = [0,1,0,2,1,0,0,0,2]targetVehicle = 4return = 8

The vehicles are at indices 1 and 4, and the chargers are at 3 and 8. Sending vehicle 1 to charger 3 and vehicle 4 to charger 8 costs 2 + 4 = 6. The other assignment costs 7 + 1 = 8. So vehicle 4 gets charger 8, even though charger 3 is closer to it.

Example 2

cells = [1,2,0,1,2]targetVehicle = 3return = 4

The vehicles are at 0 and 3, and the chargers are at 1 and 4. The best assignment costs 1 + 1 = 2, so vehicle 3 gets charger 4.

Example 3

cells = [1,1,2]targetVehicle = 0return = -1

There are two vehicles and one charger, so the answer is -1.

Example 4

cells = [2,1,2]targetVehicle = 1return = 0

Both chargers are at distance 1 from the vehicle. The tie rule picks the smaller list, so the answer is charger 0.

Constraints

1 <= cells.length <= 2000
0 <= cells[i] <= 2
0 <= targetVehicle < cells.length
cells[targetVehicle] == 1