Amazon电面问题求大牛解答 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Amazon电面问题求大牛解答

Amazon电面问题求大牛解答# JobHunting - 待字闺中

i*t2010-07-21 07:07

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个输入）

s*t2010-07-21 07:07

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

M*52010-07-21 07:07

3 楼

题目没有说完整
数字是1至？
这一题好像也不是那么难。。。。。

i*t2010-07-21 07:07

4 楼

输入是介于1至10. 能否给点详细的思路？尤其是第二问？？

M*52010-07-21 07:07

5 楼

第二问的感觉有点像dynamic programming
要再想想

l*g2010-07-21 07:07

6 楼

I agree.

【在 s*********t 的大作中提到】

: 感觉和那个找两个数和为X的题很接近

s*t2010-07-21 07:07

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 的大作中提到】

c*r2010-07-21 07:07

8 楼

This is not an optimization problem.

【在 M********5 的大作中提到】

: 第二问的感觉有点像dynamic programming
: 要再想想

l*g2010-07-21 07:07

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

s*t2010-07-21 07:07

10 楼

我也没仔细测试，可能有错

【在 l*******g 的大作中提到】

: your code confuses me. hehe. Sorry.

p*n2010-07-21 07:07

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

f*52010-07-21 07:07

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

f*52010-07-21 07:07

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 的大作中提到】

i*12010-07-21 07:07

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]
}

f*52010-07-21 07:07

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]
: }

i*12010-07-21 07:07

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

f*52010-07-21 07:07

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.

i*e2010-07-21 07:07

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)

h*62010-07-21 07:07

19 楼

既然输入都在1~10之间，用brute force就可以解决了，一共2^10 = 1024种情况

p*n2010-07-21 07:07

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