ibm oa - How would you even solve this? Looks like a DP problem, can't find it on leetcode though
Round 1
Questions:
Give an array of integers of length n, arr,
and two integers l and r, find another array brr, such that:
- l <= brr[i] <= r
- brr[i] - arr[i] < brr[i+1] - arr[i+1], for every i less than n - 1
- brr[i] <= brr[i+1] for every i less than n - 1
Among all such arrays, return the lexicographically smallest one.
If there is not an array that satisfies the conditions,
then return an array with the single element -1.
Example
arr = [1, 2, 1, 2], l = 1, r = 10
The array [1, 3, 3, 5] satisfies given conditions.
- Each element belongs in the range [1, 10]
- Construct an array crr where crr[i] = brr[i] - arr[i], crr = [0, 1, 2, 3]
- The array brr is non-decreasing
brr[i] - arr[i] for each element [0, 1, 2, 3]
1 - 1 = 0
3 - 2 = 1
3 - 1 = 2
5 - 2 = 3
Note that all brr[i] >= arr[i] as well.
There is not a lexicographically smaller array than [1, 3, 3, 5]
that satisfies the conditions.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.