Amazon·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

May 2026

Summary

Amazon OA for a SWE role, one coding problem about array manipulation. Pretty standard competitive programming flavor but the edge cases tripped me up more than I expected.

Questions Asked (1)

Given an integer array and a target value k, you can pick any contiguous subarray and add a single integer x to every element in it (at most once). What is the maximum number of elements you can make equal to k?

Algorithms & Data Structures

Author's notes

My first instinct was greedy and it was wrong.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Reframe the problem by considering the difference array d[i] = k - a[i]. We need to find a contiguous subarray where all d[i] are equal (to some value x) and maximize the count of zeros in d after adding x to that subarray. Use a hash map to track the maximum frequency of each difference value within a sliding window, ensuring all elements in the window share the same d[i].

Pro tip: Clarify that x can be any integer, including negative, and that the operation is applied at most once. This shows attention to edge cases and prevents misinterpretation.

1. Transform the problem

Compute the difference array d[i] = k - a[i]. The goal becomes: choose a contiguous subarray and add a constant x to all d[i] in it, such that the number of zeros in d is maximized.

2. Identify the condition for equality

After adding x to a subarray, an element becomes zero if d[i] + x = 0, i.e., x = -d[i]. Thus, all elements in the chosen subarray must have the same d[i] value to become zero simultaneously.

3. Find the longest subarray with equal d[i]

Scan the array and use a hash map to track the maximum frequency of each d[i] value within a sliding window where all elements have the same d[i]. The window length is the count of elements that can be made zero.

4. Consider elements already equal to k

Elements with d[i] = 0 are already zero and can be included in the count without needing the operation. They can be part of the subarray if x = 0, or counted separately if the subarray does not include them.

5. Compute the maximum

The answer is the maximum over all possible x of (number of zeros in d after operation). This is equivalent to the maximum frequency of any d[i] value in a contiguous subarray, plus any zeros outside that subarray if x ≠ 0.

Key Points to Mention

Time complexity: O(n) with a hash map and sliding window, space O(n).
Edge cases: all elements already equal to k, no elements can be made equal, x can be negative.
The operation can be applied at most once, so we can choose not to apply it.
The difference array transformation simplifies the problem to finding the longest subarray with equal values.
Use a hash map to track the maximum frequency of each difference value in a sliding window.
The answer is the maximum of (max frequency of any d[i] in a subarray) and (count of zeros in d) if we choose not to apply the operation.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.