Compute reachability and minimal-time same-type scheduling
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
1) Given four integers a, b, c, d (1 <= a, b, c, d <=
1000), you may perform the following operations any number of times and in any order: (a, b) -> (a + b, b) or (a, b) -> (a, a + b). Return true or false: can (a, b) be converted to (c, d)?
2) Given an array taskMemory of n positive integers representing the memory required for each task, an array taskType of n positive integers representing task types, and an integer maxMemory, each task takes 1 unit of time. The server can process at most two tasks in parallel only if they are the same type and together require no more than maxMemory units. Compute the minimum time required to process all tasks. Example: n = 4, taskMemory = [7, 2, 3, 9], taskType = [1, 2, 1, 3], maxMemory = 10 -> answer = 3 units.
Quick Answer: This prompt evaluates integer reachability and invariant reasoning via repeated additive transformations (testing number-theoretic reachability and state-space analysis) alongside resource-aware scheduling and grouping logic for minimizing completion time under type and memory constraints, and it falls under the Coding & Algorithms domain.
