Loading page…
Practice problem · easy
A warehouse keeps the item codes on one shelf as a sorted list. The list is stored in a fixed block with spare room at the end, so a delivery can be added without allocating a new block.
A delivery arrives with its own sorted list of item codes. You are asked to merge the delivery into the shelf list so the result is one sorted list. You must use the spare room, and the shelf list is edited in place.
Write merge_inventory(shelf, m, extra).
shelf is a block of m + n slots, where n is the length of extra. The first m slots hold sorted item codes. The last n slots are spare and hold 0.extra is the delivery: n item codes in sorted order.shelf, in sorted order, using only the spare room. Repeated codes are all kept.shelf.Input: shelf = [2, 5, 9, 0, 0, 0], m = 3, extra = [1, 5, 10]
Output: [1, 2, 5, 5, 9, 10]The walk fills the shelf from the back, so unread codes are never overwritten. Pointer i is the last unread shelf code, j is the last unread delivery code, and k is the last free slot.
| k | i | j | shelf[i] | extra[j] | Placed |
|---|---|---|---|---|---|
| 5 | 2 | 2 | 9 | 10 | 10, from the delivery |
| 4 | 2 | 1 | 9 | 5 | 9, from the shelf |
| 3 | 1 | 1 | 5 | 5 | 5, from the delivery (a tie takes the delivery) |
| 2 | 1 | 0 | 5 | 1 | 5, from the shelf |
| 1 | 0 | 0 | 2 | 1 | 2, from the shelf |
| 0 | -1 | 0 | 1 | 1, from the delivery |
The delivery is used up, so the walk ends. The shelf is 1, 2, 5, 5, 9, 10.
Input: shelf = [4, 0], m = 1, extra = [3]
Output: [3, 4]The one delivery code is smaller, so it goes first and the shelf code moves to the spare slot.
Input: shelf = [0, 0], m = 0, extra = [8, 9]
Output: [8, 9]The shelf holds nothing yet, so the delivery fills it.
1 ≤ shelf.length ≤ 100,000, and shelf.length = m + extra.length (the block size)0 ≤ m ≤ shelf.length and 0 ≤ extra.length ≤ 50,0001 ≤ shelf[i], extra[j] ≤ 10^6 (item codes), with 0 in the spare slotsInserting each delivery code into the shelf list by scanning costs up to m steps for each of n codes. With m = n = 50,000 that is about 2.5 × 10^9 steps: roughly 25 seconds at 10^8 operations a second. A merge from the back makes at most m + n steps, 100,000 in all.
merge_inventory · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.