# Debug the Last-Element Random Allocation Case A random allocator stores available workers in an array. To allocate one worker in constant time, it chooses a random index, swaps that element with the final element, returns the chosen worker, and removes the tail. Diagnose why implementations often fail when the chosen index already is the final index, and describe a focused test strategy. ### Constraints & Assumptions - Allocation from an empty collection must be defined by the caller's contract. - Each available worker may be returned once before the collection is replenished. - The intended allocation and removal operations are O(1). ### Clarifying Questions to Ask - Can the random-index source be injected or fixed in a unit test? - Does the implementation remove by index, by value, or by a stale reference? - What should happen when exactly one worker remains? ```hint Protect the invariant Check the array contents and length immediately before and after allocation when the chosen element is already at the tail. ``` ### What a Strong Answer Covers - The swap-and-pop invariant and why a self-swap should be harmless. - Likely stale-index, double-removal, or empty-array branches that can corrupt the tail case. - Deterministic tests for zero, one, first, middle, and last selected indices. - Checks that every original worker is returned exactly once and no worker is skipped. ### Follow-up Questions 1. How would you make randomized tests reproducible? 2. How would the design change if workers could be added while allocation is running?