Amazon Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
@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.
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.
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.
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:
- aonecoding June 24, 2018