How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

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

Determine reachability and optimize task scheduling

Q: Determine reachability and optimize task scheduling

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.

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.

Input: (1, 1, 1, 1)

Expected Output: True

Explanation: Start already equals target; zero operations needed.

Input: (3, 3, 12, 9)

Expected Output: True

Explanation: Reverse: (12,9)->(3,9)->(3,6)->(3,3).

Input: (1, 2, 1000000000, 1)

Expected Output: False

Explanation: d would have to shrink below its start value b=2, which the operations can never do.

Input: (2, 4, 6, 4)

Expected Output: True

Explanation: (2,4)->(6,4) via (x,y)->(x+y,y).

Input: (1, 1, 1, 1000000)

Expected Output: True

Explanation: Keep applying (x,y)->(x,x+y) with x fixed at 1 to grow the second coordinate to 1000000.

Input: (5, 7, 5, 7)

Expected Output: True

Explanation: Start equals target.

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.

Input: ([6, 6, 6], [1, 1, 1], 10)

Expected Output: 3

Explanation: 6+6=12 > 10 so nothing pairs; three units.

Input: ([1], [5], 10)

Expected Output: 1

Explanation: Single task runs alone in one unit.

Input: ([5, 5, 5, 5], [1, 2, 1, 2], 10)

Expected Output: 2

Explanation: Two type-1 tasks pair (one unit); two type-2 tasks pair (one unit).

Input: ([9, 9, 9, 9], [1, 1, 1, 1], 10)

Expected Output: 4

Explanation: Every pair sums to 18 > 10, so all four run alone.

Input: ([], [], 10)

Expected Output: 0

Explanation: No tasks, no time.

Input: ([3, 3, 3, 3, 3, 3], [1, 1, 1, 2, 2, 2], 6)

Expected Output: 4

Explanation: Each type has three 3's: pair two (3+3=6) and one alone = 2 units per type, 4 total.

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).

Quick Overview

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.