Maximize equal values via one subarray shift
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
Given an integer array A of length n, you may perform at most one operation: choose any contiguous subarray A[l..r] and add an integer Δ (which may be negative, zero, or positive) to every element in A[l..r]. After the operation (or choosing not to use it), what is the maximum possible frequency of any value in the array? Also return one optimal choice of (l, r, Δ) that achieves this maximum. For example, for A = [2, 4, 6, 2, 4, 7], selecting subarray [4,6,2,4] and adding Δ = −2 yields [2, 2, 4, 0, 2, 7], producing three 2s.
Quick Answer: This question evaluates a candidate's understanding of array manipulation, frequency analysis, range-update reasoning, and optimization under a single contiguous subarray operation.