问个google面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个google面试题

问个google面试题# JobHunting - 待字闺中

B*12011-10-21 07:10

1 楼

careercup上面看的
Partition a set of numbers into two such that difference between their sum
is minimum, and both sets have equal number of elements.
For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff = 17
-13=4.
Does greedy work here? First sorting, and then picking smallest and largest
to fall in set 1, and picking 2nd smallest and 2nd largest to fall in set 2.
I was asked to prove which I failed :(

g*i2011-10-21 07:10

2 楼

partition problem变种,应该可以用subset problem的dp solution来做,wiki上说的.
greedy方法的approximation factor是4/3,很接近了.
楼主我觉得你老是钻研这种难题没啥必要,面试这种题目出现的概率极低,出了面试官也
会引导你的.

B*12011-10-21 07:10

3 楼

没有研究，careercup上的google的怎么都这么难。

y*g2011-10-21 07:10

4 楼

careercup 估计是假题目吧
我觉得glassdoor好的多，

【在 B*******1 的大作中提到】

: 没有研究，careercup上的google的怎么都这么难。

B*12011-10-21 07:10

5 楼

是啊？而且看了这几个我贴的这么难的都是google india的。

D*e2011-10-21 07:10

6 楼

有人跟我说，随机置换两边的数（只要让结果变好就换）是最快的

c*p2011-10-21 07:10

7 楼

greedy，容易达到local optimal.

【在 D*******e 的大作中提到】

: 有人跟我说，随机置换两边的数（只要让结果变好就换）是最快的

i*d2011-10-21 07:10

8 楼

这应该是一个dp题。
等价于在数组中找出 len/2个数，使得和在不大于 sum/2时，最大化.

c*x2011-10-21 07:10

9 楼

必然是假的
子集和(NPC) => 二等分 => 二等分且两边元素个数相等 => minimum difference is 0
in this problem

17
largest
2.

【在 B*******1 的大作中提到】

: careercup上面看的
: Partition a set of numbers into two such that difference between their sum
: is minimum, and both sets have equal number of elements.
: For example: {1, 4, 9, 16} is partitioned as {1,16} and {4,9} with diff = 17
: -13=4.
: Does greedy work here? First sorting, and then picking smallest and largest
: to fall in set 1, and picking 2nd smallest and 2nd largest to fall in set 2.
: I was asked to prove which I failed :(