Loading page…
Practice problem · medium
A payments app sends each batch of transaction ids to two processors that take turns. Processor A handles the even slots of the batch, and processor B handles the odd slots. Slots are numbered from 0.
Processor A can only take even ids, and processor B only odd ids. Every batch has equally many even and odd ids, but they arrive mixed. You are asked to arrange the batch.
Even ids must sit at slots 0, 2, 4 and so on. Odd ids must sit at slots 1, 3, 5 and so on. Arrival order must be kept inside each parity.
Write interleave_parity(ids).
ids is a batch of transaction ids. It has an even length, and exactly half of the ids are even.Input: ids = [4, 2, 5, 7]
Output: [4, 5, 2, 7]Two write slots start at the first even slot, 0, and the first odd slot, 1. Each id goes to the slot of its parity, and that slot moves on by 2.
| id | Parity | Written to | Next even slot | Next odd slot |
|---|---|---|---|---|
| 4 | even | slot 0 | 2 | 1 |
| 2 | even | slot 2 | 4 | 1 |
| 5 | odd | slot 1 | 4 | 3 |
| 7 | odd | slot 3 | 4 | 5 |
The result is 4, 5, 2, 7.
Input: ids = [3, 8]
Output: [8, 3]The even id 8 goes to slot 0, and the odd id 3 goes to slot 1.
Input: ids = [1, 3, 2, 4]
Output: [2, 1, 4, 3]The evens 2, 4 take slots 0 and 2. The odds 1, 3 take slots 1 and 3.
2 ≤ ids.length ≤ 100,000, an even number, and exactly half of the ids are even (ids in a batch)1 ≤ ids[i] ≤ 10^6 (transaction ids)Finding the k-th even id and the k-th odd id by scanning from the start for every slot costs up to n steps per slot. That is about n × n ÷ 2 steps: 5 × 10^9 at n = 100,000, roughly 50 seconds. One pass with two write slots costs 100,000 steps.
interleave_parity · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.