Katkat
Back

Compute reachability and minimal-time same-type scheduling

AmazonSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

  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.