Campus Bikes

Campus Bikes

What is this problem about?

The Campus Bikes interview question is an assignment problem. You are given the coordinates of n workers and m bikes on a 2D plane (m >= n). You need to assign each worker a bike such that the overall assignment follows a "closest-first" priority based on Manhattan distance. If multiple (worker, bike) pairs have the same distance, the pair with the smaller worker index is preferred. If those are also equal, the one with the smaller bike index is preferred. This Campus Bikes coding problem is about stable sorting and greedy matching.

Why is this asked in interviews?

Google uses this to test a candidate's ability to handle custom sorting criteria and efficient data storage. Since the distances are integers and limited by the grid size, it tests if you can optimize the sorting using Bucket Sort or a Priority Queue. It’s a great exercise in processing large amounts of structured data with specific tie-breaking rules.

Algorithmic pattern used

This follows the Array, Sorting, Heap (Priority Queue) interview pattern.

1. Calculate the Manhattan distance for every possible (worker, bike) pair.
2. Store these pairs in a way that respects the distance, worker index, and bike index priorities.
3. Use a greedy approach: process pairs from the smallest distance upwards. Assign a bike to a worker only if both are currently "free."

Example explanation

Worker 0: (0,0), Worker 1: (1,1). Bike 0: (0,1), Bike 1: (2,2).

1. Distance (W0, B0) = 1.
2. Distance (W1, B1) = 2.
3. Distance (W0, B1) = 4.
4. Distance (W1, B0) = 1. Pairs at distance 1: (W0, B0) and (W1, B0). Priority: W0 comes before W1. So assign Bike 0 to Worker 0. Now Bike 0 is gone. Worker 1 must take Bike 1 (distance 2).

Common mistakes candidates make

• Full sort when not needed: Using a standard O(K log K) sort (where K = N * M) when the distance range is small enough for Bucket Sort (O(K)).
• Ignoring "Already Assigned" status: Not tracking which workers or bikes have already been paired, leading to double-assignments.
• Manhattan distance formula: Calculating Euclidean distance instead of Manhattan (|x1-x2| + |y1-y2|).

Interview preparation tip

Whenever you see a problem with many sorting criteria (distance, then index A, then index B), think about "Bucket Sort" if the primary value (distance) has a small range. It’s a powerful optimization that interviewers love to see.