Allocate an Order from the Oldest Inventory Batches

Question

This question asks the candidate to devise an algorithm that allocates an order from the oldest inventory batches available.

Codemia · Accepted Answer

To allocate an order from the oldest inventory batches, we can use a greedy algorithm. The idea is to sort the inventory batches by their arrival date and then iterate through them to allocate items to the order until it is fulfilled or we run out of batches.

1. **Sort the inventory batches** by their arrival date.  
2. **Initialize a variable** to keep track of the remaining order quantity.  
3. **Iterate through the sorted batches**:  
   - If the batch quantity is greater than or equal to the remaining order quantity, allocate the order from this batch and update the batch quantity.  
   - If the batch quantity is less than the remaining order quantity, allocate all items from this batch and reduce the remaining order quantity accordingly.  
4. **Return the allocation result**.

The time complexity of this algorithm is O(n log n) due to the sorting step, where n is the number of inventory batches. The space complexity is O(1) if we sort in place, or O(n) if we use additional data structures for sorting.

```python
class InventoryBatch:
    def __init__(self, arrival_date, quantity):
        self.arrival_date = arrival_date
        self.quantity = quantity

def allocate_order(batches, order_quantity):
    # Sort batches by arrival date
    batches.sort(key=lambda x: x.arrival_date)
    allocation = []

for batch in batches:
        if order_quantity <= 0:
            break
        if batch.quantity >= order_quantity:
            allocation.append((batch.arrival_date, order_quantity))
            batch.quantity -= order_quantity
            order_quantity = 0
        else:
            allocation.append((batch.arrival_date, batch.quantity))
            order_quantity -= batch.quantity
            batch.quantity = 0

return allocation
```

Consider scenarios such as:  
- The order quantity exceeds the total available inventory.  
- All batches are exhausted before fulfilling the order.  
- Batches with zero quantity should be ignored.  
Handling these cases ensures the robustness of the solution.

Allocate an Order from the Oldest Inventory Batches

Airbnb

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Airbnb Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string