Jobs

Interviews

Discussions

Campus Bikes

Medium

Asked by:

5 views

Topics:

ArraysGreedy Algorithms

On a campus represented as a 2D grid, there are n workers and m bikes, with n <= m. You are given a list of the workers' locations: workers[i] = (xi, yi) and a list of bike locations: bikes[j] = (xj, yj). All the workers and bikes are distinct.

Assign a bike to each worker such that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points (a, b) and (c, d) is |a - c| + |b - d|.

Return an array result of size n, where result[i] is the index of the bike assigned to the i^th worker.

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]
Explanation: 
The bike at [1,2] is assigned to the worker at [0,0]; the bike at [3,3] is assigned to the worker at [2,1].

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: [0,2,1]

Constraints:

n == workers.length
m == bikes.length
1 <= n <= m <= 1000
workers[i].length == bikes[j].length == 2
0 <= xi, yi < 1000
All the workers and bikes are distinct.

Try coding it in LeetCode

Campus Bikes

Medium

Asked by:

5 views

Topics:

ArraysGreedy Algorithms

Assign a bike to each worker such that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points (a, b) and (c, d) is |a - c| + |b - d|.

Return an array result of size n, where result[i] is the index of the bike assigned to the i^th worker.

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]
Explanation: 
The bike at [1,2] is assigned to the worker at [0,0]; the bike at [3,3] is assigned to the worker at [2,1].

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: [0,2,1]

Constraints:

n == workers.length
m == bikes.length
1 <= n <= m <= 1000
workers[i].length == bikes[j].length == 2
0 <= xi, yi < 1000
All the workers and bikes are distinct.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of workers and bikes, specifically the maximum number of each?
What is the expected behavior if two or more worker-bike pairs have the same distance? Should I prioritize based on worker index, bike index, or is any ordering acceptable?
Are the coordinates guaranteed to be integers, or should I expect floating-point numbers?
Is it possible for a worker or bike location to coincide (have the exact same coordinates)? If so, how should that be handled?
Is it guaranteed that there will always be at least as many bikes as workers, or could there be more workers than bikes (or vice-versa)?

Brute Force Solution

Approach

We want to assign bikes to workers so that the total distance between workers and their assigned bikes is as small as possible. The brute force approach considers every single possible assignment of bikes to workers, calculating the total distance for each.

Here's how the algorithm would work step-by-step:

First, list all the possible pairings of workers to bikes. Think of it like trying every possible seating arrangement.
For each possible arrangement, calculate the total distance. This means adding up the distance between each worker and the bike they've been assigned in that particular arrangement.
After calculating the total distance for every possible worker-bike arrangement, compare all the total distances.
Finally, pick the arrangement that has the smallest total distance. This is our best (optimal) solution because it minimizes the total walking distance for everyone.

Code Implementation

import itertools

def campus_bikes_brute_force(
    workers_positions, bikes_positions
):
    number_of_workers = len(workers_positions)
    number_of_bikes = len(bikes_positions)

    # Ensure there are at least as many bikes as workers
    if number_of_bikes < number_of_workers:
        return -1

    minimum_total_distance = float('inf')

    # Generate all possible bike assignments to workers.
    for bike_assignment in itertools.permutations(
        range(number_of_bikes), number_of_workers
    ):
        current_total_distance = 0

        # Calculate the total distance for the current assignment.
        for worker_index in range(number_of_workers):
            bike_index = bike_assignment[worker_index]

            worker_x, worker_y = workers_positions[worker_index]
            bike_x, bike_y = bikes_positions[bike_index]

            current_distance = abs(worker_x - bike_x) + abs(
                worker_y - bike_y
            )
            current_total_distance += current_distance

        # Update minimum total distance if necessary.
        minimum_total_distance = min(
            minimum_total_distance, current_total_distance
        )

    return minimum_total_distance

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores all possible pairings of workers to bikes. If we have 'n' workers and 'n' bikes, the number of possible assignments is n! (n factorial). For each of these n! permutations, we calculate the total distance, which takes O(n) time. Therefore, the overall time complexity is O(n * n!). Because n! grows much faster than n, the dominant term is n!, and the time complexity is effectively O(n!).

Space Complexity

O(W! * W) – The brute force approach explores all possible assignments of workers to bikes. This involves generating all permutations of bike assignments to workers. There are W! possible permutations, where W is the number of workers. Each permutation, representing an assignment, requires storing an array or list of length W, mapping each worker to a specific bike. Therefore, the space complexity is dominated by storing all permutations and each individual permutation itself, resulting in O(W! * W) auxiliary space.

Optimal Solution

Approach

The best way to assign bikes to workers is to consider the distances between each worker and each bike. We want to prioritize assigning bikes that are closer to workers and avoid assigning the same bike or worker multiple times. It is more efficient than trying all combinations.

Here's how the algorithm would work step-by-step:

Calculate the distance between each worker and each bike.
Organize these distances from shortest to longest, keeping track of which worker and bike each distance refers to.
Go through the distances in order from shortest to longest.
For each distance, check if the worker and bike involved have already been assigned.
If neither the worker nor the bike has been assigned yet, assign that bike to the worker.
Mark both the worker and the bike as assigned so they aren't considered again.
Continue until all workers have been assigned a bike.

Code Implementation

def assign_bikes(workers, bikes):
    distances = []
    number_of_workers = len(workers)
    number_of_bikes = len(bikes)

    for worker_index in range(number_of_workers):
        for bike_index in range(number_of_bikes):
            worker_x, worker_y = workers[worker_index]
            bike_x, bike_y = bikes[bike_index]
            distance = abs(worker_x - bike_x) + abs(worker_y - bike_y)
            distances.append((distance, worker_index, bike_index))

    distances.sort()

    assigned_bikes = [None] * number_of_workers
    worker_assigned = [False] * number_of_workers
    bike_assigned = [False] * number_of_bikes

    bikes_assigned_count = 0

    for distance, worker_index, bike_index in distances:
        # Only proceed if both worker and bike are unassigned
        if not worker_assigned[worker_index] and not bike_assigned[bike_index]:

            assigned_bikes[worker_index] = bike_index
            worker_assigned[worker_index] = True
            bike_assigned[bike_index] = True
            bikes_assigned_count += 1

            # Exit once all workers are assigned
            if bikes_assigned_count == number_of_workers:
                break

    return assigned_bikes

Big(O) Analysis

Time Complexity

O(m * n * log(m * n)) – Let n be the number of workers and m be the number of bikes. Calculating the distance between each worker and each bike takes O(m * n) time. Sorting these distances, which is the dominant factor, takes O(m * n * log(m * n)) time. The subsequent loop iterates through the sorted distances, and each check (whether worker or bike has been assigned) is O(1), thus the total time complexity is dominated by the sorting step. Therefore, the overall time complexity is O(m * n * log(m * n)).

Space Complexity

O(W * B) – The dominant space usage comes from storing the distances between each worker and each bike, which are then sorted. We have to store all of the distances in memory to be able to sort them, even temporarily. Where W is the number of workers and B is the number of bikes, this requires storing W * B distances. The 'assigned' markers for workers and bikes contribute negligibly to space complexity in comparison.

Edge Cases

Case	How to Handle
Empty worker or bike array	Return an empty list or an error, as no assignments can be made without workers or bikes.
Workers and bikes have identical positions.	The distance calculation will result in zero, which should be handled correctly by the sorting or priority queue mechanism.
Maximum number of workers and bikes close to constraint limits (e.g., 1000 workers and 1000 bikes).	Ensure the solution scales efficiently, especially the distance calculation and assignment steps, avoiding excessive computation.
Integer overflow in distance calculation due to large coordinate values.	Use appropriate data types (e.g., long) to prevent integer overflow when calculating Manhattan distance.
Cases where the workers and bikes are far apart and results in very large distances.	The solution should still perform correctly, handling potentially large integer values appropriately and preventing performance degradation due to unnecessary calculations.
Number of workers and bikes are significantly different (e.g., many more workers than bikes or vice versa).	The algorithm should efficiently handle such unbalanced scenarios, prioritizing the closest assignments and ensuring all workers/bikes are considered if possible.
Coordinates are negative.	Manhattan distance calculation will handle negative coordinates correctly.
Duplicate worker or bike locations.	The assignment logic should not get stuck trying to reassign the same location and should correctly assign the closest available bike to each worker.

Empty worker or bike array

How to Handle:

Return an empty list or an error, as no assignments can be made without workers or bikes.

Workers and bikes have identical positions.

How to Handle:

The distance calculation will result in zero, which should be handled correctly by the sorting or priority queue mechanism.

Maximum number of workers and bikes close to constraint limits (e.g., 1000 workers and 1000 bikes).

How to Handle:

Ensure the solution scales efficiently, especially the distance calculation and assignment steps, avoiding excessive computation.

Integer overflow in distance calculation due to large coordinate values.

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow when calculating Manhattan distance.

Cases where the workers and bikes are far apart and results in very large distances.

How to Handle:

The solution should still perform correctly, handling potentially large integer values appropriately and preventing performance degradation due to unnecessary calculations.

Number of workers and bikes are significantly different (e.g., many more workers than bikes or vice versa).

How to Handle:

The algorithm should efficiently handle such unbalanced scenarios, prioritizing the closest assignments and ensuring all workers/bikes are considered if possible.

Coordinates are negative.

How to Handle:

Manhattan distance calculation will handle negative coordinates correctly.

Duplicate worker or bike locations.

How to Handle:

The assignment logic should not get stuck trying to reassign the same location and should correctly assign the closest available bike to each worker.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of workers and bikes, specifically the maximum number of each?
What is the expected behavior if two or more worker-bike pairs have the same distance? Should I prioritize based on worker index, bike index, or is any ordering acceptable?
Are the coordinates guaranteed to be integers, or should I expect floating-point numbers?
Is it possible for a worker or bike location to coincide (have the exact same coordinates)? If so, how should that be handled?
Is it guaranteed that there will always be at least as many bikes as workers, or could there be more workers than bikes (or vice-versa)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, list all the possible pairings of workers to bikes. Think of it like trying every possible seating arrangement.
For each possible arrangement, calculate the total distance. This means adding up the distance between each worker and the bike they've been assigned in that particular arrangement.
After calculating the total distance for every possible worker-bike arrangement, compare all the total distances.
Finally, pick the arrangement that has the smallest total distance. This is our best (optimal) solution because it minimizes the total walking distance for everyone.

Code Implementation

import itertools

def campus_bikes_brute_force(
    workers_positions, bikes_positions
):
    number_of_workers = len(workers_positions)
    number_of_bikes = len(bikes_positions)

    # Ensure there are at least as many bikes as workers
    if number_of_bikes < number_of_workers:
        return -1

    minimum_total_distance = float('inf')

    # Generate all possible bike assignments to workers.
    for bike_assignment in itertools.permutations(
        range(number_of_bikes), number_of_workers
    ):
        current_total_distance = 0

        # Calculate the total distance for the current assignment.
        for worker_index in range(number_of_workers):
            bike_index = bike_assignment[worker_index]

            worker_x, worker_y = workers_positions[worker_index]
            bike_x, bike_y = bikes_positions[bike_index]

            current_distance = abs(worker_x - bike_x) + abs(
                worker_y - bike_y
            )
            current_total_distance += current_distance

        # Update minimum total distance if necessary.
        minimum_total_distance = min(
            minimum_total_distance, current_total_distance
        )

    return minimum_total_distance

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Calculate the distance between each worker and each bike.
Organize these distances from shortest to longest, keeping track of which worker and bike each distance refers to.
Go through the distances in order from shortest to longest.
For each distance, check if the worker and bike involved have already been assigned.
If neither the worker nor the bike has been assigned yet, assign that bike to the worker.
Mark both the worker and the bike as assigned so they aren't considered again.
Continue until all workers have been assigned a bike.

Code Implementation

def assign_bikes(workers, bikes):
    distances = []
    number_of_workers = len(workers)
    number_of_bikes = len(bikes)

    for worker_index in range(number_of_workers):
        for bike_index in range(number_of_bikes):
            worker_x, worker_y = workers[worker_index]
            bike_x, bike_y = bikes[bike_index]
            distance = abs(worker_x - bike_x) + abs(worker_y - bike_y)
            distances.append((distance, worker_index, bike_index))

    distances.sort()

    assigned_bikes = [None] * number_of_workers
    worker_assigned = [False] * number_of_workers
    bike_assigned = [False] * number_of_bikes

    bikes_assigned_count = 0

    for distance, worker_index, bike_index in distances:
        # Only proceed if both worker and bike are unassigned
        if not worker_assigned[worker_index] and not bike_assigned[bike_index]:

            assigned_bikes[worker_index] = bike_index
            worker_assigned[worker_index] = True
            bike_assigned[bike_index] = True
            bikes_assigned_count += 1

            # Exit once all workers are assigned
            if bikes_assigned_count == number_of_workers:
                break

    return assigned_bikes

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty worker or bike array	Return an empty list or an error, as no assignments can be made without workers or bikes.
Workers and bikes have identical positions.	The distance calculation will result in zero, which should be handled correctly by the sorting or priority queue mechanism.
Maximum number of workers and bikes close to constraint limits (e.g., 1000 workers and 1000 bikes).	Ensure the solution scales efficiently, especially the distance calculation and assignment steps, avoiding excessive computation.
Integer overflow in distance calculation due to large coordinate values.	Use appropriate data types (e.g., long) to prevent integer overflow when calculating Manhattan distance.
Cases where the workers and bikes are far apart and results in very large distances.	The solution should still perform correctly, handling potentially large integer values appropriately and preventing performance degradation due to unnecessary calculations.
Number of workers and bikes are significantly different (e.g., many more workers than bikes or vice versa).	The algorithm should efficiently handle such unbalanced scenarios, prioritizing the closest assignments and ensuring all workers/bikes are considered if possible.
Coordinates are negative.	Manhattan distance calculation will handle negative coordinates correctly.
Duplicate worker or bike locations.	The assignment logic should not get stuck trying to reassign the same location and should correctly assign the closest available bike to each worker.

Empty worker or bike array

How to Handle:

Return an empty list or an error, as no assignments can be made without workers or bikes.

Workers and bikes have identical positions.

How to Handle:

The distance calculation will result in zero, which should be handled correctly by the sorting or priority queue mechanism.

Maximum number of workers and bikes close to constraint limits (e.g., 1000 workers and 1000 bikes).

How to Handle:

Ensure the solution scales efficiently, especially the distance calculation and assignment steps, avoiding excessive computation.

Integer overflow in distance calculation due to large coordinate values.

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow when calculating Manhattan distance.

Cases where the workers and bikes are far apart and results in very large distances.

How to Handle:

The solution should still perform correctly, handling potentially large integer values appropriately and preventing performance degradation due to unnecessary calculations.

Number of workers and bikes are significantly different (e.g., many more workers than bikes or vice versa).

How to Handle:

The algorithm should efficiently handle such unbalanced scenarios, prioritizing the closest assignments and ensuring all workers/bikes are considered if possible.

Coordinates are negative.

How to Handle:

Manhattan distance calculation will handle negative coordinates correctly.

Duplicate worker or bike locations.

How to Handle:

The assignment logic should not get stuck trying to reassign the same location and should correctly assign the closest available bike to each worker.