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