logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
这里聪明人多，来一道面试题
avatar
这里聪明人多，来一道面试题# JobHunting - 待字闺中
n*k
1 楼
请教各位大牛指教了：
有N个nonunique numbers, 每个数都是在1到100之间，
请问用什么方法能最快地找出所有的数的排列组合that the total of all numbers in
it is greater than 100?
avatar
n*k
2 楼
不可能这里没人会做吧？

in

【在 n***k 的大作中提到】
: 请教各位大牛指教了：
: 有N个nonunique numbers, 每个数都是在1到100之间，
: 请问用什么方法能最快地找出所有的数的排列组合that the total of all numbers in
: it is greater than 100?
avatar
t*t
3 楼
还要排列？比如10-41-50和50-41-10算两组？
avatar
n*k
4 楼
说错了，不算排列，只是组合。
你说的算一组。

【在 t********t 的大作中提到】
: 还要排列？比如10-41-50和50-41-10算两组？
avatar
y*n
5 楼
同问？
avatar
w*9
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的各种组合）就不说了。
avatar
K*g
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的各种组合）就不说了。
avatar
n*k
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).
:
avatar
w*9
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).
:
avatar
z*9
10 楼
这个先用counting sort, 然后作1－100的组合，O(n)?
avatar
n*k
11 楼
不懂。。。

【在 z***9 的大作中提到】
: 这个先用counting sort, 然后作1－100的组合，O(n)?
avatar
z*9
12 楼
counting sort -> array [n] --> array[100]
check a[1]+a[100],
a[2]+a[99], a[2]+a[100]...
avatar
g*e
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).
:
avatar
p*r
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).
:
avatar
K*g
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.
avatar
g*e
16 楼
组合的个数是2^n

【在 K******g 的大作中提到】
: 如果按照你这种算法的话，如果组合的个数是n^2级别的话，那就不存在小于O（n^2）
: 的算法。
: 这道题目应该说是找出combination的个数。
:
: together
avatar
y*n
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) + " ");
}
avatar
w*9
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) {
avatar
s*9
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;jcout<cout<}
if(levelfor(int j=i+1;jif(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?
avatar
w*9
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;
avatar
g*n
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).
:
avatar
g*n
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的各种组合）就不说了。
avatar
w*9
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)
avatar
K*g
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.
avatar
l*q
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.
avatar
w*9
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
avatar
w*9
28 楼

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

【在 K******g 的大作中提到】
: 这样子好了，如果*p1+*p2 < 100, 我们用recursive，p3指向p1+1，再在p1+1和p2-1之
: 间找组合，使得这个组合的和大于100-(*p1+*p2)。每次内层找到的组合必须加上外层
: 已经有的组合，这样子就可以把所有的找出来了。
: 不过这样的复杂度会很高的。一个简单的办法就是将数组所有的组合产生出来，然后每
: 个判断。
avatar
l*q
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的情况更复杂。
avatar
w*9
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种值的集合
: 当然了，如果转移方程本身有误，还请指正
avatar
w*9
31 楼

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

【在 w********9 的大作中提到】
:
: 这和我前面的解法是一样的吧？
: 与背包问题的本质（这里没有对总价格的任何要求）和解法相差很大。
相关阅读
亚麻现在面试是什么标准？眼红U家国人发财的U黑简直无法无天了纽约地区有什么startup？被老板逼迫签pip，要签么？同一家公司的不同方向的职位，能找不同的人内推么？求建议，startup offer选择年底职位少，下一波招人什么时候开始？2年经验 湾区码农求refer湾区就是个体户集散地已经寄给移民局offer letter申请OPT延期, 公司又改了开始工作的时间这里有没有亚麻做市场，销售或售前的同学聚会合影，猜猜哪个是斯坦福校友脸书高管 (转载)被雷后，找了一份不相干的工作，面试要讲吗？招合同工: 工程软件测试在大中小型IT公司一个sde工作的影响力是怎么样的一种体现？有没有这样一种专利，Uber申请之后别家不许做一样的事情？请教TEXAS SERVICE CENTER --Fax Number--opt京东商城的分类检索做的很垃圾我发现当PM比当马工还苦 (转载)面试的项目不给钱怎么办
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。