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.

Compute reachability and minimal-time same-type scheduling

Quick Overview

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.

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.

Reachability under (a,b)->(a+b,b) / (a,b)->(a,a+b)

Given four integers a, b, c, d (1 <= a, b, c, d <= 1000), you may apply, any number of times and in any order, either operation: - (a, b) -> (a + b, b) - (a, b) -> (a, a + b) Return true if and only if the pair (a, b) can be transformed into the pair (c, d). Example: (1, 1) can become (5, 2) via (1,1)->(1,2)->(3,2)->(5,2), so the answer is true. (5, 2) cannot become (1, 1) because the values only ever grow, so that answer is false.

Constraints

1 <= a, b, c, d <= 1000
Operations may be applied any number of times and in any order
Values only ever increase, so reachability is checked by reducing (c, d) back toward (a, b)

Examples

Input: (1, 1, 5, 2)

Expected Output: True

Explanation: (1,1)->(1,2)->(3,2)->(5,2).

Input: (1, 1, 4, 7)

Expected Output: True

Explanation: Reachable by a sequence of additions (reverse-reduces (4,7) back to (1,1)).

Input: (2, 3, 2, 3)

Expected Output: True

Explanation: Already equal; zero operations needed.

Input: (5, 2, 1, 1)

Expected Output: False

Explanation: Target is smaller than the start; values can only grow.

Input: (1, 1, 2, 2)

Expected Output: False

Explanation: From (1,1) you can reach (1,2) or (2,1) but never (2,2).

Input: (3, 5, 8, 5)

Expected Output: True

Explanation: (3,5)->(8,5) directly via (a+b,b).

Input: (1, 1, 1000, 1)

Expected Output: True

Explanation: Repeatedly apply (a+b,b) keeping b=1 to grow a up to 1000.

Input: (4, 6, 5, 9)

Expected Output: False

Explanation: Reverse reduction lands on (1,0), not (4,6).

Hints

Both operations strictly increase one coordinate, so (c, d) must be component-wise >= (a, b) to be reachable.
Work backwards from (c, d): the larger coordinate must have come from repeatedly adding the smaller one, so reduce it modulo the smaller (like the Euclidean algorithm) instead of subtracting one step at a time.
Stop reducing a coordinate once it reaches its target (a or b): then check whether the remaining difference in the other coordinate is an exact multiple of the fixed one.

Minimum time to process same-type tasks in pairs

You are given an array taskMemory of n positive integers (the memory each task needs), an array taskType of n positive integers (each task's type), and an integer maxMemory. Each task takes 1 unit of time. The server can process at most two tasks in parallel, and only if they are the SAME type and their combined memory is at most maxMemory. Otherwise a task is processed alone. Compute the minimum total time to process all tasks. Example: n = 4, taskMemory = [7, 2, 3, 9], taskType = [1, 2, 1, 3], maxMemory = 10. Type 1 has memories {7, 3} which pair (7+3=10 <= 10) into 1 unit; type 2 {2} takes 1 unit; type 3 {9} takes 1 unit. Total = 3 units.

Constraints

taskMemory and taskType have the same length n
All memories and types are positive integers
Two tasks may share a time slot only if same type and combined memory <= maxMemory
Each task takes exactly 1 unit of time

Examples

Input: ([7, 2, 3, 9], [1, 2, 1, 3], 10)

Expected Output: 3

Explanation: Type1 {7,3} pair (=10), type2 {2} alone, type3 {9} alone -> 3 units.

Input: ([], [], 10)

Expected Output: 0

Explanation: No tasks.

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

Expected Output: 1

Explanation: Single task runs alone.

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

Expected Output: 3

Explanation: No two 6's fit together (6+6=12>10), so each runs alone.

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

Expected Output: 2

Explanation: Pair them into two slots of (1,1).

Input: ([4, 4, 4, 4], [1, 2, 1, 2], 8)

Expected Output: 2

Explanation: Type1 {4,4} pair, type2 {4,4} pair -> 2 units.

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

Expected Output: 3

Explanation: 10 runs alone; the three 1's give one pair plus one solo -> 1+2 = 3.

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

Expected Output: 3

Explanation: Two pairs (3+3=6) plus one leftover -> 3 units.

Hints

Tasks of different types can never share a slot, so handle each type independently and sum the results.
Within one type, sort the memories. The classic greedy is two pointers: try to pair the smallest remaining task with the largest remaining task.
If the smallest + largest exceeds maxMemory, the largest cannot pair with anything (everything else is <= the smallest), so it must run alone; otherwise pair them and move both pointers inward.

Quick Overview