Maximum Number of Achievable Transfer Requests

Maximum Number of Achievable Transfer Requests

What is this problem about?

The Maximum Number of Achievable Transfer Requests coding problem gives you n buildings and a list of transfer requests, where each request moves one employee from one building to another. You want to satisfy as many requests as possible such that at the end, every building's net employee count change is zero (the building population returns to its original state). This is a constraint satisfaction maximization problem.

Why is this asked in interviews?

Amazon uses this problem to test bit manipulation enumeration on small-scale inputs (n ≤ 20 requests). While the constraint n ≤ 20 immediately suggests bitmask enumeration, the verification step (checking zero net change for all buildings) requires careful implementation. It rewards candidates who recognize the upper bound on complexity and implement the check cleanly.

Algorithmic pattern used

Bitmask enumeration: Enumerate all 2^n subsets of requests. For each subset, compute the net change in employee count for each building (each accepted request adds one to the destination and removes one from the source). If all buildings have zero net change, count the number of set bits (accepted requests) and update the maximum. Total complexity: O(2^n * (n + buildings)).

With n ≤ 20 (though typically n ≤ 16), this is about 1 million iterations — very feasible.

Example explanation

Buildings: 5. Requests: [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]

• Try subset {0,1,2} (first 3 requests): [0→1, 1→0, 0→1].
  • Building 0: -1-1+0 = -2? Net: leaves 0 twice (+source), receives 0 once? Request[0]: 0 leaves, 1 arrives. Request[1]: 1 leaves, 0 arrives. Request[2]: 0 leaves, 1 arrives.
  • Building 0 net: -1+1-1 = -1. Not zero. Invalid.
• Try subset {0,1}: [0→1, 1→0]. Building 0: -1+1=0. Building 1: +1-1=0. All zero! Count=2.
• Continue searching for larger valid subsets.

Common mistakes candidates make

• Not checking all buildings for zero net change: Only checking buildings involved in the selected requests misses buildings that might have a net imbalance from not being involved.
• Integer overflow for large bit masks: Use appropriate integer types for masks when n is large.
• Forgetting that popcount gives the accepted count: The answer is the number of set bits in the best valid mask, not a separate counter.

Interview preparation tip

For the Array Enumeration Backtracking Bit Manipulation interview pattern, bitmask enumeration with feasibility check is the go-to template when n ≤ 20. Always state the complexity explicitly (2^n * verification_cost) to show you've analyzed it. This pattern appears in many NP-hard problems where small n makes brute force feasible.