Implement minimal-cost overtime/contractor allocation
Company: Capital One
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
You must cover H extra engineering hours this week at minimum cost using employee overtime and optional contractors. Each employee i has a maximum overtime cap cap[i] and an overtime cost rate cost_emp[i] per hour. Contractors have unlimited availability at rate cost_contractor per hour. Return both the minimal total cost and an allocation of hours per employee and contractors. Constraints: 0 ≤ hours[i] ≤ cap[i]; sum(hours[i]) + contractor_hours = H. If multiple allocations have the same minimal cost, prefer the one that minimizes contractor_hours; if still tied, minimize the variance of employee overtime hours.
Input example:
H = 120
cap = [8, 20, 40, 12]
cost_emp = [55, 35, 60, 45]
cost_contractor = 50
Questions:
(a) Describe and implement an O(n log n) algorithm that returns the allocation and total cost. Justify correctness and complexity.
(b) Extend your algorithm to handle per-employee overtime tiering (first t[i] hours at rate r1[i], remaining at r2[i] > r1[i]) and a global contractor capacity C. Provide the modified approach and complexity.
(c) For the input above, what is the exact optimal allocation and cost?
Quick Answer: This question evaluates a candidate's ability in cost-minimizing resource allocation and algorithm design, specifically testing greedy strategies, sorting-based selection, tie-breaking rules, constraint handling, and time-complexity analysis.
Allocate H extra hours across employee caps and unlimited contractors. Prefer lower cost, use employees before equal-cost contractors, and balance equal-rate employees by current hours.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: (120, [8,20,40,12], [55,35,60,45], 50)
Expected Output: {'totalCost': 5640, 'employeeHours': [0, 20, 0, 12], 'contractorHours': 88}
Explanation: Prompt input.
Input: (10, [5,5], [50,50], 50)
Expected Output: {'totalCost': 500, 'employeeHours': [5, 5], 'contractorHours': 0}
Explanation: Tie prefers employees and balances.
Input: (7, [2,2], [100,90], 10)
Expected Output: {'totalCost': 70, 'employeeHours': [0, 0], 'contractorHours': 7}
Explanation: Contractor cheaper.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.