Schedule vector ops on heterogeneous cores

Q: Schedule vector ops on heterogeneous cores

This question evaluates understanding of scheduling and load-balancing heuristics for heterogeneous processors, algorithmic complexity reasoning, and efficient implementation of constrained assignment problems.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Question

Loading...

You are optimizing a “vectored computation” on a heterogeneous (non-SMP) CPU with asymmetric cores.

Hardware model

There are two core types:

D-cores : can execute division operations only.
MD-cores : can execute multiplication and division , and may have different per-op costs.

Each core runs one operation at a time; operations assigned to the same core run sequentially.

Workload

You are given a vector of independent operations (order doesn’t matter):

ops[i] ∈ {'M', 'D'} meaning multiply or divide.

And performance parameters:

D-core: time_D_on_Dcore
MD-core: time_D_on_MDcore , time_M_on_MDcore

Task

Design and implement a function that produces a near-optimal schedule to minimize the total completion time (makespan):

def schedule_ops(ops: list[str], num_d: int, num_md: int,
                 tD_d: int, tD_md: int, tM_md: int) -> tuple[int, list[int]]:
    """
    Returns:
      - estimated minimal makespan (time units)
      - an assignment array where assignment[i] is the core index chosen for ops[i]
        (e.g., cores 0..num_d-1 are D-cores, num_d..num_d+num_md-1 are MD-cores)
    """

Requirements

Must never assign an M op to a D-core.
Should handle large inputs (e.g., up to 1e5 operations).
The goal is not perfect optimality (the exact optimum may be expensive); aim for a good heuristic with clear reasoning.

Edge cases

num_d=0 or num_md=0
All ops are the same type
Very imbalanced costs (e.g., MD-core divides much slower than D-core)