A distributed file system stores multiple replicas of each block so data remains available when hardware fails. Replicas on the same rack share power and networking, so placing all copies together leaves them vulnerable to one rack-level failure.
Design a RackAwareReplicaPlacer class:
RackAwareReplicaPlacer() creates a stateless placement utility.int[] place(int[] rackCapacities, int numReplicas) returns how many replicas are placed on each rack.
rackCapacities[i] is the number of free replica slots on rack i. Place replicas in round-robin order by rack index:
- Give at most one replica to each eligible rack per rotation.
- Skip racks that have reached capacity.
- Continue cycling until
numReplicas replicas have been placed or every rack is full.
Return an array aligned with rackCapacities. Do not modify the input array, and treat each call independently.
Example 1:
Input:
Output:
Explanation: The first rotation places one replica on each rack. All three copies occupy different rack failure domains.
Example 2:
Input:
Output:
Explanation: The first three replicas use racks 0, 1, and 2. Racks 0 and 1 are then full, so rack 2 receives the fourth replica.
Constraints
1 <= rackCapacities.length <= 10^50 <= rackCapacities[i] <= 10^50 <= numReplicas <= 10^5- At most
100 calls are made to place.
Place Rack-Aware Replicasmedium