Cisco Systems Interview Question
Country: India
Dynamic programming solution:
def get_prob(k, probs):
n = len(probs)
if k > n:
return 0
memo = [[0]*n for _ in range(k+1)]
memo[0] = [reduce(mul, [(1-p) for p in probs[:i+1]])
for i in range(n)]
for i in range(1, k+1):
memo[i][i] = reduce(mul, probs[:i+1])
for j in range(k+1, n):
memo[i][j] = probs[j]*memo[i-1][j-1] \
+ (1-probs[j])*memo[i][j-1]
return memo[k][-1]
Let P(i,j) denote the probability of j heads amongst the coins C_i, C_(i+1), ..., C_(N-1).
- RecruitingForSandvineCanada August 23, 2015In other words, we are trying to eventually determine P(0, K).
Assume the probability of getting a heads for i-th coin is prob[i].
Recurrence:
P(i,j) = prob[i]*( P(i+1, j-1) ) + (1-prob[i])*( P(i+1, j) ) <-- probability theory
Now create a memo over i,j to reduce the runtime to O(numCoins*K).