Задача интервью с Google Combinatorial Optimization

Question

Мне задали этот вопрос в интервью для Google пару недель назад, я не совсем получил ответ, и мне было интересно, сможет ли кто-нибудь здесь помочь мне.

У вас есть массив с n элементами. Элементы либо 0, либо 1. Вы хотите разбить массив на k непрерывных подмассивов . Размер каждого подмассива может варьироваться от потолка (n / 2k) до пола (3n / 2k). Вы можете предположить, что k << n. После того, как вы разбили массив на k подмассивов. Один элемент каждого подмассива будет выбран случайным образом. </p>

Разработать алгоритм максимизации суммы случайно выбранных элементов из k подмассивов. По сути, это означает, что мы хотим разделить массив таким образом, чтобы сумма всех ожидаемых значений для элементов, выбранных из каждого подмассива, была максимальной.

Можно предположить, что n является степенью 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

Answer 1

Я думаю, что мы можем решить эту проблему с помощью динамического программирования.

В основном имеем:

f (i, j) определяется как максимальная сумма всех ожидаемых значений, выбранных из массива размером i и разбитого на j подмассивов. Поэтому решение должно быть f (n, k) .

Рекурсивное уравнение:

f(i,j) = f(i-x,j-1) + sum(i-x+1,i)/x where (n/2k) <= x <= (3n/2k)

Answer 2

Я не знаю, остается ли этот вопрос открытым или нет, но кажется, что ОП удалось добавить достаточно разъяснений, чтобы их было легко решить.Во всяком случае, если я понимаю, что вы говорите, это справедливо спросить в среде интервью о позиции разработки программного обеспечения.

Вот базовое решение O (n ^ 2 * k),что должно быть достаточно для малого k (как указал интервьюер):

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]

Я использовал функции numpy ceil / floor, но вы в основном поняли идею.Единственная «хитрость» в этой версии заключается в том, что она выполняет управление окнами, чтобы уменьшить накладные расходы памяти до O (n) вместо O (n * k), и что она предварительно вычисляет частичные суммы, чтобы вычислить ожидаемое значение для блока aработа в постоянном времени (таким образом, сохраняя коэффициент O (n) из внутреннего цикла).

Answer 3

Не знаю, заинтересован ли кто-нибудь еще в поиске решения этой проблемы. Просто наткнулся на этот вопрос полчаса назад и подумал о публикации моего решения (Java). Сложность для этого O (n * K ^ log10). Доказательство немного запутанно, поэтому я бы предпочел привести числа времени выполнения:

n k время (мс)
48 4 25
48 8 265
24 4 20
24 8 33
96 4 51
192 4 143
192 8 343919

Решение - то же самое старое рекурсивное, где дан массив, выберите первый раздел размера ceil (n / 2k) и найдите рекурсивное решение для остальных с числом разделов = k -1, затем возьмите ceil ( n / 2k) + 1 и т. д.

Код:

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;
}
 }

Answer 4

Let

• a [] = заданный массив длины n
• from = включающий индекс массива a
• k = количество требуемых разбиений
• minSize = минимальный размер разделения
• maxSize = максимальный размер разделения
• d = maxSize - minSize

• ожидание (a, от, до) = среднее значение по всему элементу массива a от "от" до "до"

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

Время выполнения (при условии, что запоминание или dp) = O (n * k * d)

Answer 5

Как насчет рекурсивной функции:

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

Это, в свою очередь, использует помощника:

// 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) вычисляет ожидаемое значение разбиения A, которое идет от l до m, т.е. (A [l] + A [l + 1] + ... A [m] ) / (м-л + 1).

BestValue вызывает BestValueHelper после вычисления массива допустимых размеров разделения между ceil (n / 2k) и floor (3n / 2k).

Я пропустил обработку ошибок и некоторые конечные условия, но их не должно быть слишком сложно добавить.

Answer 6

Я думаю, что это плохой вопрос для собеседования, но это также легко решаемая проблема.

Каждое целое число вносит вклад в ожидаемое значение с весом 1 / с, где s - размер множества, в котором оно было размещено. Поэтому, если вы угадаете размеры наборов в вашем разделе, вам просто нужно заполнить наборы, начиная с наименьшего набора, а затем заполнить оставшийся наибольший набор нулями.

Вы можете легко увидеть, что если у вас есть раздел, заполненный, как указано выше, где размеры наборов равны S_1, ..., S_k, и вы выполняете преобразование, при котором вы удаляете один элемент из набора S_i и перемещаете его в установите S_i + 1, у вас есть следующие случаи:

• И S_i, и S_i + 1 были заполнены единицами; тогда ожидаемое значение не меняется
• Оба они были заполнены нулями; тогда ожидаемое значение не меняется
• S_i содержит как 1, так и 0, а S_i + 1 содержит только нули; перемещение 0 к S_i + 1 увеличивает ожидаемое значение, поскольку ожидаемое значение S_i увеличивается
• S_i содержит 1, а S_i + 1 содержит 1 и 0; перемещение 1 в S_i + 1 увеличивает ожидаемое значение, поскольку ожидаемое значение S_i + 1 увеличивается, а S_i остается неизменным

Во всех этих случаях вы можете переместить элемент с S_i на S_i + 1, поддерживая правило заполнения, заключающееся в заполнении наименьших наборов единицами, так что ожидаемое значение увеличивается. Это приводит к простому алгоритму:

1. Создать разделение, в котором есть максимальное количество массивов максимального размера и максимальное количество массивов минимального размера
2. Заполните массивы, начиная с самого маленького, 1
3. Заполните оставшиеся слоты нулями

Answer 7

Я думаю, что это можно решить с помощью динамического программирования.В каждом возможном месте разделения получите максимальную сумму, если вы разделите в этом месте и если вы не разделите в этой точке.Может быть полезна рекурсивная функция и таблица для хранения истории.

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)
           }

Это может привести к чему-то ...

Answer 8

Не уверен, что понимаю, алгоритм состоит в том, чтобы разбить массив на группы, верно?Максимальное значение, которое может иметь сумма, равно числу единиц.Поэтому разбейте массив на «n» групп по 1 элементу в каждой, и сложение будет максимально возможным значением.Но это должно быть что-то еще, и я не понял проблему, которая кажется слишком глупой.