phone interview question - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

phone interview question

phone interview question# JobHunting - 待字闺中

b*e2013-02-27 08:02

1 楼

give a polynomial complexity algorithm to find whether a set of intergers
can be evenly divided into 3 subsets. that is: if sum of the set is A,
decide whether it can be divided into 3 subsets, each with sum = A/3.

p*22013-02-27 08:02

2 楼

DFS

f*e2013-02-27 08:02

3 楼

2D dp

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

: give a polynomial complexity algorithm to find whether a set of intergers
: can be evenly divided into 3 subsets. that is: if sum of the set is A,
: decide whether it can be divided into 3 subsets, each with sum = A/3.

b*e2013-02-27 08:02

4 楼

more details? I can only think of dynamical programming with n * A^3.

【在 p*****2 的大作中提到】

: DFS

p*22013-02-27 08:02

5 楼

give a polynomial complexity algorithm

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

: 2D dp

b*e2013-02-27 08:02

6 楼

more details? I can only think a 4-D DP (i, a1, a2, a3)

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

: 2D dp

p*22013-02-27 08:02

7 楼

DFS先找到1/3，再继续找下一个1/3

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

: more details? I can only think a 4-D DP (i, a1, a2, a3)

b*e2013-02-27 08:02

8 楼

how to find the first 1/3?

【在 p*****2 的大作中提到】

:
: DFS先找到1/3，再继续找下一个1/3

f*e2013-02-27 08:02

9 楼

以前讨论过的,tninja给的一个答案。

【在 p*****2 的大作中提到】

:
: DFS先找到1/3，再继续找下一个1/3

p*22013-02-27 08:02

10 楼

不好意思。是我理解错了。那就DP吧。

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

: 以前讨论过的,tninja给的一个答案。

f*e2013-02-27 08:02

11 楼

http://www.mitbbs.com/article_t/JobHunting/32303331.html

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

: 以前讨论过的,tninja给的一个答案。

r*n2013-02-27 08:02

12 楼

类似http://people.csail.mit.edu/bdean/6.046/dp/ 里面的第7题balanced partition
假设A是3的倍数，n是数列长度
vector DP[0,1,...,A][0,1,...,n-1]
every time you consider a new integer, fill in one column of DP，the
difference between this problem and the balanced partition problem is that
DP[s][i] is now a vector contains all indices leading to subset sum being
equal to s。
when you back track starting at DP[A/3][n-1], you can easily get all
feasible subsets. Then it's not difficult to determine whether three of them
form the original array.
As such, this may lead to exponential running time when all integers are
equal. To guarantee polynomial time, for each feasible subset, you repeat
the above procedure for the remaining integers that are not in this set.

h*i2013-02-27 08:02

13 楼

最多pseudo polynomial，用DP。本身是一个sum of subset问题，NP complete.

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

p*22013-02-27 08:02

14 楼

them
感觉写起代码来也不容易呀。

【在 r*********n 的大作中提到】

: 类似http://people.csail.mit.edu/bdean/6.046/dp/ 里面的第7题balanced partition
: 假设A是3的倍数，n是数列长度
: vector DP[0,1,...,A][0,1,...,n-1]
: every time you consider a new integer, fill in one column of DP，the
: difference between this problem and the balanced partition problem is that
: DP[s][i] is now a vector contains all indices leading to subset sum being
: equal to s。
: when you back track starting at DP[A/3][n-1], you can easily get all
: feasible subsets. Then it's not difficult to determine whether three of them
: form the original array.

b*u2013-02-27 08:02

15 楼

恩，感觉就是leetcode上combination sum的升级版

b*e2013-02-27 08:02

16 楼

my solution: 4d np.
recursive function.
Exist(i, a1, a2, a3) = { Exist(i-1, a1-xi, a2, a3) ||
Exist(i-1, a1, a2-xi, a3) ||
Exist(i-1, a1, a2, a3-xi) }
where xi is the ith integer.
a1, a2, a3 are the sum of three subsets in the set.
start from i = 1, a1, a2, a3 = 1
stop at i = n, a1 = a2 = a3 = sum/3.
complexity n * (sum/3)^3.
Any problem with the above DP?