## Cisco Systems Interview Question

• 0

Country: India

Comment hidden because of low score. Click to expand.
2
of 4 vote

Let P(i,j) denote the probability of j heads amongst the coins C_i, C_(i+1), ..., C_(N-1).
In 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).

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

import java.io.*;
class Soll
{
soll(int i,intj)
int c[][];
c[i][j]=c[i+1][j+2];
for(int a=0;a<=6;a++)
{
system.out.prinln(c[i][j]);
}
}
public static void main(String args)
{
Soll s=new Soll(2,4);
}

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

in python:
def choose_probs(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield elements[i]
else:
for next in choose_iter(elements[i+1:len(elements)], length-1):
yield elements[i] * np.prod(next)
def totabl_prob(probs, k):
return np.sum(choose_probs(probs, k))

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

``````def choose_probs(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield elements[i]
else:
for next in choose_iter(elements[i+1:len(elements)], length-1):
yield elements[i] * np.prod(next)
def totabl_prob(probs, k):
return np.sum(choose_probs(probs, k))``````

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

``````def choose_probs(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield elements[i]
else:
for next in choose_iter(elements[i+1:len(elements)], length-1):
yield elements[i] * np.prod(next)
def totabl_prob(probs, k):
return np.sum(choose_probs(probs, k))``````

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

Dynamic programming solution:

``````def get_prob(k, probs):
n = len(probs)
if k > n:
return 0
memo = [*n for _ in range(k+1)]
memo = [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]``````

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.

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