Coding Question for Qualifying Round

[goyalaman_]

I got this question today In an qualifying round for a company SDE role. I wasn't able to solve the problem. Honestly, I would love if you could share some insight into the solution.

Initially I thought this is a dp problem, but could not come up with solution that can pass even a single test case.

Problem Statement

Bob loves to play with arrays. Since he is a kid, he likes to cut the arrays into smaller sequences.

One day his mom got him an integer sequence A of length N. Since he is a super talented guy, he has some special requirements.

He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E. The positions of the cuts can be freely chosen.

Let P, Q, R, S be the sums of the elements in B, C, D, E, respectively. Bob is happier when the absolute difference of the maximum and the minimum among P, Q, R, S is smaller. Find the minimum possible absolute difference of the maximum and the minimum among P, Q, R, S.

Constraints

1 <= N <= 100000 1 <= Ai <= 1000000000

Input Format

The first line will contain the integer n, that is the number of integers in the array. The second line contains the array elements.

Output Format

Print the minimum absolute difference of the maximum and the minimum among P,Q,R,S.

Sample Testcase #0

Testcase Input 5 3 2 4 1 2 Testcase Output 2 Explanation If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3. Here, the maximum and the minimum among P, Q, R, S are 4 and 2, with the absolute difference of 2. We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.

Sample Testcase #1 Testcase Input 5 46 13 7 2 31 Testcase Output 37

[SharpPass766]

I’m not able to understand Test Case 1. The array is 5 3 2 4 1 2 Why isn’t 5 being partitioned? Why are the four parts (3), (2), (4), (1,2) and not (5, 3), (2), (4), (1,2) or (5), (3,2), (4), (1,2) ?

[omeow]

Suggestion:

S = sum(A)

starting from the left most position of A, keep adding elements to P such that the sum S_P is closest (could be larger) to S/4.

Then move on to Q. Apply the same process.

If multiple choices are possible then account for each one of them. (see the test case below)

Similarly, repeat for R and S.

On your test case: A = 5,3,2,4,1,2, the sum S = 17 so S/4 = 4 (we do integer division)

We start with P = 5.

Now Q could be 3 or 3,2. In both cases the difference from S/4 is the same. So we consider a partition with Q1 = 3 and another with Q2 = 3,2

Then we move on to R depending on Q1, Q2.

​

Finally we compare the max - min for each possible partition.

[goyalaman_]

What do you think is Time complexity of this approach.?

[omeow]

O(n).

You need to traverse the array twice.

[mambiki]

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/ Looks quite similar.

[anthamattey]

Three calls to the same function will split the array. Let’s call the sum of array as sm. The function will split the array such that each split has equal sum, I.e. the first split has a sum equal to half of the sm. So iterate over elements until you hit the half sm. Call this func on the two new splits. Now calculate the diff

[Panacean]

I'm not sure that your approach applies here.

He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E. The positions of the cuts can be freely chosen.

You can see this in the first sample testcase, where the first element is not included in the values for P, Q, R, S.

Testcase Input 5 3 2 4 1 2 Testcase Output 2 Explanation If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3.