Solve interval deletion and GCD subarray problems
Overview
This question evaluates algorithm design and complexity-analysis skills across interval manipulation and number-theoretic array operations, testing competency in reasoning about interval coverage and deletions as well as GCD properties and subarray modification under constraints.
Amazon
Jul 16, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
0
0
- 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.
- 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.