Redian新闻
>
Amazon电面问题求大牛解答
avatar
Amazon电面问题求大牛解答# JobHunting - 待字闺中
i*t
1
写一个方法,接受4个整数输入,输出一个integer result.
输入值都介于1至10, 此方法应该返回输入数和值为18的组合数目
例如:输入W, X, Y, and Z, 值为4, 6, 8, 10。输出应该为2
因为和值为18的组合有两个:

Input:
W = 4
X = 6
Y = 8
Z = 10

Combos:
Y + Z = 18
W + X + Y = 18
扩展:
如何改进你的算法以接收随意数目的输入。(不局限于刚好4个输入)
avatar
s*t
2
感觉和那个找两个数和为X的题很接近

【在 i****t 的大作中提到】
: 写一个方法,接受4个整数输入,输出一个integer result.
: 输入值都介于1至10, 此方法应该返回输入数和值为18的组合数目
: 例如:输入W, X, Y, and Z, 值为4, 6, 8, 10。输出应该为2
: 因为和值为18的组合有两个:
:
: Input:
: W = 4
: X = 6
: Y = 8
: Z = 10

avatar
M*5
3
题目没有说完整
数字是1至?
这一题好像也不是那么难。。。。。
avatar
i*t
4
输入是介于1至10. 能否给点详细的思路?尤其是第二问??
avatar
M*5
5
第二问的感觉有点像dynamic programming
要再想想
avatar
l*g
6
I agree.

【在 s*********t 的大作中提到】
: 感觉和那个找两个数和为X的题很接近
avatar
s*t
7
def findsum(arr, s):
ht = {}
for i in arr:
for j in ht.items():
if ht.has_key(j[0]+i):
ht[j[0]+i] += j[1]
else:
ht[j[0]+i] = 1
if ht.has_key(i):
ht[i] += 1
else:
ht[i] = 1
return ht[s]

【在 i****t 的大作中提到】
: 写一个方法,接受4个整数输入,输出一个integer result.
: 输入值都介于1至10, 此方法应该返回输入数和值为18的组合数目
: 例如:输入W, X, Y, and Z, 值为4, 6, 8, 10。输出应该为2
: 因为和值为18的组合有两个:
:
: Input:
: W = 4
: X = 6
: Y = 8
: Z = 10

avatar
c*r
8
This is not an optimization problem.

【在 M********5 的大作中提到】
: 第二问的感觉有点像dynamic programming
: 要再想想

avatar
l*g
9
your code confuses me. hehe. Sorry.

【在 s*********t 的大作中提到】
: def findsum(arr, s):
: ht = {}
: for i in arr:
: for j in ht.items():
: if ht.has_key(j[0]+i):
: ht[j[0]+i] += j[1]
: else:
: ht[j[0]+i] = 1
: if ht.has_key(i):
: ht[i] += 1

avatar
s*t
10
我也没仔细测试,可能有错

【在 l*******g 的大作中提到】
: your code confuses me. hehe. Sorry.
avatar
p*n
11
What about this solution
S(n, k) = S(n - 1, k) + S(n-1, k-a[n])
n is the number of the input numbers
k is the given sum.
In the case that n = 4, k = 18
S(4, 18) = S(3, 18) + S(3, 8)
S(3, 18) = S(2, 18) + S(2, 10)
S(3, 8) = S(2, 8) + S(2, 0)
among the above, S(2, 10) = 1, S(2, 0) = 1(because a[3] = 8)
Therefore, S(4, 18) = 2
avatar
f*5
12
u will get duplicate results.
for example int a[3]={2,1,3};
s(3,3)=s(2,3)+s(2,1)
s(2,1)=1 //only 1,then your combination is 1,2
s(2,3)=s(1,3)+s(1,2)
you will get two combination 3 and 2,1

【在 p******n 的大作中提到】
: What about this solution
: S(n, k) = S(n - 1, k) + S(n-1, k-a[n])
: n is the number of the input numbers
: k is the given sum.
: In the case that n = 4, k = 18
: S(4, 18) = S(3, 18) + S(3, 8)
: S(3, 18) = S(2, 18) + S(2, 10)
: S(3, 8) = S(2, 8) + S(2, 0)
: among the above, S(2, 10) = 1, S(2, 0) = 1(because a[3] = 8)
: Therefore, S(4, 18) = 2

avatar
f*5
13
find the combination of items in input[] with the sum of tartget.
static int count=0;
quicksort(input,0,size-1);
void GetCombinationNumber(int input[],int used[],vector&vec,int
size,int target,int *count)
{
if (target==0) { *count++; return; }
for(int i=0;i{
if (used[i]==1)continue; //we donot want to use them
repeatedly
if ((vec.size()>0)&&(vec.back()>a[i])) continue; //we will use
the items in
order so that we can avoid duplicate
if (t

【在 i****t 的大作中提到】
: 写一个方法,接受4个整数输入,输出一个integer result.
: 输入值都介于1至10, 此方法应该返回输入数和值为18的组合数目
: 例如:输入W, X, Y, and Z, 值为4, 6, 8, 10。输出应该为2
: 因为和值为18的组合有两个:
:
: Input:
: W = 4
: X = 6
: Y = 8
: Z = 10

avatar
i*1
14
if (the number of element is less than around 20), we can enumerate all
posibilities using bits related method.
else {
//DP. suppose there are N positive numbers V[1] to V[N] and we need to
reach sum S
Possiblity[S,N] stores the final answer
And Possiblity[A,B] stores the number of possibility to sum to A using
the first B numbers
Possiblity[A,B] = possiblity[A-V[B],B-1] + possibility[A,B-1]
}
avatar
f*5
15
i think u will get duplicate results

need to
using

【在 i***1 的大作中提到】
: if (the number of element is less than around 20), we can enumerate all
: posibilities using bits related method.
: else {
: //DP. suppose there are N positive numbers V[1] to V[N] and we need to
: reach sum S
: Possiblity[S,N] stores the final answer
: And Possiblity[A,B] stores the number of possibility to sum to A using
: the first B numbers
: Possiblity[A,B] = possiblity[A-V[B],B-1] + possibility[A,B-1]
: }

avatar
i*1
16
Good catch. If there are duplicate numbers in input, and they don't
distinguish from each other, (I mean A=4, B=4, and we don't care variable
name) then both of my methods will get duplicates.
The DP need some changes to address this situation.

【在 f*********5 的大作中提到】
: i think u will get duplicate results
:
: need to
: using

avatar
f*5
17
i didn't mean duplicate input,
i mean...
see my above post

variable

【在 i***1 的大作中提到】
: Good catch. If there are duplicate numbers in input, and they don't
: distinguish from each other, (I mean A=4, B=4, and we don't care variable
: name) then both of my methods will get duplicates.
: The DP need some changes to address this situation.

avatar
i*e
18
没有重复
可以想象成二叉树,从左到右递归
4--6--8--10
\/ \/ \/
/\ /\ /\
0--0--0--0
从左到右递归
#!/usr/bin/env runhaskell
count [] 0 = 1
count [] _ = 0
count a s = count (tail a) s + count (tail a) (s - head a)
main = print(count [4, 6, 8, 10] 18)
avatar
h*6
19
既然输入都在1~10之间,用brute force就可以解决了,一共2^10 = 1024种情况
avatar
p*n
20
这个应该是
s(3, 3) = s(2, 3) + s(2, 0)/* s(2, 0) is 1, because a[3] is 3*/
s(2, 3) = s(1, 3) + s(1, 2)
s(1, 3) = 0
s(1, 2) = 1 /* because a[1] = 2 */
所以 s(3, 3) = 2, 也就是找到两个组合sum up to 3

【在 f*********5 的大作中提到】
: u will get duplicate results.
: for example int a[3]={2,1,3};
: s(3,3)=s(2,3)+s(2,1)
: s(2,1)=1 //only 1,then your combination is 1,2
: s(2,3)=s(1,3)+s(1,2)
: you will get two combination 3 and 2,1

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。