## Amazon Interview Question for Software Developers

• 2

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 5 vote

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

SOLUTION:

``````int assignBalls(int m, int n) {
if (m == 0 || n == 1) {
return 1;
}
if (n > m) {
return assignBalls(m, m);
} else {
return assignBalls(m, n - 1) + assignBalls(m - n, n);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def part(m, n):
if n < 2:
return 1
n = min(m, n)
dp = [[0]*n for _ in xrange(m)]
for i in xrange(m):
dp[i][0] = 1
for i in xrange(1, m):
for j in xrange(1, min(i+1, n)):
dp[i][j] = dp[i-1][j-1] + dp[i-j-1][j]
return sum(dp[m-1][j] for j in xrange(n))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@ranapratapchandra, counter example: 4 balls, 2 bins. The answer is 3, not 2 (4+0, 3+1, 2+2).
The original question can be rephrased as follows: how many ways a positive integer M can be written as a sum of N non-negative (we allow empty bins) integers where the order of addendums does not matter.

Comment hidden because of low score. Click to expand.
-1
of 3 vote

Points to be noted :
1. Bucket has no order
2. Only one type of ball is present.

This means , the question can be re-phrased as 'How many ways n bins can be re-arranged for 1 type of ball ?' . The number of ball in this question can be ignored as all balls are same.

This is a pure mathematical question - no coding required. It is asking the value of nC1 which is n.

The answer will always be = number of bins = n.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

isn't this nchoosek(m+n-1, m) ?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.