How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Interactive.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at Interactive during technical interviews.

Compute Minimum Production Days | Interactive Coding Question

Quick Overview

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.

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.

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. Return the minimum number of days needed to produce all products in the given order. 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. Assume `len(products)` can be large, so an O(n) solution is preferred.

Constraints

0 <= len(products) <= 10^6
0 <= space <= 10^9
Each products[i] is an integer product-type id
Products must be produced strictly in the given order

Examples

Input: ([1, 3, 1, 3, 2], 2)

Expected Output: 6

Explanation: The worked example: 1,3 on days 1-2, an idle day 3 while type 1 cools, then 1,3,2 on days 4-6.

Input: ([], 3)

Expected Output: 0

Explanation: No products to produce, so zero days are needed.

Input: ([5], 10)

Expected Output: 1

Explanation: A single product takes exactly one day regardless of the cooling period.

Input: ([5, 5, 5], 2)

Expected Output: 7

Explanation: All identical: scheduled on days 1, 4, 7 (each waits space=2 full days after the previous), so 7 days total.

Input: ([1, 2, 3, 4], 5)

Expected Output: 4

Explanation: All distinct types never trigger cooling, so each produces on consecutive days 1-4.

Input: ([1, 1, 1], 0)

Expected Output: 3

Explanation: space=0 means no cooling at all, so the answer is just the number of products.

Input: ([7, 7], 1)

Expected Output: 3

Explanation: First 7 on day 1; the second 7 must wait until day 1+1+1=3.

Input: ([2, 2, 3, 2], 1)

Expected Output: 5

Explanation: 2 on day1; 2 cooled to day3; 3 on day4; final 2 earliest is day5 (cooled to 3+1+1=5).

Hints

Because the order is fixed, delaying a job that could be produced now can never reduce the total time. So schedule every product on the earliest legal day.
Track the day the most recent job was scheduled (`day`) and, per product type, the last day that type was produced (`last_day[p]`).
For each product p the earliest valid day is max(day + 1, last_day[p] + space + 1). Update day and last_day[p] to that value, then move on.

Quick Overview