Coding

Campus Bikes II

Asked at

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

On a campus represented as a 2D grid, there are n workers and m bikes, with n <= m. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] Output: 6 Explanation: We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]] Output: 4 Explanation: We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Input : workers : [[0,0],[1,1],[2,2]] , bikes : [[0,0],[1,1],[2,2],[3,3]]

n == workers.length
m == bikes.length
1 <= n <= m <= 10
workers[i].length == 2
bikes[i].length == 2
0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
All the workers and the bikes locations are unique.

cpp

class Solution {
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        // Your code goes here
    }
};

java

class Solution {
    public int assignBikes(int[][] workers, int[][] bikes) {
        // Your code goes here
    }
}

python

class Solution(object):
    def assignBikes(self, workers, bikes):
        """
        :type workers: List[List[int]]
        :type bikes: List[List[int]]
        :rtype: int
        """
        # Your implementation here

javascript

/**
 * @param {number[][]} workers
 * @param {number[][]} bikes
 * @return {number}
 */
var assignBikes = function(workers, bikes) {
    return 0; // Your implementation here
};

csharp

public class Solution {
    public int AssignBikes(int[][] workers, int[][] bikes) {

    }
}

func assignBikes(workers [][]int, bikes [][]int) int {

}

Stuck? Show a way to structure it+

01Represent used bikes with a bitmask.
02Let worker index equal the number of set bits.
03Try every unused bike for that worker.
04Memoize the minimum remaining cost.

Reference answer

Because there are at most ten bikes, use a mask of assigned bikes. In state mask, worker popcount(mask) is next; try each unset bike, add Manhattan distance, and recurse. Memoizing by mask yields at most 2^m states and O(m * 2^m) transitions, with O(2^m) memory. Greedily assigning each worker its nearest bike can be globally suboptimal because it may steal the only good option for a later worker. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

How would you reconstruct the assignment?
Tests: choice tracking
When does the Hungarian algorithm become preferable?
Tests: scalability

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question