Return maximum value of the integer at index k in array

user_8517295 0
Viewed 651

This question was asked during Microsoft interview for intern position, I have no idea how to even approach this.

Array has n positive integers, sum of all elements in the array is at most max_sum, absolute difference between any two consecutive elements in the array is at most 1. Return maximum value of the integer at index k in array.

Input : n = 3, max_sum = 7, k = 1
Output: 3
In this case let's say array is [2,3,2]

Input: n = 4, max_sum = 6, k = 2
output = 2
In this case let's say array is [1,1,2,1]
algorithm
2 Answers

This is a brute-force approach. A better solution would be to calculate the values, but I'll leave it to you do figure that out. This is your challenge to get the job, right?

Input: n = 7, max_sum = 34, k = 4

  1. Set all values to 0.

    //                    ↓ k
array = { 0, 0, 0, 0, 0, 0, 0 }, sum = 0

  2. Since we want maximum value at k, with lowest sum, just increment the value to 1.

    //                    ↓ k
array = { 0, 0, 0, 0, 1, 0, 0 }, sum = 1 (+1)

  3. Since consecutive elements must be at most 1 apart, when we increment value at k again, we need to increment the neighboring values too.

    //                    ↓ k
array = { 0, 0, 0, 1, 2, 1, 0 }, sum = 4 (+3)

  4. Repeat, repeatedly.

    //                    ↓ k
array = { 0, 0, 1, 2, 3, 2, 1 }, sum = 9 (+5)

array = { 0, 1, 2, 3, 4, 3, 2 }, sum = 15 (+6)

array = { 1, 2, 3, 4, 5, 4, 3 }, sum = 22 (+7)

array = { 2, 3, 4, 5, 6, 5, 4 }, sum = 29 (+7)

  5. We can't repeat again, because we'd get sum = 29 + 7 = 36 if we did, and that would exceed max_sum = 34.

Result: Max value at k is 6.

There are many ways to distribute the remaining 5 points, to get the exact sum, but showing a solution with the exact sum isn't the goal, so we don't need to do anything about the 5 extra points.

user_52211490

Let's define a as average array value:

a = max_sum / n

Let's find the maximum for k = 0:

max(0) = a + n/2

In this case, all other values of array would decrease, so the last value will be

a - n/2

for k = 1 we can see that maximum will not exceed max(0)-1, so

max(1) = a + n/2 - 1

and so on until k = n/2. for k > n/2 the max value will increase up to a + n/2 at k = n-1, so we have "V"-like curve with minimum at k=n/2, equal to a.

The only thing rest is to properly process border conditions, odd or even n and so on. I hope you got the idea.

user_27027810
Related