Amazon Coding Interview: Bounded Increasing Subsequence

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the SDE2 role at Amazon. We'll work through two separate coding problems together, so please think out loud as you code. You can pause the interview at any time with the Pause button at the top right of your screen.

The first problem is about finding the longest steadily climbing run you can pick out of a sequence, and it's up in your Problem tab now. Take your time reading it through, and ask me anything you'd like before you start.

The problem

Find the longest steadily climbing run of values you can pick from a sequence while keeping their original order.

• arr: a list of integers (may contain duplicates and negatives).
• k: a positive integer, the largest allowed step.

Return the length of the longest subsequence of arr (elements kept in their original relative order, not necessarily contiguous) that is strictly increasing and where each element minus the one before it is at most k. An empty arr gives 0; any single element is a valid subsequence of length 1.

Example: arr = [7, 1, 4, 5, 8, 8, 10, 6, 7, 7, 7, 8], k = 4 → 6 (e.g. [1, 4, 5, 6, 7, 8]).

0 ≤ len(arr) ≤ 10^5; 1 ≤ k ≤ 10^9.