## shuaixin.david

BAN USERprint path in a recursive way

```
GRAPH={'A':['B','C','D'], 'B':['A','C','D'], 'C':['A','B','D'], 'D':['A','B','C']}
def find_noloop_path(s, t, path):
if s in path:###already visited in path
return
if s == t:###find the target
print path + [t]
return
path.append(s)
for n in GRAPH[s]:
find_noloop_path(n, t, path[:])
find_noloop_path('A', 'C', [])
```

result:

['A', 'B', 'C']

['A', 'B', 'D', 'C']

['A', 'C']

['A', 'D', 'B', 'C']

['A', 'D', 'C']

I share the same thoughts with you.

Just consider it as a Binomial distribution..

We can achieve the O(n) solution without using recursion

def isMatch(reg, str):

if not reg and not str:##both reg and str are NULL

return True

if len(reg) == 2 and reg[1]=='*':##reg='a*' and b=''

return str==''

i = 0

j = 0

while i < len(reg) and j < len(str):

if i+2<len(reg) and reg[i+2]=='*':

if reg[i] == str[j]:

i = i + 3

j = j + 1

else:

return False

elif reg[i] == '.':

i += 1

j += 1

else:

if reg[i]==str[j]:

i += 1

j += 1

else:

return False

return (i == len(reg) and j==len(str))

Is your statement is complete?

this seems a incomplete problem and to solve it, more information is needed.

For instance, how many times can the two persons try? 2, or more than 2?

I will set up a Hypothesis testing. Let theta be the probability that the coin is head, k be the number of times we observed that the coin is head.

H0 (null hypothesis): the coin is fair, i.e. theta=0.5

H1 (alternative): the coin is not fair, i.e. theta!=0.5

And the p value is the probability that the observed results are obtained under H0.

Because P(k) follows binomial distribution so P(k) = (C10,k)*theta^(k)*(1-theta)^(10-k)

Under H0, theta=0.5, so we compute p value as P(k=8)=C10,8*0.5^(10)=0.044<0.05

If we set the significance level as 0.05 then we can reject the null hypothesis H0, in other words, we select H1, i.e. this is not a fair coin.

If we have more (i.e. 10) coins, because each coin is independent, so I can judge the fairness of each coin use the same method above.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

The solution seems reasonable but it tooks O(n^3)

- shuaixin.david November 05, 2013I think we can reduce it to O(n^2) if we utilize the following property

S[i,j] is palin if S[i-1,j+1] is palin and S[i]==S[j]