## Amazon Interview Question for Software Developers

• 2
of 2 votes

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 6 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.
0
of 0 vote

Anyone understand this line

return assignBalls(m, n - 1) + assignBalls(m - n, n)

?

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

When n>m
Total number of ways to assign balls = number of ways to assign balls in bins where at least one or more bins are empty + number of ways to assign balls in bins where no bins are empty.

number of ways to assign balls in bins where at least one or more bins are empty = assignBalls(m, n - 1) - explanation: since we are using recursion assume when 1 less bin was there, then no of ways will be assignBalls(m, n - 1). Now with every combination you add a new empty bin.

number of ways to assign balls in bins where no bins are empty = assignBalls(m - n, n) - explanation: you assign 1 ball in each bin so that no bin is empty and then assign remaining m-n balls among n bins.

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

assignBalls(m, n - 1)

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) ?

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More