Compute Minimum Production Days
Company: Interactive
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
You are given a list of product IDs `products`, where `products[i]` is the type of the product that must be produced at step `i`, and a non-negative integer `space` representing a required cooling period.
Rules:
- You can produce at most one product per day.
- The products must be produced in the given order.
- After producing a product with type `x` on day `d`, you must wait at least `space` full days before producing type `x` again. In other words, the next valid day to produce the same type is `d + space + 1`.
- During waiting days, you may either produce the next product in order (if it is valid to produce) or stay idle.
Write a function that returns the minimum number of days needed to produce all products in the given order:
```python
def min_days(products: List[int], space: int) -> int
```
**Example**
- Input: `products = [1, 3, 1, 3, 2]`, `space = 2`
- Output: `6`
One optimal schedule:
- Day 1: produce `1`
- Day 2: produce `3`
- Day 3: idle
- Day 4: produce `1`
- Day 5: produce `3`
- Day 6: produce `2`
So the minimum total number of days is `6`.
Assume `len(products)` can be large, so an `O(n)` solution is preferred.
Quick Answer: A data engineering coding screen on greedy scheduling under a cooldown constraint: produce an ordered list of products, one per day, where each product type must cool down for `space` days before it can be produced again. Candidates must return the minimum number of days, ideally in O(n) time using a hash map of last-produced days.