Google Combinatorial Optimization面试问题

Question

几周前,我在谷歌的一次采访中被问到这个问题,我没有得到答案,我想知道这里是否有人可以帮助我.

你有一个包含n个元素的数组.元素为0或1.您希望将数组拆分为k 个连续的子数组.每个子阵列的大小可以在ceil(n/2k)和floor(3n/2k)之间变化.你可以假设k << n.将数组拆分为k个子数组后.将随机选择每个子阵列的一个元素.

设计一种算法,用于最大化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

我不知道这是否仍然是一个悬而未决的问题，但似乎OP已经设法添加了足够的澄清，这应该很容易解决。无论如何，如果我理解你在说什么，那么在面试环境中询问软件开发职位似乎是一件公平的事情。

这是基本的 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)，并且它预先计算部分和以计算一个框的期望值恒定时间操作（从而从内部循环中节省 O(n) 因子）。