由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 这里聪明人多,来一道面试题
相关主题
请教一道面试题问几道面试题
Quick sort为什么需要logN的memory?问个 combination 问题
问个算法题share一下最近三个电话面试题Amazon, Groupon, Google
O(1)space解法到底能不能用递归?问一道题(2)
求教一道面试题面试题
求教一个combination的问题,求好方法发点面试题讨包子(cs)
请问可以用二分法判断一个数组是否sorted吗?昨天的google面试题
请教一个面试题[合集] 昨天的google面试题
相关话题的讨论汇总
话题: p1话题: p2话题: int话题: 100话题: p3
进入JobHunting版参与讨论
1 (共1页)
n***k
发帖数: 2780
1
请教各位大牛指教了:
有N个nonunique numbers, 每个数都是在1到100之间,
请问用什么方法能最快地找出所有的数的排列组合that the total of all numbers in
it is greater than 100?
n***k
发帖数: 2780
2
不可能这里没人会做吧?

in

【在 n***k 的大作中提到】
: 请教各位大牛指教了:
: 有N个nonunique numbers, 每个数都是在1到100之间,
: 请问用什么方法能最快地找出所有的数的排列组合that the total of all numbers in
: it is greater than 100?

t********t
发帖数: 5415
3
还要排列?比如10-41-50和50-41-10算两组?
n***k
发帖数: 2780
4
说错了,不算排列,只是组合。
你说的算一组。

【在 t********t 的大作中提到】
: 还要排列?比如10-41-50和50-41-10算两组?
y****n
发帖数: 579
5
同问?
w********9
发帖数: 8613
6
是计算算法的问题吗?
排序:A1 基本问题Q(m):m (<=N) numbers, A(1) to A(m), to find all combinations each
having a sum greater than S(m).
Take out Am, reduce the question to Q(m-1) for A1 to A(m-1) with S(m-1)=S(m)
-A(m)。
更小的一些细节(比如列出AM到AN的各种组合)就不说了。
K******g
发帖数: 1870
7
一个更简单的办法:
1)排序,从小到大
2)两个指针,p1 points to the first element, and the p2 points to the
largest element.
3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
combination with *p2. Then --p2. repeat.
4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
5) repeat until p1 and p2 meet.
the total complexity will be O(nlogn).

each
m)

【在 w********9 的大作中提到】
: 是计算算法的问题吗?
: 排序:A1: 基本问题Q(m):m (<=N) numbers, A(1) to A(m), to find all combinations each
: having a sum greater than S(m).
: Take out Am, reduce the question to Q(m-1) for A1 to A(m-1) with S(m-1)=S(m)
: -A(m)。
: 更小的一些细节(比如列出AM到AN的各种组合)就不说了。

n***k
发帖数: 2780
8
let me see. this could be a very good solution.

value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
p1 are such as combination. then ++p1, repeat.

【在 K******g 的大作中提到】
: 一个更简单的办法:
: 1)排序,从小到大
: 2)两个指针,p1 points to the first element, and the p2 points to the
: largest element.
: 3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
: combination with *p2. Then --p2. repeat.
: 4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
: 5) repeat until p1 and p2 meet.
: the total complexity will be O(nlogn).
:

w********9
发帖数: 8613
9

value so that *p3>100-(*p1+*p2). Then any number between p3 and p2
together p1 are such as combination. then ++p1, repeat.
你这个更复杂。我只是给了个框架和大思路,否则不简明。那个方法每一步也是可以用
binaryS的(A1
到Am的和,在准备期就被记下来了),跳过很多数的。
因为中间要列组合,不可能是O(N*lgN)。

【在 K******g 的大作中提到】
: 一个更简单的办法:
: 1)排序,从小到大
: 2)两个指针,p1 points to the first element, and the p2 points to the
: largest element.
: 3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
: combination with *p2. Then --p2. repeat.
: 4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
: 5) repeat until p1 and p2 meet.
: the total complexity will be O(nlogn).
:

z***9
发帖数: 696
10
这个先用counting sort, 然后作1-100的组合,O(n)?
相关主题
求教一个combination的问题,求好方法问几道面试题
请问可以用二分法判断一个数组是否sorted吗?问个 combination 问题
请教一个面试题share一下最近三个电话面试题Amazon, Groupon, Google
进入JobHunting版参与讨论
n***k
发帖数: 2780
11
不懂。。。

【在 z***9 的大作中提到】
: 这个先用counting sort, 然后作1-100的组合,O(n)?
z***9
发帖数: 696
12
counting sort -> array [n] --> array[100]
check a[1]+a[100],
a[2]+a[99], a[2]+a[100]...
g**e
发帖数: 6127
13
你这怎么会是nlogn,"*p1 to *(p2-1) can have such a combination with *p2"。要
找出p1至p2-1的全组合, 难道是O(1)?

value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
p1 are such as combination. then ++p1, repeat.

【在 K******g 的大作中提到】
: 一个更简单的办法:
: 1)排序,从小到大
: 2)两个指针,p1 points to the first element, and the p2 points to the
: largest element.
: 3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
: combination with *p2. Then --p2. repeat.
: 4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
: 5) repeat until p1 and p2 meet.
: the total complexity will be O(nlogn).
:

p******r
发帖数: 2999
14
排序后DP
O(n^2)

value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
p1 are such as combination. then ++p1, repeat.

【在 K******g 的大作中提到】
: 一个更简单的办法:
: 1)排序,从小到大
: 2)两个指针,p1 points to the first element, and the p2 points to the
: largest element.
: 3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
: combination with *p2. Then --p2. repeat.
: 4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
: 5) repeat until p1 and p2 meet.
: the total complexity will be O(nlogn).
:

K******g
发帖数: 1870
15
如果按照你这种算法的话,如果组合的个数是n^2级别的话,那就不存在小于O(n^2)
的算法。
这道题目应该说是找出combination的个数。

together

【在 g**e 的大作中提到】
: 你这怎么会是nlogn,"*p1 to *(p2-1) can have such a combination with *p2"。要
: 找出p1至p2-1的全组合, 难道是O(1)?
:
: value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
: p1 are such as combination. then ++p1, repeat.

g**e
发帖数: 6127
16
组合的个数是2^n

【在 K******g 的大作中提到】
: 如果按照你这种算法的话,如果组合的个数是n^2级别的话,那就不存在小于O(n^2)
: 的算法。
: 这道题目应该说是找出combination的个数。
:
: together

y****n
发帖数: 579
17
我来贴代码
private static void Combination(Vector array, int start, int k,
int limitsum) {
int remaining = array.size() - start;
if (remaining == k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += array.get(start + i);
}
if (sum < limitsum) {
return;
}
for (int i = 0; i < array.size(); i++) {
System.out.print(array.get(i) + " ");
}
w********9
发帖数: 8613
18

k,
只是个算法问题,可以只是理论上的(而不一定有实用性)。最多写个pseudo code就可以了。
另外,写程序还是要多些写comments。

【在 y****n 的大作中提到】
: 我来贴代码
: private static void Combination(Vector array, int start, int k,
: int limitsum) {
: int remaining = array.size() - start;
: if (remaining == k) {
: int sum = 0;
: for (int i = 0; i < k; i++) {
: sum += array.get(start + i);
: }
: if (sum < limitsum) {

w********9
发帖数: 8613
s**9
发帖数: 207
20
solution based on back tracking:
#include
using namespace std;
const int N=10;
const int M=10;
//sort a[N] first;
int a[N]={0,0, 2, 3, 4,5,5,8,9,10};
int level=0;
int order[N];
int sum=0;
void comb(int i){
order[level++]=a[i];
sum+=a[i];
if(sum>M){
for(int j=0;j cout< cout< }
if(level for(int j=i+1;j if(a[j]!=a[j-1])
comb(j);
}
}
sum-=a[i]

【在 n***k 的大作中提到】
: 请教各位大牛指教了:
: 有N个nonunique numbers, 每个数都是在1到100之间,
: 请问用什么方法能最快地找出所有的数的排列组合that the total of all numbers in
: it is greater than 100?

相关主题
问一道题(2)昨天的google面试题
面试题[合集] 昨天的google面试题
发点面试题讨包子(cs)几道微软面试题
进入JobHunting版参与讨论
w********9
发帖数: 8613
21

楼主只是要求方法。写code还是应该加些comment,否则造成费解。质量高些的地方都
是有这个要
求的。
两个没用的0元素是你fill in以便M和N相等?用得上吗?
排序结果用得太少。重复值是可以用两次以上的。
因为有组合,怎么也逃不了某种recursion。把Q(M,S(M))的问题转换成Q(M-1,S(M))和
Q(M-
1,S(M-1)=S(M)-A(M)),排序就很好用上。有重复值时,排序后A(1)to A(M)各个相互不
等同,
每个有count(1)到count(M)。把Q(M,N)的问题转换成Q(M-1,S(M)),
。。。
Q(M-1,S(M)-count(M)*A(M))
其中有些recursion可能会没必要做(当余下的数和太小时)。

【在 s**9 的大作中提到】
: solution based on back tracking:
: #include
: using namespace std;
: const int N=10;
: const int M=10;
: //sort a[N] first;
: int a[N]={0,0, 2, 3, 4,5,5,8,9,10};
: int level=0;
: int order[N];
: int sum=0;

g****n
发帖数: 431
22
你这个方式是错的,反例:
1,2,3,50,60,70
按你的方法,*p1 + *p2 = 71 <= 100。 然后p3指向50,满足*p3>100-(*p1+*p2)。这
时你
输出1以及50和70之间的数,然后++p1。++p1后,你的方法已经漏过了一个解:
1+2+3+50+60+70。这个解按你的方法永远不会出现了。

a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2
together p1 are such as combination. then ++p1, repeat.

【在 K******g 的大作中提到】
: 一个更简单的办法:
: 1)排序,从小到大
: 2)两个指针,p1 points to the first element, and the p2 points to the
: largest element.
: 3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
: combination with *p2. Then --p2. repeat.
: 4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
: 5) repeat until p1 and p2 meet.
: the total complexity will be O(nlogn).
:

g****n
发帖数: 431
23
1. 按你的方法,排序是不需要的
2. 你的方法本质上只是brute遍历的一种实现,时间复杂度仍然是(2^n),没有任何改进

each
1)=S(m)

【在 w********9 的大作中提到】
: 是计算算法的问题吗?
: 排序:A1: 基本问题Q(m):m (<=N) numbers, A(1) to A(m), to find all combinations each
: having a sum greater than S(m).
: Take out Am, reduce the question to Q(m-1) for A1 to A(m-1) with S(m-1)=S(m)
: -A(m)。
: 更小的一些细节(比如列出AM到AN的各种组合)就不说了。

w********9
发帖数: 8613
24

必要。有的数可能是有重复的。排序结果可以用来避免重复计算和重复解。
还有,每次recursion是最大的数被taken out。对不少情况,这样做会让Q reduce得快
、真正要做的recursion会少一些。
改进
不是那样的。余下数的总和比S小时,recursion就没有必要做下去了,相应的那些余数
的组合也就免了(当然可能在另外的recursion里没有)。(楼主在san Francisco的版
面上把题目做了个小改动,使得更多的组合不需要做。)
这个问题本身最坏的complexity就是O(2^N)。能做的只是减小2^N前的系数。

【在 g****n 的大作中提到】
: 1. 按你的方法,排序是不需要的
: 2. 你的方法本质上只是brute遍历的一种实现,时间复杂度仍然是(2^n),没有任何改进
:
: each
: 1)=S(m)

K******g
发帖数: 1870
25
这样子好了,如果*p1+*p2 < 100, 我们用recursive,p3指向p1+1,再在p1+1和p2-1之
间找组合,使得这个组合的和大于100-(*p1+*p2)。每次内层找到的组合必须加上外层
已经有的组合,这样子就可以把所有的找出来了。
不过这样的复杂度会很高的。一个简单的办法就是将数组所有的组合产生出来,然后每
个判断。

【在 g****n 的大作中提到】
: 你这个方式是错的,反例:
: 1,2,3,50,60,70
: 按你的方法,*p1 + *p2 = 71 <= 100。 然后p3指向50,满足*p3>100-(*p1+*p2)。这
: 时你
: 输出1以及50和70之间的数,然后++p1。++p1后,你的方法已经漏过了一个解:
: 1+2+3+50+60+70。这个解按你的方法永远不会出现了。
:
: a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2
: together p1 are such as combination. then ++p1, repeat.

l****q
发帖数: 177
26
同感,有点类似duplicate的背包问题
f(i,100) = f(i-1, 100) + f(i, 100 - K*a[i]) (K = 1,2,3,...,k)
排序后,考虑第i种值的情况,有两种可能:
只考虑前i-1种值的情况得出的所有解
除了i-1种值,也加上第i种值,如果这种值的数有k个,则可取1到k次

together

【在 p******r 的大作中提到】
: 排序后DP
: O(n^2)
:
: value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
: p1 are such as combination. then ++p1, repeat.

w********9
发帖数: 8613
27

http://www.mitbbs.com/article_t1/SanFrancisco/33200773_0_2.html
发信人: wewill2009 (daluobe), 信区: SanFrancisco
标 题: Re: 这里聪明人多,来一道面试题 (转载)
发信站: BBS 未名空间站 (Sat Jun 19 14:03:49 2010, 美东)
不是。这里并没有要求个数(总价格)是最大的,因此满足要求的组合更多。

【在 l****q 的大作中提到】
: 同感,有点类似duplicate的背包问题
: f(i,100) = f(i-1, 100) + f(i, 100 - K*a[i]) (K = 1,2,3,...,k)
: 排序后,考虑第i种值的情况,有两种可能:
: 只考虑前i-1种值的情况得出的所有解
: 除了i-1种值,也加上第i种值,如果这种值的数有k个,则可取1到k次
:
: together

w********9
发帖数: 8613
28

过分复杂化了。要处理×p1或×p2不在考虑之内的情况。nonunique的情况更复杂。

【在 K******g 的大作中提到】
: 这样子好了,如果*p1+*p2 < 100, 我们用recursive,p3指向p1+1,再在p1+1和p2-1之
: 间找组合,使得这个组合的和大于100-(*p1+*p2)。每次内层找到的组合必须加上外层
: 已经有的组合,这样子就可以把所有的找出来了。
: 不过这样的复杂度会很高的。一个简单的办法就是将数组所有的组合产生出来,然后每
: 个判断。

l****q
发帖数: 177
29
没有说是一样的
f(i,100) = f(i-1, 100) + f(i, 100 - K*a[i]) (K = 1,2,3,...,k)
f(i,100)是大于100的所有使用了前i种值的集合
当然了,如果转移方程本身有误,还请指正

【在 w********9 的大作中提到】
:
: 过分复杂化了。要处理×p1或×p2不在考虑之内的情况。nonunique的情况更复杂。

w********9
发帖数: 8613
30

这和我前面的解法是一样的吧?
与背包问题的本质(这里没有对总价格的任何要求)和解法相差很大。

【在 l****q 的大作中提到】
: 没有说是一样的
: f(i,100) = f(i-1, 100) + f(i, 100 - K*a[i]) (K = 1,2,3,...,k)
: f(i,100)是大于100的所有使用了前i种值的集合
: 当然了,如果转移方程本身有误,还请指正

相关主题
贡献亚马逊面试题Quick sort为什么需要logN的memory?
面试题问个算法题
请教一道面试题O(1)space解法到底能不能用递归?
进入JobHunting版参与讨论
w********9
发帖数: 8613
31

更确切些:这里是按“价格”递推,而不是按“重量”递推。

【在 w********9 的大作中提到】
:
: 这和我前面的解法是一样的吧?
: 与背包问题的本质(这里没有对总价格的任何要求)和解法相差很大。

1 (共1页)
进入JobHunting版参与讨论
相关主题
[合集] 昨天的google面试题求教一道面试题
几道微软面试题求教一个combination的问题,求好方法
贡献亚马逊面试题请问可以用二分法判断一个数组是否sorted吗?
面试题请教一个面试题
请教一道面试题问几道面试题
Quick sort为什么需要logN的memory?问个 combination 问题
问个算法题share一下最近三个电话面试题Amazon, Groupon, Google
O(1)space解法到底能不能用递归?问一道题(2)
相关话题的讨论汇总
话题: p1话题: p2话题: int话题: 100话题: p3