Katkat
Back

Compute Minimum Production Days

Interactive BrokersData Engineer · Technical Screen
MediumData EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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:

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.