D.E. Shaw SDE Interview Question
Summary
Interviewed at D.E. Shaw for SDE role. The interview included a problem-solving question about transforming an array to match a target array with minimum operations. The candidate was asked to determine the minimum number of operations required and provide hints for solving the problem.
Full Experience
From an array source of n integers, in a single ALL operation, you can choose any even-length subarray and alternately add and subtract 1 from each element of the subarray from left to right. For example, if source = [1, 2, 3, 4, 5, 6], the subarray [3, 4, 5, 6] can be chosen and transformed into [4, 3, 6, 5]. Then, the updated source becomes [1, 2, 4, 3, 6, 5].
Given two arrays source and target of n integers, the task is to find the minimum number of operations required to make the array source equal to the array target. If it is not possible to make the two arrays equal, report -1.
Example: Suppose n = 4, source = [4, 3, 1, 3], and target = [6, 2, 3, 0]. It is optimal to choose the subarray [3, 1] first, resulting in source = [4, 4, 0, 3]. Next, choose [0, 3] to get source = [4, 4, 1, 2]. Then, choose the entire array to make source = [5, 3, 2, 1]. Finally, choose [5, 1] to obtain source = [6, 2, 3, 0]. Thus, the two arrays can be made equal in at most 4 operations. Hence, the answer is 4.
Question Link: https://www.chegg.com/homework-help/questions-and-answers/question-2-array-source-n-integers-single-operation-choose-even-length-subarray-alternatel-q127865023
Please Provide some hints to approach this problem.