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 Technical Screen rounds at Amazon.

What role is this question designed for?

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

Solve interval deletion and GCD subarray problems

Quick Overview

This question evaluates proficiency in combinatorial algorithms, specifically interval covering and GCD-based subarray optimization. It tests the ability to design efficient near-linearithmic solutions for classic greedy and number-theory problems commonly assessed in software engineering interviews.

Solve interval deletion and GCD subarray problems

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

1) Given n closed intervals [li, ri] on a number line, remove the fewest intervals so that among the remaining intervals there exists at least one interval that fully covers all other remaining intervals (i.e., there is [L, R] such that for every remaining [l, r], L <= l and r <= R). Return the minimum number of deletions required and describe an algorithm with time and space complexity. 2) Given an integer array nums and an integer k (maximum number of elements you may change within a chosen subarray), find the minimum length of a contiguous subarray such that, after modifying at most k elements inside that subarray to any positive integers of your choice, the subarray’s greatest common divisor is greater than 1. Return the minimal length and outline an efficient approach. Example: nums = [2, 2, 4, 9, 6], k = 1 -> output 1.

Quick Answer: This question evaluates proficiency in combinatorial algorithms, specifically interval covering and GCD-based subarray optimization. It tests the ability to design efficient near-linearithmic solutions for classic greedy and number-theory problems commonly assessed in software engineering interviews.

Fewest Interval Deletions So One Interval Covers the Rest

Given `n` closed intervals `[l_i, r_i]` on a number line, remove the **fewest** intervals so that, among the remaining intervals, at least one interval **fully covers all the others** — i.e. there exists a remaining `[L, R]` such that for every remaining `[l, r]` we have `L <= l` and `r <= R`. Return the minimum number of deletions required. The covering interval must be one of the remaining intervals (not a virtual super-interval), and an interval is considered to cover itself. Intervals may be identical, nested, or disjoint. Endpoints can be large. **Reduction:** minimizing deletions equals maximizing how many intervals you keep under a single chosen container. For container `[L, R]`, the keepable intervals are exactly those with `l >= L` and `r <= R`; let `c` be that count (the container counts itself). The answer is `n - max(c)`. Example: `[[1,10],[2,3],[4,5],[6,7]]` -> `0` (the interval `[1,10]` already covers all others). Example: `[[1,2],[3,4],[5,6]]` -> `2` (pairwise disjoint, keep only one).

Constraints

0 <= n <= 10^5
Each interval is [l, r] with l <= r (degenerate point intervals l == r allowed)
Endpoints may exceed 32-bit range; coordinate-compress right endpoints
Intervals may be identical, nested, or disjoint

Examples

Input: ([[1, 10], [2, 3], [4, 5], [6, 7]],)

Expected Output: 0

Explanation: [1,10] already covers [2,3],[4,5],[6,7], so no deletions are needed.

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

Expected Output: 2

Explanation: All three are pairwise disjoint; the best container holds only itself, so keep 1 and delete 2.

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

Expected Output: 0

Explanation: All identical; any one covers the other two, so zero deletions.

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

Expected Output: 0

Explanation: A single interval covers itself; nothing to delete.

Input: ([],)

Expected Output: 0

Explanation: No intervals means zero deletions.

Input: ([[1, 10], [2, 8], [3, 9], [0, 4]],)

Expected Output: 1

Explanation: Container [1,10] covers itself, [2,8], and [3,9] (count 3) but not [0,4] since 0<1. Best kept = 3, so delete 1.

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

Expected Output: 0

Explanation: Container [1,4] covers [2,4] (l>=1, r<=4) and [1,3]; equal-left ties are handled, count 3, delete 0.

Input: ([[0, 100], [10, 20], [10, 90], [50, 60], [101, 102]],)

Expected Output: 1

Explanation: [0,100] covers the three nested intervals (count 4) but not [101,102]; keep 4, delete 1.

Hints

Minimizing deletions equals maximizing kept intervals under one chosen container. Fix a container [L, R]; what must every other kept interval satisfy? (l >= L and r <= R.)
Counting how many intervals a container dominates is a two-sided 2D dominance count. Eliminate one inequality by sorting on the left endpoint, and answer the other with a Fenwick/BIT prefix query over compressed right endpoints.
Handle ties carefully: insert ALL intervals sharing the same left endpoint into the BIT before querying any of them, so an equal-L interval (including the container itself and exact duplicates) is counted iff its right endpoint <= R.

Shortest Subarray With GCD > 1 After At Most k Changes

Given an integer array `nums` and an integer `k` (the maximum number of elements you may change **inside a chosen contiguous subarray**), find the **minimum length** of a contiguous subarray such that, after modifying at most `k` of its elements to any positive integers of your choice, the subarray's greatest common divisor is greater than 1. Return the minimal length, or `-1` if no valid subarray exists. **Key insight:** `gcd > 1` iff some prime `p` divides every element. Inside the window you may set up to `k` elements to multiples of `p` for free, so a window is feasible for prime `p` iff at most `k` of its elements are NOT divisible by `p`. Candidate primes can be restricted to the prime factors of array elements (a prime dividing nothing only ever helps a window of length <= k, already covered by the length-1 case when k >= 1). For each candidate prime, a two-pointer sliding window counting non-multiples finds the shortest feasible window; take the global minimum (plus the universal length-1 window when `k >= 1`). Example: `nums = [2,2,4,9,6]`, `k = 1` -> `1` (the single element `2` already has gcd 2 > 1, no change needed). Return `-1` only when `k = 0` and every element equals 1 (no prime divides any element).

Constraints

0 <= n <= 10^5
1 <= nums[i] (positive integers; may exceed 32-bit — use trial division / Pollard-rho instead of the sieve for very large values)
0 <= k <= n
Return -1 when no valid subarray exists (only when k == 0 and every element equals 1)

Examples

Input: ([2, 2, 4, 9, 6], 1)

Expected Output: 1

Explanation: The single element 2 already has gcd 2 > 1 with zero changes, so the minimum length is 1.

Input: ([6, 10, 15], 0)

Expected Output: 1

Explanation: With k=0, the single element 6 alone has gcd 6 > 1, so length 1 suffices.

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

Expected Output: -1

Explanation: k=0 and every element is 1; no prime divides any element, so no window of any length has gcd > 1.

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

Expected Output: 1

Explanation: k>=1 lets you change a single element to any value > 1, giving a length-1 window.

Input: ([], 5)

Expected Output: -1

Explanation: Empty array has no subarray, so the answer is -1.

Input: ([9], 0)

Expected Output: 1

Explanation: k=0 but 9 > 1 already has gcd 9, so length 1.

Input: ([35, 22, 13], 0)

Expected Output: 1

Explanation: Each element is > 1, so a length-1 window already has gcd > 1 even with no changes.

Input: ([7, 7, 7], 0)

Expected Output: 1

Explanation: Element 7 alone has gcd 7 > 1 with k=0, so the minimum length is 1.

Hints

gcd > 1 over a set means a single prime p divides every element. A changed element can always be made a multiple of p, so changes are free with respect to p — only unchanged non-multiples constrain you.
You cannot try every prime. A prime is only worth testing if it divides at least one array element; any other prime makes every element a non-multiple, so it only helps windows of length <= k (already covered by the length-1 case when k >= 1). Factor each value with an SPF sieve.
For each candidate prime, run a two-pointer window counting non-multiples; shrink while the count exceeds k. The shortest feasible window over all primes (and the universal length-1 window when k >= 1) is the answer; impossible only when k == 0 and all elements are 1.

Quick Overview

Solve interval deletion and GCD subarray problems

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Fewest Interval Deletions So One Interval Covers the Rest

Constraints

0 <= n <= 10^5
Each interval is [l, r] with l <= r (degenerate point intervals l == r allowed)
Endpoints may exceed 32-bit range; coordinate-compress right endpoints
Intervals may be identical, nested, or disjoint

Examples

Input: ([[1, 10], [2, 3], [4, 5], [6, 7]],)

Expected Output: 0

Explanation: [1,10] already covers [2,3],[4,5],[6,7], so no deletions are needed.

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

Expected Output: 2

Explanation: All three are pairwise disjoint; the best container holds only itself, so keep 1 and delete 2.

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

Expected Output: 0

Explanation: All identical; any one covers the other two, so zero deletions.

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

Expected Output: 0

Explanation: A single interval covers itself; nothing to delete.

Input: ([],)

Expected Output: 0

Explanation: No intervals means zero deletions.

Input: ([[1, 10], [2, 8], [3, 9], [0, 4]],)

Expected Output: 1

Explanation: Container [1,10] covers itself, [2,8], and [3,9] (count 3) but not [0,4] since 0<1. Best kept = 3, so delete 1.

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

Expected Output: 0

Explanation: Container [1,4] covers [2,4] (l>=1, r<=4) and [1,3]; equal-left ties are handled, count 3, delete 0.

Input: ([[0, 100], [10, 20], [10, 90], [50, 60], [101, 102]],)

Expected Output: 1

Explanation: [0,100] covers the three nested intervals (count 4) but not [101,102]; keep 4, delete 1.

Hints

Minimizing deletions equals maximizing kept intervals under one chosen container. Fix a container [L, R]; what must every other kept interval satisfy? (l >= L and r <= R.)
Counting how many intervals a container dominates is a two-sided 2D dominance count. Eliminate one inequality by sorting on the left endpoint, and answer the other with a Fenwick/BIT prefix query over compressed right endpoints.
Handle ties carefully: insert ALL intervals sharing the same left endpoint into the BIT before querying any of them, so an equal-L interval (including the container itself and exact duplicates) is counted iff its right endpoint <= R.

Shortest Subarray With GCD > 1 After At Most k Changes

Constraints

0 <= n <= 10^5
1 <= nums[i] (positive integers; may exceed 32-bit — use trial division / Pollard-rho instead of the sieve for very large values)
0 <= k <= n
Return -1 when no valid subarray exists (only when k == 0 and every element equals 1)

Examples

Input: ([2, 2, 4, 9, 6], 1)

Expected Output: 1

Explanation: The single element 2 already has gcd 2 > 1 with zero changes, so the minimum length is 1.

Input: ([6, 10, 15], 0)

Expected Output: 1

Explanation: With k=0, the single element 6 alone has gcd 6 > 1, so length 1 suffices.

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

Expected Output: -1

Explanation: k=0 and every element is 1; no prime divides any element, so no window of any length has gcd > 1.

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

Expected Output: 1

Explanation: k>=1 lets you change a single element to any value > 1, giving a length-1 window.

Input: ([], 5)

Expected Output: -1

Explanation: Empty array has no subarray, so the answer is -1.

Input: ([9], 0)

Expected Output: 1

Explanation: k=0 but 9 > 1 already has gcd 9, so length 1.

Input: ([35, 22, 13], 0)

Expected Output: 1

Explanation: Each element is > 1, so a length-1 window already has gcd > 1 even with no changes.

Input: ([7, 7, 7], 0)

Expected Output: 1

Explanation: Element 7 alone has gcd 7 > 1 with k=0, so the minimum length is 1.

Hints

gcd > 1 over a set means a single prime p divides every element. A changed element can always be made a multiple of p, so changes are free with respect to p — only unchanged non-multiples constrain you.
You cannot try every prime. A prime is only worth testing if it divides at least one array element; any other prime makes every element a non-multiple, so it only helps windows of length <= k (already covered by the length-1 case when k >= 1). Factor each value with an SPF sieve.
For each candidate prime, run a two-pointer window counting non-multiples; shrink while the count exceeds k. The shortest feasible window over all primes (and the universal length-1 window when k >= 1) is the answer; impossible only when k == 0 and all elements are 1.