Alphabet phone interview
Anonymous User
984

Different ways to represent N as sum of S non-negative integers
Given N and S. The task is to find out how many different ways are there to represent N as the sum of S non-negative integers.

N=2, S=4
(0, 4)
(1, 3)
(2, 2)
(3, 1)
(4, 0)
=> 5

N=3, S=5
(0, 0, 5)
(0, 1, 4)
...
=> 21

It is a dynamic programming problem, I couldn't solve it during the interview. Any idea how to solve it? Thank you

P.S it was with one of the alphabet companies.

Comments (9)