由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 一道面试题:三等分数组
相关主题
一个面试题请教一道google的面试题
问几道算法题一道列举所有和相等的pairs的面试题.
贡献个面试题,目前狗狗都没找到.....大家看看这几道google面试题怎么做?
简单问题2问道面试题
这题有点意思 给一个数组, 找最大的整数m, 使得数组里比m大的或相等 的值的树木大于等于m(线性)请教一道面试题
把一个数组划分成尽可能相等的k份这道算法题follow-up让所有人都跪了,你会做吗?
问道题一个有关数组的面试题 (难度较高)
请教一道面试题[合集] 面试题求解
相关话题的讨论汇总
话题: exist话题: 10话题: false话题: a1话题: a2
进入JobHunting版参与讨论
1 (共1页)
d****r
发帖数: 80
1
一道面试题:
给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。
不能分的时候返回空值。能分的时候给出一个解就行。
我只能想到三进制,有没有更优化的方法?
c********t
发帖数: 5706
2
是整数吧?要求每组的整数个数相等吗?

【在 d****r 的大作中提到】
: 一道面试题:
: 给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。
: 不能分的时候返回空值。能分的时候给出一个解就行。
: 我只能想到三进制,有没有更优化的方法?

d****r
发帖数: 80
3
对,整数。有何高见?

【在 c********t 的大作中提到】
: 是整数吧?要求每组的整数个数相等吗?
j*****y
发帖数: 1071
4
用三进制 brute force ?

【在 d****r 的大作中提到】
: 对,整数。有何高见?
d****r
发帖数: 80
5
我是那么想的。三进制达不到要求。要求优化解。

【在 j*****y 的大作中提到】
: 用三进制 brute force ?
d****r
发帖数: 80
6
不要求个数相等。

【在 c********t 的大作中提到】
: 是整数吧?要求每组的整数个数相等吗?
j*****y
发帖数: 1071
7
二等分数组是可以用 dp的,
三等分的话,可不可以证明:
如果可以三等分的话,如果拿出一个子集的和是 1/3的和,那么剩下的一定可以二等分?
这个可以证明是正确的话,那么就是两次 dp 了

【在 d****r 的大作中提到】
: 一道面试题:
: 给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。
: 不能分的时候返回空值。能分的时候给出一个解就行。
: 我只能想到三进制,有没有更优化的方法?

j*****y
发帖数: 1071
8
这个可以证明是正确的,那么就是两次 dp
第一次 dp 找出和是 1/3 的总和的子集
第二次dp 等分剩下的集合

分?

【在 j*****y 的大作中提到】
: 二等分数组是可以用 dp的,
: 三等分的话,可不可以证明:
: 如果可以三等分的话,如果拿出一个子集的和是 1/3的和,那么剩下的一定可以二等分?
: 这个可以证明是正确的话,那么就是两次 dp 了

z*******8
发帖数: 30
9
我觉得这个思路挺好,有点递归的意思,不过条件有点强吧。
比如
1,2,3,
0,0,5,
0,0,7
这个数组就是不能三分的。

分?

【在 j*****y 的大作中提到】
: 二等分数组是可以用 dp的,
: 三等分的话,可不可以证明:
: 如果可以三等分的话,如果拿出一个子集的和是 1/3的和,那么剩下的一定可以二等分?
: 这个可以证明是正确的话,那么就是两次 dp 了

j*****y
发帖数: 1071
10
不能三分的话两次 dp 也能 detect 出来

【在 z*******8 的大作中提到】
: 我觉得这个思路挺好,有点递归的意思,不过条件有点强吧。
: 比如
: 1,2,3,
: 0,0,5,
: 0,0,7
: 这个数组就是不能三分的。
:
: 分?

相关主题
把一个数组划分成尽可能相等的k份请教一道google的面试题
问道题一道列举所有和相等的pairs的面试题.
请教一道面试题大家看看这几道google面试题怎么做?
进入JobHunting版参与讨论
c********t
发帖数: 5706
11
应该不是正确的。1,1,3,4,6
dp 两次也不一定可以 1,1,2,3,4,4 如果第一次拿走 1,1,3,以后将无解啊

【在 j*****y 的大作中提到】
: 这个可以证明是正确的,那么就是两次 dp
: 第一次 dp 找出和是 1/3 的总和的子集
: 第二次dp 等分剩下的集合
:
: 分?

j*****y
发帖数: 1071
12
哈哈,我刚才大脑过了一遍,感觉是对的,看来是错的 :)

【在 c********t 的大作中提到】
: 应该不是正确的。1,1,3,4,6
: dp 两次也不一定可以 1,1,2,3,4,4 如果第一次拿走 1,1,3,以后将无解啊

c********t
发帖数: 5706
13
用dp找出=1/3*sum 的所有解,然后对每一组都取剩下的,试试能不能用dp 2等分?
是不是太复杂了?

【在 j*****y 的大作中提到】
: 哈哈,我刚才大脑过了一遍,感觉是对的,看来是错的 :)
j*****y
发帖数: 1071
14
这个所有解,感觉太复杂了:)

【在 c********t 的大作中提到】
: 用dp找出=1/3*sum 的所有解,然后对每一组都取剩下的,试试能不能用dp 2等分?
: 是不是太复杂了?

f*****e
发帖数: 2992
15
一个DP就行,然后就看所有解中是否有两个不相交就行。

【在 c********t 的大作中提到】
: 用dp找出=1/3*sum 的所有解,然后对每一组都取剩下的,试试能不能用dp 2等分?
: 是不是太复杂了?

c********t
发帖数: 5706
16
嗯,同意

【在 f*****e 的大作中提到】
: 一个DP就行,然后就看所有解中是否有两个不相交就行。
d**********n
发帖数: 132
17
不可以,有反例

分?

【在 j*****y 的大作中提到】
: 二等分数组是可以用 dp的,
: 三等分的话,可不可以证明:
: 如果可以三等分的话,如果拿出一个子集的和是 1/3的和,那么剩下的一定可以二等分?
: 这个可以证明是正确的话,那么就是两次 dp 了

d**********n
发帖数: 132
18
请大牛明示,这道题的dp是找一个解吧?用一个二维数组来储存当前element可能生成
的和

【在 f*****e 的大作中提到】
: 一个DP就行,然后就看所有解中是否有两个不相交就行。
s********i
发帖数: 145
19
这道题不是经典的NP-COMPLETE的problem之一么...还解个啥?
t****a
发帖数: 1212
20
我把它当二维DP做了,clojure程序和结果如下
(def divide-3-sub
(memoize
(fn [s1 s2 [x & xs]]
(cond (and (zero? s1) (zero? s2)) ['() '() (cons x xs)]
(or (< s1 0) (< s2 0) (empty? xs)) nil
:else (if-let [d1 (divide-3-sub (- s1 x) s2 xs)]
(assoc d1 0 (cons x (first d1)))
(if-let [d2 (divide-3-sub s1 (- s2 x) xs)]
(assoc d2 1 (cons x (second d2)))
(if-let [d3 (divide-3-sub s1 s2 xs)]
(assoc d3 2 (cons x (last d3)))
nil)))))))
(defn divide-3 [x]
(let [s (apply + x)
s3 (int (/ s 3))]
(if (= s (* s3 3))
(divide-3-sub s3 s3 x)
nil)))
(divide-3 (take 12 (repeat 1))) ; [(1 1 1 1) (1 1 1 1) (1 1 1 1)]
(divide-3 (range 6)) ; [(0 1 4) (2 3) (5)]
(divide-3 (range 12)) ; [(0 1 2 3 7 9) (4 8 10) (5 6 11)]
(divide-3 (take 100 (repeatedly #(rand-int 20)))) ; [(19 19 5 19 3 3 7 4 2 4
18 5 16 9 4 16 7 3 12 9 3 19 2 6 13 5 0 3 0 9 3 7 12 8 17 1 7 9 17 1 0 0 0)
(17 18 17 12 19 4 9 18 5 17 3 14 19 16 7 7 1 8 3 14 4 10 19 15 4 15 17 13 1
) (16 15 10 19 6 17 11 15 18 18 14 8 17 11 17 9 19 6 5 2 2 11 7 11 19 15 5 3
)]
这个程序的计算复杂度为O(s*s*n),其中s为数组的总和,n为数组长度。
相关主题
问道面试题一个有关数组的面试题 (难度较高)
请教一道面试题[合集] 面试题求解
这道算法题follow-up让所有人都跪了,你会做吗?面试题
进入JobHunting版参与讨论
j*****y
发帖数: 1071
21
能把那个 optimal structure 写一下吗?
thanks.

【在 t****a 的大作中提到】
: 我把它当二维DP做了,clojure程序和结果如下
: (def divide-3-sub
: (memoize
: (fn [s1 s2 [x & xs]]
: (cond (and (zero? s1) (zero? s2)) ['() '() (cons x xs)]
: (or (< s1 0) (< s2 0) (empty? xs)) nil
: :else (if-let [d1 (divide-3-sub (- s1 x) s2 xs)]
: (assoc d1 0 (cons x (first d1)))
: (if-let [d2 (divide-3-sub s1 (- s2 x) xs)]
: (assoc d2 1 (cons x (second d2)))

t****a
发帖数: 1212
22
f(s1, s2, (x & xs)) = f(s1-x, s2, xs) or f(s1, s2-x, xs) or f(s1, s2, xs)
f(0, 0, (x & xs)) 时候成功
话说楼主的3进制是什么意思啊?
j*****y
发帖数: 1071
23
s1 是第一个 subset, s2 是第二个 subset ?
x 和 xs 是什么呢?

【在 t****a 的大作中提到】
: f(s1, s2, (x & xs)) = f(s1-x, s2, xs) or f(s1, s2-x, xs) or f(s1, s2, xs)
: f(0, 0, (x & xs)) 时候成功
: 话说楼主的3进制是什么意思啊?

t****a
发帖数: 1212
24
(x & xs)整体表示输入的数字序列。s1是该数字序列中需要分出来第一组的和和第二组
的和。本题s1=s2=1/3 * sum(x & xs)

【在 j*****y 的大作中提到】
: s1 是第一个 subset, s2 是第二个 subset ?
: x 和 xs 是什么呢?

w**********o
发帖数: 140
25
小弟抛块砖,希望大牛们点评下。
首先sort, 从大到小排列。
L: 100, 98, 97, 76, 50, 30, ...., 10, 9, 2,1
分3组, a, b, c. 挨个拿。
First time
a: 100
b: 98
c: 97
sum(a) = 100
sum(b) = 98
sum(c) = 97 最小, 把L里面最大的分给他
Second time
a: 100,
b: 98,
c: 97, 76
sum(a) =100
sum(b) = 98 最小, 把L里面最大的分给他
sum(c) =173
3rd
a: 100,
b: 98, 50,
c: 97, 76,
sum(a) =100 最小, 把L里面最大的分给他
sum(b) = 148
sum(c) = 173
3rd
a: 100, 30
b: 98, 50,
c: 97, 76,
以此类推, 全部分完。
这样3组的difference比较小,size基本一样的情况下。
算法:个人理解就和国内分蛋糕一样。
每人都拿一块, c拿最小的要说话了, 再给我一份。
c变最大, b说他也要,一次不行,两次,拿到他是最大的(最小的变最大的)。
接着a也不服气,直到大家找到平衡点(找到组合), 要么掀桌
子(return null)。
可用structure,: 2个heap, one min heap for 3(a,b,c), one max heap for list(
same thing as sorted list)。
====
回复楼上,估计不是测试DP问题,interviewer没那个闲工夫测试30mins吧。
t****a
发帖数: 1212
26
这个会挂掉的。因为解的个数在最糟糕情况下是个组合数。

【在 f*****e 的大作中提到】
: 一个DP就行,然后就看所有解中是否有两个不相交就行。
t****a
发帖数: 1212
27
这样的方法好像是贪婪,不知道能不能保证找到结果啊。我数学不好,有哪位朋友来证
明一下贪婪对不对么?

【在 w**********o 的大作中提到】
: 小弟抛块砖,希望大牛们点评下。
: 首先sort, 从大到小排列。
: L: 100, 98, 97, 76, 50, 30, ...., 10, 9, 2,1
: 分3组, a, b, c. 挨个拿。
: First time
: a: 100
: b: 98
: c: 97
: sum(a) = 100
: sum(b) = 98

w**********o
发帖数: 140
28
题目本身是NP, 所以应该没问题吧。
希望PeK能点评下。

【在 t****a 的大作中提到】
: 这样的方法好像是贪婪,不知道能不能保证找到结果啊。我数学不好,有哪位朋友来证
: 明一下贪婪对不对么?

d**********x
发帖数: 4083
29
http://poj.org/problem?id=1011
一个区别不大的问题,poj的这个只是组数不确定
如果没记错的话,没有多项式解法,只是暴力搜索,加上各种神奇的剪支。

【在 d****r 的大作中提到】
: 一道面试题:
: 给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。
: 不能分的时候返回空值。能分的时候给出一个解就行。
: 我只能想到三进制,有没有更优化的方法?

s********i
发帖数: 145
30

我都说了是NP-COMPLETE了,为什么大家都无视我呢... T_T

【在 d**********x 的大作中提到】
: http://poj.org/problem?id=1011
: 一个区别不大的问题,poj的这个只是组数不确定
: 如果没记错的话,没有多项式解法,只是暴力搜索,加上各种神奇的剪支。

相关主题
Google的一道面试题问几道算法题
问一道google面试题(from careercup)贡献个面试题,目前狗狗都没找到.....
一个面试题简单问题2
进入JobHunting版参与讨论
d**********x
发帖数: 4083
31
真没看见你那篇。。

【在 s********i 的大作中提到】
:
: 我都说了是NP-COMPLETE了,为什么大家都无视我呢... T_T

f*****e
发帖数: 2992
32
对NP-complete,你能搞个pseudopolynoimal算法,也很nb的。

【在 s********i 的大作中提到】
:
: 我都说了是NP-COMPLETE了,为什么大家都无视我呢... T_T

v*******e
发帖数: 326
33
既然是np complete 为啥还要考楼主算法和优化解?

【在 s********i 的大作中提到】
:
: 我都说了是NP-COMPLETE了,为什么大家都无视我呢... T_T

s****r
发帖数: 28
34
这个不就是相当于leetcode上的combination sum么?
target = total_sum/3
如果能找两个不相交的组合就可以了

【在 d****r 的大作中提到】
: 一道面试题:
: 给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。
: 不能分的时候返回空值。能分的时候给出一个解就行。
: 我只能想到三进制,有没有更优化的方法?

d**********x
发帖数: 4083
35
Once I was interviewed by fb and the interviewer told me the problem IS an
NP, but he still wanted to see how optimized algorithm I could give

【在 v*******e 的大作中提到】
: 既然是np complete 为啥还要考楼主算法和优化解?
d****r
发帖数: 80
36

穷举。N个数的话,用N位的三进制。从0扫到最大值。0,1,2对应三个组。我这个方法实
际上没什么用。

【在 t****a 的大作中提到】
: f(s1, s2, (x & xs)) = f(s1-x, s2, xs) or f(s1, s2-x, xs) or f(s1, s2, xs)
: f(0, 0, (x & xs)) 时候成功
: 话说楼主的3进制是什么意思啊?

b*******e
发帖数: 217
37
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?

【在 d****r 的大作中提到】
:
: 穷举。N个数的话,用N位的三进制。从0扫到最大值。0,1,2对应三个组。我这个方法实
: 际上没什么用。

c********t
发帖数: 5706
38
两个问题
1.如何保证同一个元素没有被a1,a2,a3重用
2.a3需要吗?如果能求出a1,a2就不用a3了吧。n * (sum/3)^2.

【在 b*******e 的大作中提到】
: 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.

f****s
发帖数: 74
39
背包问题也是npc啊,

【在 s********i 的大作中提到】
:
: 我都说了是NP-COMPLETE了,为什么大家都无视我呢... T_T

c********t
发帖数: 5706
40
肯定是不行的
试试用你的做法把 1 3 4 5 6 7分成两组

【在 w**********o 的大作中提到】
: 小弟抛块砖,希望大牛们点评下。
: 首先sort, 从大到小排列。
: L: 100, 98, 97, 76, 50, 30, ...., 10, 9, 2,1
: 分3组, a, b, c. 挨个拿。
: First time
: a: 100
: b: 98
: c: 97
: sum(a) = 100
: sum(b) = 98

相关主题
简单问题2问道题
这题有点意思 给一个数组, 找最大的整数m, 使得数组里比m大的或相等 的值的树木大于等于m(线性)请教一道面试题
把一个数组划分成尽可能相等的k份请教一道google的面试题
进入JobHunting版参与讨论
b*******e
发帖数: 217
41
for (2): you are right.
recursive fucntion:
exist(i, a1, a2) = { exist(i-1, a1-xi, a2) ||
exist(i-1, a1, a2-xi)}
starting form i = 1 a1 = 1, a2 =1
end at i = n and a1 = a2 = sum/3.
complexity: n * (sum/3)^2.
don't quite understand (1). any example?
when start froming i = 1 to i = n, the recursive structure ... should be
able to gurantee that xi will only be used for once?
my solution: 3d np.
c********t
发帖数: 5706
42
for 1) example 4,6.....
exist(1,10,10)= exist(0,4,10)|| exist(0,10,4);
did ur program put 4 in a1, a2 or both? how about 6?
for 1,3,4,6,1,9, how can you prevent the result to be 1,9| 1,3,6 | 4,6 (use
6 twice)

【在 b*******e 的大作中提到】
: for (2): you are right.
: recursive fucntion:
: exist(i, a1, a2) = { exist(i-1, a1-xi, a2) ||
: exist(i-1, a1, a2-xi)}
: starting form i = 1 a1 = 1, a2 =1
: end at i = n and a1 = a2 = sum/3.
: complexity: n * (sum/3)^2.
: don't quite understand (1). any example?
: when start froming i = 1 to i = n, the recursive structure ... should be
: able to gurantee that xi will only be used for once?

b*******e
发帖数: 217
43
for i == 0, only exist(0, 4, 0) and exist(0, 0, 4) = true. all other
comibinations for i == 0 including exist(0, 4, 10) = false and exist(0, 10,
4) = false, so exist(1, 10, 10) = false.
for i == 1, exist(1, 10, 0) = exist(0, 4, 0 ) || exist(0, 10, -6) = true ||
false. and exist(1, 0, 10) = exist(0, -6, 10) || exist(0, 0, 4) = false ||
true and exist(1, 4, 6) = exist(0, 4, 0) || exist(0, -2, 0) = true || false
and
exist (1, 6, 4) = exist(0, 0, 4) || exist(0, 6, -2) = true || false will be
true. All other combinations will be false.
for 1, 3, 4, 5, 1, 9, "6" participate in the selection only when i == 3. and
it will either stay with 3 and 1, or with 4 for exist(3, 10, 10).
exist(3, 10, 10) = exist(2, 4, 10) || exist(2, 10, 4) = exist(1, 0, 10) ||
exist(1, 4, 6) || exist(1, 6, .... = false.

use

【在 c********t 的大作中提到】
: for 1) example 4,6.....
: exist(1,10,10)= exist(0,4,10)|| exist(0,10,4);
: did ur program put 4 in a1, a2 or both? how about 6?
: for 1,3,4,6,1,9, how can you prevent the result to be 1,9| 1,3,6 | 4,6 (use
: 6 twice)

c********t
发帖数: 5706
44
I think it will cause the problem,if continuing, later 4 might be used in
both a1 and a2.
let me simplify my second example to 6,1,3,4,10. By running ur program to
get exist(3,10,10), won't 6 be used in both a1 and a2? exist(3,[6,1,3], [6,
4])?

,
|
|

【在 b*******e 的大作中提到】
: for i == 0, only exist(0, 4, 0) and exist(0, 0, 4) = true. all other
: comibinations for i == 0 including exist(0, 4, 10) = false and exist(0, 10,
: 4) = false, so exist(1, 10, 10) = false.
: for i == 1, exist(1, 10, 0) = exist(0, 4, 0 ) || exist(0, 10, -6) = true ||
: false. and exist(1, 0, 10) = exist(0, -6, 10) || exist(0, 0, 4) = false ||
: true and exist(1, 4, 6) = exist(0, 4, 0) || exist(0, -2, 0) = true || false
: and
: exist (1, 6, 4) = exist(0, 0, 4) || exist(0, 6, -2) = true || false will be
: true. All other combinations will be false.
: for 1, 3, 4, 5, 1, 9, "6" participate in the selection only when i == 3. and

b*******e
发帖数: 217
45
exist(3, 10, 10)
= exist(2, 10-4, 10) || exist(2, 10, 10-4)
= exist(2, 6, 10) || exist(2, 10, 6) = false || false = false already.
let us continue from i == 2 to i== 1
= exist(1, 3, 10) || exist(1, 6, 7) || exist(1, 7, 6) || exist(1, 6, 7)
= false || false || false || false.
we can continue from i == 1 to 0.
also we can find it is false.
So exist(3, 10, 10) = false. That indicates 6 are not used for multiple
times.
Otherwise exist(3, 10, 10) should be true.

to
6,

【在 c********t 的大作中提到】
: I think it will cause the problem,if continuing, later 4 might be used in
: both a1 and a2.
: let me simplify my second example to 6,1,3,4,10. By running ur program to
: get exist(3,10,10), won't 6 be used in both a1 and a2? exist(3,[6,1,3], [6,
: 4])?
:
: ,
: |
: |

c********t
发帖数: 5706
46
好像你是对的。我有空做做看。多谢!

【在 b*******e 的大作中提到】
: exist(3, 10, 10)
: = exist(2, 10-4, 10) || exist(2, 10, 10-4)
: = exist(2, 6, 10) || exist(2, 10, 6) = false || false = false already.
: let us continue from i == 2 to i== 1
: = exist(1, 3, 10) || exist(1, 6, 7) || exist(1, 7, 6) || exist(1, 6, 7)
: = false || false || false || false.
: we can continue from i == 1 to 0.
: also we can find it is false.
: So exist(3, 10, 10) = false. That indicates 6 are not used for multiple
: times.

b*******e
发帖数: 217
47
This is a problem in DP chapter of "Algorithms" by a berkeley professor. It
asked for a polynomail complexity solution whether dividing evenly by 3
exists or not.

【在 d****r 的大作中提到】
: 一道面试题:
: 给定一个整数数组。怎样能将其分为三组(不要求个数相等),使每组值的总和相等。
: 不能分的时候返回空值。能分的时候给出一个解就行。
: 我只能想到三进制,有没有更优化的方法?

1 (共1页)
进入JobHunting版参与讨论
相关主题
[合集] 面试题求解这题有点意思 给一个数组, 找最大的整数m, 使得数组里比m大的或相等 的值的树木大于等于m(线性)
面试题把一个数组划分成尽可能相等的k份
Google的一道面试题问道题
问一道google面试题(from careercup)请教一道面试题
一个面试题请教一道google的面试题
问几道算法题一道列举所有和相等的pairs的面试题.
贡献个面试题,目前狗狗都没找到.....大家看看这几道google面试题怎么做?
简单问题2问道面试题
相关话题的讨论汇总
话题: exist话题: 10话题: false话题: a1话题: a2