13

I got asked this question on a interview for Google a couple of weeks ago, I didn't quite get the answer and I was wondering if anyone here could help me out.

You have an array with n elements. The elements are either 0 or 1. You want to split the array into k contiguous subarrays. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k << n. After you split the array into k subarrays. One element of each subarray will be randomly selected.

Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum.

You can assume that n is a power of 2.

Example:

Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6

Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.4333333 

Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.83333333
16
  • 6
    Wow I hope the interviewer explained it better than that, otherwise I never want to interview for Google. Nov 18, 2011 at 21:40
  • It was actually pretty close to that.
    – John Smith
    Nov 18, 2011 at 21:43
  • Yeah I think that is the optimal partition.
    – John Smith
    Nov 18, 2011 at 21:57
  • 1
    @hatchet: ah, that's more interesting (and a horrible abuse of the term "partition" to my ears as a mathematician). Nov 18, 2011 at 22:26
  • 1
    what about [0,0],[1,1],[0,0],[1,1],[0,1],[1,0] - it gives a 0+1+0+1+0.5+0.5 maybe we need to also multiply the percentage by the number of members in the group?
    – asafrob
    Aug 3, 2013 at 19:29

8 Answers 8

6

I think we can solve this problem using dynamic programming.

Basically, we have:

f(i,j) is defined as the maximum sum of all expected values chosen from an array of size i and split into j subarrays. Therefore the solution should be f(n,k).

The recursive equation is:

f(i,j) = f(i-x,j-1) + sum(i-x+1,i)/x where (n/2k) <= x <= (3n/2k)
3
  • I don't think that works. Where are you using the input array in your recurrence? Have you tried it for some small examples?
    – Mikola
    Nov 19, 2011 at 6:05
  • @Mikola: Just read the problem again and found that we cannot sort the array...=0= sorry...
    – derekhh
    Nov 19, 2011 at 9:46
  • Just to add that this DP approach's complexity is also O(K*N^2)
    – KFL
    Jun 29, 2012 at 6:19
3

I don't know if this is still an open question or not, but it seems like the OP has managed to add enough clarifications that this should be straightforward to solve. At any rate, if I am understanding what you are saying this seems like a fair thing to ask in an interview environment for a software development position.

Here is the basic O(n^2 * k) solution, which should be adequate for small k (as the interviewer specified):

def best_val(arr, K):
  n = len(arr)
  psum = [ 0.0 ]
  for x in arr:
    psum.append(psum[-1] + x)
  tab = [ -100000 for i in range(n) ]
  tab.append(0)
  for k in range(K):
    for s in range(n - (k+1) * ceil(n/(2*K))):
      terms = range(s + ceil(n/(2*K)), min(s + floor((3*n)/(2*K)) + 1, n+1))
      tab[s] = max( [ (psum[t] - psum[s]) / (t - s) + tab[t] for t in terms ])
  return tab[0]

I used the numpy ceil/floor functions but you basically get the idea. The only `tricks' in this version is that it does windowing to reduce the memory overhead to just O(n) instead of O(n * k), and that it precalculates the partial sums to make computing the expected value for a box a constant time operation (thus saving a factor of O(n) from the inner loop).

4
  • That actually looks right. But I am a bit confused with your code. Could you (or someone else that also understands this code)please further explain what is going on inside the for loop?
    – John Smith
    Nov 19, 2011 at 21:27
  • Also how would you go about getting the actual places where to split the array instead of the best expected val
    – John Smith
    Nov 19, 2011 at 21:46
  • @JohnSmith: Right after iteration k, tab[i] is the maximum sum of expected values of arr[i:n] partitioned into k+1 contiguous subarrays. You could maintain another array sp that stores the splitting positions that yield the value in tab[i]: simply replace the max() call with a loop that records not only the maximum value but also the best splitting point t, and set sp[s]=sp[t]+[t].
    – han
    Nov 21, 2011 at 18:33
  • @Mikola could you provide an explanation in simpler form? pseudo code perhaps?
    – Nitin Garg
    Nov 25, 2011 at 10:13
1

I don't know if anyone is still interested to see the solution for this problem. Just stumbled upon this question half an hour ago and thought of posting my solution(Java). The complexity for this is O(n*K^log10). The proof is a little convoluted so I would rather provide runtime numbers:

n k time(ms)
48 4 25
48 8 265
24 4 20
24 8 33
96 4 51
192 4 143
192 8 343919

The solution is the same old recursive one where given an array, choose the first partition of size ceil(n/2k) and find the best solution recursively for the rest with number of partitions = k -1, then take ceil(n/2k) + 1 and so on.

Code:

public class PartitionOptimization {
public static void main(String[] args) {
    PartitionOptimization p = new PartitionOptimization();
    int[] input = { 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0};
    int splitNum = 3;
    int lowerLim = (int) Math.ceil(input.length / (2.0 * splitNum));        
    int upperLim = (int) Math.floor((3.0 * input.length) / (2.0 * splitNum));
    System.out.println(input.length + " " + lowerLim + " " + upperLim + " " +
            splitNum);
    Date currDate = new Date();
    System.out.println(currDate);       
    System.out.println(p.getMaxPartExpt(input, lowerLim, upperLim,
            splitNum, 0));
    System.out.println(new Date().getTime() - currDate.getTime());
}

public double getMaxPartExpt(int[] input, int lowerLim, int upperLim,
        int splitNum, int startIndex) {
    if (splitNum <= 1 && startIndex<=(input.length -lowerLim+1)){
        double expt = findExpectation(input, startIndex, input.length-1);           
        return expt;
    }
    if (!((input.length - startIndex) / lowerLim >= splitNum))
        return -1;
    double maxExpt = 0;
    double curMax = 0;
    int bestI=0;
    for (int i = startIndex + lowerLim - 1; i < Math.min(startIndex
            + upperLim, input.length); i++) {
        double curExpect = findExpectation(input, startIndex, i);           
        double splitExpect = getMaxPartExpt(input, lowerLim, upperLim,
                splitNum - 1, i + 1);
        if (splitExpect>=0 && (curExpect + splitExpect > maxExpt)){
            bestI = i;
            curMax = curExpect;
            maxExpt = curExpect + splitExpect;
        }
    }
    return maxExpt;
}

public double findExpectation(int[] input, int startIndex, int endIndex) {
    double expectation = 0;
    for (int i = startIndex; i <= endIndex; i++) {
        expectation = expectation + input[i];
    }
    expectation = (expectation / (endIndex - startIndex + 1));
    return expectation;
}
 }
0
0

Not sure I understand, the algorithm is to split the array in groups, right? The maximum value the sum can have is the number of ones. So split the array in "n" groups of 1 element each and the addition will be the maximum value possible. But it must be something else and I did not understand the problem, that seems too silly.

7
  • "You want to split the array into k partitions." Nov 18, 2011 at 21:41
  • 1
    there are constraints on the min and max number of elements in each partition. The idea is to partition in such a way that your partitions capture the natural clustering of 1's and 0's, so you end up with lots of partitions containing mostly 1's and a few partitions containing the bulk of the 0's. Then when a single value is randomly selected from each partition, the sum is maximized. Nov 18, 2011 at 21:43
  • The original message has been edited. My response is valid within the constraints of the original message, as far as I can see.
    – DPM
    Nov 18, 2011 at 21:47
  • @hatchet: that doesn't necessarily maximize the sum. actually you don't want to cluster the 1's as they don't increase the expected value. Nov 18, 2011 at 21:49
  • 1
    What I meant is you want as many partitions as possible with a higher occurrence of ones than the average, and a few large partitions that group the 0's. Nov 18, 2011 at 21:57
0

I think this can be solved with dynamic programming. At each possible split location, get the maximum sum if you split at that location and if you don't split at that point. A recursive function and a table to store history might be useful.

sum_i = max{ NumOnesNewPart/NumZerosNewPart * sum(NewPart) + sum(A_i+1, A_end),
                sum(A_0,A_i+1) + sum(A_i+1, A_end)
           }

This might lead to something...

2
  • DP is one solution, but the table is more complicated than what you've described.
    – Per
    Nov 18, 2011 at 22:06
  • That recurrence doesn't seem right to me. Could you try it out on some small examples?
    – Mikola
    Nov 19, 2011 at 6:06
0

I think its a bad interview question, but it is also an easy problem to solve.

Every integer contributes to the expected value with weight 1/s where s is the size of the set where it has been placed. Therefore, if you guess the sizes of the sets in your partition, you just need to fill the sets with ones starting from the smallest set, and then fill the remaining largest set with zeroes.

You can easily see then that if you have a partition, filled as above, where the sizes of the sets are S_1, ..., S_k and you do a transformation where you remove one item from set S_i and move it to set S_i+1, you have the following cases:

  • Both S_i and S_i+1 were filled with ones; then the expected value does not change
  • Both them were filled with zeroes; then the expected value does not change
  • S_i contained both 1's and 0's and S_i+1 contains only zeroes; moving 0 to S_i+1 increases the expected value because the expected value of S_i increases
  • S_i contained 1's and S_i+1 contains both 1's and 0's; moving 1 to S_i+1 increases the expected value because the expected value of S_i+1 increases and S_i remains intact

In all these cases, you can shift an element from S_i to S_i+1, maintaining the filling rule of filling smallest sets with 1's, so that the expected value increases. This leads to the simple algorithm:

  1. Create a partitioning where there is a maximal number of maximum-size arrays and maximal number of minimum-size arrays
  2. Fill the arrays starting from smallest one with 1's
  3. Fill the remaining slots with 0's
4
  • 1
    I am not sure I understand the algorithm. Can you clarify your use of the Words partition, Set and Array. Because at one point you talk about sets inside a partition and then you mention arrays. Thanks for the help!
    – John Smith
    Nov 19, 2011 at 2:27
  • @antti.huima i think you have missed the case when both S_i and S_i+1 have both 1's and 0's .
    – Nitin Garg
    Nov 25, 2011 at 10:12
  • @Nitin there isn't such a case because the partitions were filled starting with ones in left-to-right order. If S_i has a 0 then 1's have run out and S_i+1 can't have 1's any more. Nov 27, 2011 at 6:31
  • Then may be you are partitioning the array into subsets, and not contiguous subarrays as the OP has specified.
    – Nitin Garg
    Nov 28, 2011 at 14:43
0

How about a recursive function:

int BestValue(Array A, int numSplits)
// Returns the best value that would be obtained by splitting 
// into numSplits partitions.

This in turn uses a helper:

// The additional argument is an array of the valid split sizes which 
// is the same for each call.
int BestValueHelper(Array A, int numSplits, Array splitSizes)
{
    int result = 0;
    for splitSize in splitSizes
        int splitResult = ExpectedValue(A, 0, splitSize) + 
                          BestValueHelper(A+splitSize, numSplits-1, splitSizes);
        if splitResult > result
            result = splitResult;
}

ExpectedValue(Array A, int l, int m) computes the expected value of a split of A that goes from l to m i.e. (A[l] + A[l+1] + ... A[m]) / (m-l+1).

BestValue calls BestValueHelper after computing the array of valid split sizes between ceil(n/2k) and floor(3n/2k).

I have omitted error handling and some end conditions but those should not be too difficult to add.

0

Let

  • a[] = given array of length n
  • from = inclusive index of array a
  • k = number of required splits
  • minSize = minimum size of a split
  • maxSize = maximum size of a split
  • d = maxSize - minSize
  • expectation(a, from, to) = average of all element of array a from "from" to "to"

    Optimal(a[], from, k) = MAX[ for(j>=minSize-1 to <=maxSize-1) { expectation(a, from, from+j) + Optimal(a, j+1, k-1)} ]
    

Runtime (assuming memoization or dp) = O(n*k*d)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.