Determine reachability and optimize task scheduling
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
LeetCode 780. Reaching Points: Given four integers a, b, c, d (1 <= a, b, c, d <=
1000). Starting from (a, b) you may repeatedly apply either operation (x, y) → (x + y, y) or (x, y) → (x, x + y). Determine whether you can reach exactly (c, d). Return True or False. Given an array taskMemory of n positive integers (memory per task), an array taskType of n positive integers (task type), 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. Find the minimum total time required to process all tasks.
https://leetcode.com/problems/reaching-points/description/
Quick Answer: This question evaluates understanding of discrete reachability and resource-constrained scheduling, testing the ability to reason about iterative coordinate transformations and to optimize parallel task assignment under type and memory limits.
Reaching Points
You are given four integers a, b, c, and d (1 <= a, b, c, d <= 10^9). Starting from the point (a, b), you may repeatedly apply either of the following operations:
- (x, y) -> (x + y, y)
- (x, y) -> (x, x + y)
Return `True` if you can transform the starting point (a, b) into exactly the target point (c, d) using zero or more operations, otherwise return `False`.
Example 1:
Input: a = 1, b = 1, c = 3, d = 5
Output: True
Explanation: (1,1) -> (1,2) -> (3,2) -> (3,5).
Example 2:
Input: a = 1, b = 1, c = 2, d = 2
Output: False
Example 3:
Input: a = 1, b = 1, c = 1, d = 1
Output: True (no operations needed).
Constraints
- 1 <= a, b, c, d <= 10^9
- Each operation strictly increases one coordinate, so coordinates never decrease.
- Work backwards from (c, d) using the modulo operation to collapse the otherwise-exponential forward search.
Examples
Input: (1, 1, 3, 5)
Expected Output: True
Explanation: (1,1)->(1,2)->(3,2)->(3,5).
Input: (1, 1, 2, 2)
Expected Output: False
Explanation: From (1,1) any move yields a point with two distinct coordinates that stay coprime; (2,2) is unreachable.
Hints
- A forward BFS/DFS explodes exponentially. Reverse the process: the predecessor of (c, d) is either (c - d, d) (if c > d) or (c, d - c) (if d > c).
- Repeatedly subtracting the smaller coordinate from the larger is exactly the Euclidean algorithm, so replace the loop of subtractions with a single modulo (%) operation.
- When one coordinate finally matches its target (e.g. c == a), the other must be reachable by adding the fixed coordinate a whole number of times: check that (d - b) is a non-negative multiple of a.
Minimum Time to Process Same-Type Tasks
You are given two integer arrays `taskMemory` and `taskType` of equal length n, and an integer `maxMemory`. For the i-th task, `taskMemory[i]` is its memory requirement and `taskType[i]` is its type (both positive).
Each task takes 1 unit of time. The server may process at most two tasks in parallel during a single time unit, but only if both tasks have the **same type** and the sum of their memory requirements is no more than `maxMemory`. A task may also run alone in a time unit.
Return the minimum total time required to process all tasks.
Example 1:
Input: taskMemory = [4, 6, 5, 5], taskType = [1, 1, 2, 2], maxMemory = 10
Output: 2
Explanation: Pair the two type-1 tasks (4 + 6 = 10) in one unit, and the two type-2 tasks (5 + 5 = 10) in another unit.
Example 2:
Input: taskMemory = [6, 6, 6], taskType = [1, 1, 1], maxMemory = 10
Output: 3
Explanation: No two of these tasks fit together (6 + 6 = 12 > 10), so each runs alone.
Constraints
- Tasks of different types can never share a time unit.
- 1 <= taskMemory[i], taskType[i]; 1 <= maxMemory.
- Group by type, then solve each group independently and sum the results.
Examples
Input: ([4, 6, 5, 5], [1, 1, 2, 2], 10)
Expected Output: 2
Explanation: Type 1: 4+6=10 pairs. Type 2: 5+5=10 pairs. Two time units.
Input: ([7, 8, 3, 2], [1, 1, 1, 1], 10)
Expected Output: 2
Explanation: Sorted [2,3,7,8]: pair 2+8=10 and 3+7=10. Two units.
Hints
- Tasks of different types can never be paired, so split the tasks into independent groups by type and solve each group on its own.
- Within one type, sort the memory values. Use two pointers: try to pair the smallest remaining task with the largest remaining task.
- If the smallest and largest fit together (sum <= maxMemory), pair them (one time unit, advance both pointers); otherwise the largest must run alone (one time unit, move only the right pointer).