Google Interview Question
SDE1sCountry: United States
Number of Songs: N
Number of Songs to be played: L
Interval between the same song: K
Initially all songs has to be played, After playing N songs, Remaining number of songs to be played L-N.
Initial N songs can be selected in N! ways.
The Interval between the same song should be K, The remaining songs for selection are 'N-K'.
The Answer: N! * (N-K) power of (L-N)
Ex: N: 1,2,3 L-5 and K-2
The possible options:
1 2 3 1 2
1 3 2 1 3
2 1 3 2 1
2 3 1 2 3
3 1 2 3 1
3 2 1 3 2
Please correct the Answer/Approach if its incorrect.
Let F(N,L,K) = N*(N-1)...(N-K) * [(N-K)*(N-K)*....(N-L)].(length is L)
- lxfuhuo January 08, 2018The answer should be :
F(N,L,K) - C(N,1)F(N-1,L,K) + C(N,2)F(N-2,L,K)F(N,3)F(N-3,L,K) .....where C(n,i) means combination number of selecting i items from n items.