牛人们，进来帮助解数学题啦！ - 未名空间MITBBS历史存档

牛人们，进来帮助解数学题啦！# PDA - 掌中宝

l*n2013-05-16 07:05

1 楼

烙印面试居然问我Markov chain 之类的coding 解法，我当场傻掉。
given a list of words ["apple", "apce", appe"]
写个函数之类的，可以产生一些rules:
like:
1. first letter is 'a' 100%
2. last letter is 'e' 100%
3. p followed by l 33%
3. p followed by c 33%
......
他想要Markov chain ,概率方面的方向去做。我都说我不是ml 方向的，要画一个state
machine 之类的东东。请问有人知道怎么做吗？这些rules 是自动生成的based on
your input strings.

s*i2013-05-16 07:05

2 楼

现有酒 n 瓶。其中可能有少量几瓶（m）含有铊毒 (n > m)。
作为一个千老，你有老鼠若干。
你可以取多瓶酒滴混合喂老鼠。有毒就死。
求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。

a*m2013-05-16 07:05

3 楼

trie?

M*n2013-05-16 07:05

4 楼

不用老鼠，既然n
【在 s*i 的大作中提到】

: 现有酒 n 瓶。其中可能有少量几瓶（m）含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。

g*e2013-05-16 07:05

5 楼

这就是普通的coding question吧，又不是让你用markov解数学题。你自己不行

f*i2013-05-16 07:05

6 楼

m小于n吧，如果m够小，用二分法大概log n时间吧

千老，你有老鼠若干。="" :="" 你可以取多瓶酒滴混合喂老鼠。有毒就死。="" :=""
求解，怎么做才能最节省老鼠而验出哪瓶有毒。="">

【在 s*i 的大作中提到】

: 现有酒 n 瓶。其中可能有少量几瓶（m）含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。

l*82013-05-16 07:05

7 楼

不需要知道什么markov chain. 直接求概率就可以了吧

state

【在 l***n 的大作中提到】

: 烙印面试居然问我Markov chain 之类的coding 解法，我当场傻掉。
: given a list of words ["apple", "apce", appe"]
: 写个函数之类的，可以产生一些rules:
: like:
: 1. first letter is 'a' 100%
: 2. last letter is 'e' 100%
: 3. p followed by l 33%
: 3. p followed by c 33%
: ......
: 他想要Markov chain ,概率方面的方向去做。我都说我不是ml 方向的，要画一个state

s*i2013-05-16 07:05

8 楼

n > m
原文已经改了

[发表自未名空间手机版 - m.mitbbs.com]

【在 M******n 的大作中提到】

: 不用老鼠，既然n

l*82013-05-16 07:05

9 楼

应该跟trie没关系。

【在 a********m 的大作中提到】

: trie?

s*i2013-05-16 07:05

10 楼

不是说复杂度。说具体的算法。显然跟m有关。

"
[发表自未名空间手机版 - m.mitbbs.com]

【在 f*******i 的大作中提到】

: m小于n吧，如果m够小，用二分法大概log n时间吧
:
: 千老，你有老鼠若干。="" :="" 你可以取多瓶酒滴混合喂老鼠。有毒就死。="" :=""
: 求解，怎么做才能最节省老鼠而验出哪瓶有毒。="">

w*x2013-05-16 07:05

11 楼

如果就是你说的那几个rule好像也没啥tricky的

J*02013-05-16 07:05

12 楼

唔。。。难道不是逐瓶的灌？

S*e2013-05-16 07:05

13 楼

关键是要自动derive这些rules,而不是有几个rule,让你去算一下概率.
这个我也不懂,是不是还是得先有一个rule set,然后把概率高的拿出来
算总结出来的rule?

【在 w****x 的大作中提到】

: 如果就是你说的那几个rule好像也没啥tricky的

s*s2013-05-16 07:05

14 楼

m+1?

【在 s*i 的大作中提到】

: 现有酒 n 瓶。其中可能有少量几瓶（m）含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。

l*n2013-05-16 07:05

15 楼

对！ rules 是要自动生成的，就好像一个model 一样！

【在 S*******e 的大作中提到】

: 关键是要自动derive这些rules,而不是有几个rule,让你去算一下概率.
: 这个我也不懂,是不是还是得先有一个rule set,然后把概率高的拿出来
: 算总结出来的rule?

a*a2013-05-16 07:05

16 楼

这个还是一瓶一瓶灌比较省老鼠吧？
要不然，两瓶一混，老鼠死了，拿出一瓶灌，老鼠还是死了，你还得灌剩下那瓶，结果
又死了，弄死三个才鉴别出两瓶，更浪费了。

f*e2013-05-16 07:05

17 楼

他问你的可能是hidden markov chain。知道测量结果，求参数。好像有现成的公式。

state

【在 l***n 的大作中提到】

: 烙印面试居然问我Markov chain 之类的coding 解法，我当场傻掉。
: given a list of words ["apple", "apce", appe"]
: 写个函数之类的，可以产生一些rules:
: like:
: 1. first letter is 'a' 100%
: 2. last letter is 'e' 100%
: 3. p followed by l 33%
: 3. p followed by c 33%
: ......
: 他想要Markov chain ,概率方面的方向去做。我都说我不是ml 方向的，要画一个state

s*i2013-05-16 07:05

18 楼

显然不是啦。比如最多就1瓶有毒。总共16瓶。你的方法最差情况要测试16次呢。
二分法最多9次就搞定了

【在 a***a 的大作中提到】

: 这个还是一瓶一瓶灌比较省老鼠吧？
: 要不然，两瓶一混，老鼠死了，拿出一瓶灌，老鼠还是死了，你还得灌剩下那瓶，结果
: 又死了，弄死三个才鉴别出两瓶，更浪费了。

w*x2013-05-16 07:05

19 楼

你没这个背景问你这个问题就是要你死啊~~

J*02013-05-16 07:05

20 楼

问题是你要省老鼠，不是省灌的次数

【在 s*i 的大作中提到】

: 显然不是啦。比如最多就1瓶有毒。总共16瓶。你的方法最差情况要测试16次呢。
: 二分法最多9次就搞定了

a*m2013-05-16 07:05

21 楼

hmm还是比较复杂的。不过这个题目只是一个普通统计程序，lz想太多了。

【在 f*****e 的大作中提到】

: 他问你的可能是hidden markov chain。知道测量结果，求参数。好像有现成的公式。
:
: state

a*32013-05-16 07:05

22 楼

hehe, you are talking about the worst case. The best case is both are good,
you can save one attempt without losing one mouse with mixed drink.

【在 a***a 的大作中提到】

: 这个还是一瓶一瓶灌比较省老鼠吧？
: 要不然，两瓶一混，老鼠死了，拿出一瓶灌，老鼠还是死了，你还得灌剩下那瓶，结果
: 又死了，弄死三个才鉴别出两瓶，更浪费了。

s*e2013-05-16 07:05

23 楼

HMM需要动态规划，现场写也没有那么难，不过你的确得对整个过程非常清晰。我过去
面试时候现场写过，感觉还可以，不过是因为我是做nlp的，写过太多遍了。。
但是你这个不是，你的就是简单的language model. 所有的规则都是bigram，最大似然
估计。
第一个规则就是条件概率，前一个字符是START，后一个是'a'的概率
P(c_current ='a' | c_previous = START) = #(START a)/#(START)
#代表数字，(START a)代表一个sequence
后面的规则按照此办理就可以了。所以这个问题就是问你，如何统计一个文章中所有字
符出现的次数和所有二字符序列出现的顺序。
可能他解释得不好，否则这个问题根本就是放水啊。。。。我要是面试时候能问我这么
简单的问题就好了。。。

a*a2013-05-16 07:05

24 楼

要是只有1瓶没毒呢？你二分怎么把那瓶没毒的找出来？要废掉多少老鼠？

【在 s*i 的大作中提到】

: 显然不是啦。比如最多就1瓶有毒。总共16瓶。你的方法最差情况要测试16次呢。
: 二分法最多9次就搞定了

t*52013-05-16 07:05

25 楼

做一个28X28矩阵M。26字符加头尾。M(x,y)是x后面跟y的概率。每一行概率和为1。所
以“Markov"。不过不用管这个名字啦。
所以问题就是怎么走一边list，把这个矩阵做出来。

s*i2013-05-16 07:05

26 楼

有道理。我改了原文。改成用老鼠的次数。

[发表自未名空间手机版 - m.mitbbs.com]

【在 J**0 的大作中提到】

: 问题是你要省老鼠，不是省灌的次数

j*e2013-05-16 07:05

27 楼

可以一边走一边counting，最后再scan你的matrix来算概率

【在 t**5 的大作中提到】

: 做一个28X28矩阵M。26字符加头尾。M(x,y)是x后面跟y的概率。每一行概率和为1。所
: 以“Markov"。不过不用管这个名字啦。
: 所以问题就是怎么走一边list，把这个矩阵做出来。

s*i2013-05-16 07:05

28 楼

按照某牛的做法：
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
灌四只老鼠，按列混合。根据结果可以得出哪个有毒的。

[发表自未名空间手机版 - m.mitbbs.com]

【在 a***a 的大作中提到】

: 要是只有1瓶没毒呢？你二分怎么把那瓶没毒的找出来？要废掉多少老鼠？

l*82013-05-16 07:05

29 楼

good idea!

【在 t**5 的大作中提到】

: 做一个28X28矩阵M。26字符加头尾。M(x,y)是x后面跟y的概率。每一行概率和为1。所
: 以“Markov"。不过不用管这个名字啦。
: 所以问题就是怎么走一边list，把这个矩阵做出来。

j*k2013-05-16 07:05

30 楼

http://www.matrix67.com/blog/archives/4361/comment-page-2
大家应该都听说过这个老题目：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的
水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只
小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10
位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子，让第二只老鼠
喝掉所有二进制数右起第二位是 1 的瓶子，等等。一星期后，如果第一只老鼠死了，
就知道毒药瓶子的二进制编号中，右起第一位是 1 ；如果第二只老鼠没死，就知道毒
药瓶子的二进制编号中，右起第二位是 0 ……每只老鼠的死活都能确定出 10 位二进
制数的其中一位，由此便可知道毒药瓶子的编号
了。
现在，有意思的问题来了：如果你有两个星期的时间（换句话说你可以做两轮实验
），为了从 1000 个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死
掉的老鼠，就无法继续参与第二次实验了。
答案：7 只老鼠就足够了。事实上，7 只老鼠足以从 37 = 2187 个瓶子中找出毒
药来。首先，把所有瓶子从 0 到 2186 编号，然后全部转换为 7 位三进制数。现在，
让第一只老鼠喝掉所有三进制数右起第一位是 2 的瓶子，让第二只老鼠喝掉所有三进
制数右起第二位是 2 的瓶子，等等。一星期之后，如果第一只老鼠死了，就知道毒药
瓶子的三进制编号中，右起第一位是 2 ；如果第二只老鼠没死，就知道毒药瓶子的三
进制编号中，右起第二位不是 2，只可能是 0 或者 1 ……也就是说，每只死掉的老鼠
都用自己的生命确定出了，三进制编号中自己负责的那一位是 2 ；但每只活着的老鼠
都只能确定，它所负责的那一位不是 2 。于是，问题就归约到了只剩一个星期时的情
况。在第二轮实验里，让每只活着的老鼠继续自己未完成的任务，喝掉它负责的那一位
是 1 的所有瓶子。再过一星期，毒药瓶子的三进制编号便能全部揭晓了。
类似地，我们可以证明， n 只小白鼠 t 周的时间可以从 (t+1)n 个瓶子中检验出
毒药来。

d*32013-05-16 07:05

31 楼

Could you tell me why it is a 28X28 matrix, but not 26X26 ? I thought it
was 26X26 ...

【在 t**5 的大作中提到】

: 做一个28X28矩阵M。26字符加头尾。M(x,y)是x后面跟y的概率。每一行概率和为1。所
: 以“Markov"。不过不用管这个名字啦。
: 所以问题就是怎么走一边list，把这个矩阵做出来。

f*i2013-05-16 07:05

32 楼

以前大概看过这类解法，楼主给的条件太宽泛了

10

【在 j****k 的大作中提到】

: http://www.matrix67.com/blog/archives/4361/comment-page-2
: 大家应该都听说过这个老题目：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的
: 水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只
: 小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
: 这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10
: 位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子，让第二只老鼠
: 喝掉所有二进制数右起第二位是 1 的瓶子，等等。一星期后，如果第一只老鼠死了，
: 就知道毒药瓶子的二进制编号中，右起第一位是 1 ；如果第二只老鼠没死，就知道毒
: 药瓶子的二进制编号中，右起第二位是 0 ……每只老鼠的死活都能确定出 10 位二进
: 制数的其中一位，由此便可知道毒药瓶子的编号

p*k2013-05-16 07:05

33 楼

日死印度人，阿三臭逼

J*02013-05-16 07:05

34 楼

但m可以等于upto n-1：）

【在 s*i 的大作中提到】

: 有道理。我改了原文。改成用老鼠的次数。
:
: [发表自未名空间手机版 - m.mitbbs.com]

g*72013-05-16 07:05

35 楼

这个标题太歧义了.

state

【在 l***n 的大作中提到】

: 烙印面试居然问我Markov chain 之类的coding 解法，我当场傻掉。
: given a list of words ["apple", "apce", appe"]
: 写个函数之类的，可以产生一些rules:
: like:
: 1. first letter is 'a' 100%
: 2. last letter is 'e' 100%
: 3. p followed by l 33%
: 3. p followed by c 33%
: ......
: 他想要Markov chain ,概率方面的方向去做。我都说我不是ml 方向的，要画一个state

r*n2013-05-16 07:05

36 楼

log(n)只老鼠
这是PDA版学术化的开端吗？

【在 s*i 的大作中提到】

: 现有酒 n 瓶。其中可能有少量几瓶（m）含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。

S*r2013-05-16 07:05

37 楼

就是考你动态规划啊

state

【在 l***n 的大作中提到】

: 烙印面试居然问我Markov chain 之类的coding 解法，我当场傻掉。
: given a list of words ["apple", "apce", appe"]
: 写个函数之类的，可以产生一些rules:
: like:
: 1. first letter is 'a' 100%
: 2. last letter is 'e' 100%
: 3. p followed by l 33%
: 3. p followed by c 33%
: ......
: 他想要Markov chain ,概率方面的方向去做。我都说我不是ml 方向的，要画一个state

M*n2013-05-16 07:05

38 楼

m不等于1哦

【在 r*********n 的大作中提到】

: log(n)只老鼠
: 这是PDA版学术化的开端吗？

r*n2013-05-16 07:05

39 楼

这个题就是典型的马额科夫连。 tk45说的很对。28*28是因为头尾要加两个状态。然后
就扫描字符，每扫描过一个，在相应cell 加1。比如 ”but “ 要在开始－> b 的
cell加1, b－> u的 cell 加1，。。。t －> 中止 cell 加1 。最后把每列normalize
一下就行了。不用HHM，动态规划什么，哪有那么复杂。复杂度是O（n）。 n是字符
数。

it

【在 d******3 的大作中提到】

: Could you tell me why it is a 28X28 matrix, but not 26X26 ? I thought it
: was 26X26 ...

n*72013-05-16 07:05

40 楼

你显然是千老
因为m是不确定的，所以跟你这里说的完全不是一回事

【在 s*i 的大作中提到】

: 显然不是啦。比如最多就1瓶有毒。总共16瓶。你的方法最差情况要测试16次呢。
: 二分法最多9次就搞定了

t*52013-05-16 07:05

41 楼

这个倒也是。如果要问“x后面任何字符再跟y“之类的就是动态规划了。也可以直接用
矩阵算啦，Markov过程。还记得条件概率的话想想M＊M[x,y]是啥，也就想出来了。
记得G有个面试题，很早了，怎么算组合数n取m，必须用动态规划。呵呵，没有那个规
定咱直接给他公式了。

【在 S*********r 的大作中提到】

: 就是考你动态规划啊
:
: state

t*t2013-05-16 07:05

42 楼

上ICP，一个老鼠都不要。

【在 s*i 的大作中提到】

: 现有酒 n 瓶。其中可能有少量几瓶（m）含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。

l*n2013-05-16 07:05

43 楼

高人！

【在 t**5 的大作中提到】

: 这个倒也是。如果要问“x后面任何字符再跟y“之类的就是动态规划了。也可以直接用
: 矩阵算啦，Markov过程。还记得条件概率的话想想M＊M[x,y]是啥，也就想出来了。
: 记得G有个面试题，很早了，怎么算组合数n取m，必须用动态规划。呵呵，没有那个规
: 定咱直接给他公式了。

a*e2013-05-16 07:05

44 楼

一瓶有毒4次搞定吧

【在 s*i 的大作中提到】

: 显然不是啦。比如最多就1瓶有毒。总共16瓶。你的方法最差情况要测试16次呢。
: 二分法最多9次就搞定了

t*52013-05-16 07:05

45 楼

呵呵，其实是我自己还记得Markov过程是啥样子的，所以就有思路。阿三告诉你Markov
过程，你恰好知道就是提示，你不知道就是被心理战了。这种时候最好不要理他，就说
“让我一个人想几分钟”。
我碰到过类似的。两个人面我。白人还不错，阿三老是打岔。无所谓了，算是长经验，
那公司去不成是运气。

【在 l***n 的大作中提到】

: 高人！

l*s2013-05-16 07:05

46 楼

F(n,m) = 当m为已知数时，最少试验次数。
T(n,m) = 当m为已知上限时，1为下限时，最少试验次数。
F(n,m)=MIN{ F1(n,m), F2(n,m),…}
T(n,m)=MIN{ T1(n,m), T2(n,m),…}
F1,T1: 逐瓶试验，
F2,T2: 两分法。
其他方法估计不会优于这两种方法中较少的试验次数。
F1(n,m) =n-m,
T1(n,m) =n-1,
F2(n,1) =log2(n)
F2(n,m)=2*(m-1)*( log2(n)-P)+2^(P+1)-2, P=CEIL[log2(m-1)]
T2(n,m)= F2(n,m)+m-1
有按照可能的试验结果给出 F(n,m)=log2[C(n,m)],
这是理论上的最低上限，但除了m=1, 设计不出可行的方案。
最简单的例子是n=4, m=3. log2[C(4,3)]= log2[4]=2. 设计不出可行的2次试验的方
案。

h*o2013-05-16 07:05

47 楼

草，你不会连古典概率都没学过，不会算吧

state

【在 l***n 的大作中提到】

: 烙印面试居然问我Markov chain 之类的coding 解法，我当场傻掉。
: given a list of words ["apple", "apce", appe"]
: 写个函数之类的，可以产生一些rules:
: like:
: 1. first letter is 'a' 100%
: 2. last letter is 'e' 100%
: 3. p followed by l 33%
: 3. p followed by c 33%
: ......
: 他想要Markov chain ,概率方面的方向去做。我都说我不是ml 方向的，要画一个state

s*i2013-05-16 07:05

48 楼

大牛！赞。我觉得最后一个例子特别说明问题。

【在 l*******s 的大作中提到】

: F(n,m) = 当m为已知数时，最少试验次数。
: T(n,m) = 当m为已知上限时，1为下限时，最少试验次数。
: F(n,m)=MIN{ F1(n,m), F2(n,m),…}
: T(n,m)=MIN{ T1(n,m), T2(n,m),…}
: F1,T1: 逐瓶试验，
: F2,T2: 两分法。
: 其他方法估计不会优于这两种方法中较少的试验次数。
: F1(n,m) =n-m,
: T1(n,m) =n-1,
: F2(n,1) =log2(n)

s*n2013-05-16 07:05

49 楼

估计问你Viterbi decoder.
你面什么方向。这个不是随便问。
这题好像很简单。
整个matrix搞定。

state

【在 l***n 的大作中提到】

: 烙印面试居然问我Markov chain 之类的coding 解法，我当场傻掉。
: given a list of words ["apple", "apce", appe"]
: 写个函数之类的，可以产生一些rules:
: like:
: 1. first letter is 'a' 100%
: 2. last letter is 'e' 100%
: 3. p followed by l 33%
: 3. p followed by c 33%
: ......
: 他想要Markov chain ,概率方面的方向去做。我都说我不是ml 方向的，要画一个state

s*n2013-05-16 07:05

50 楼

楼主好像没有明白markov过程的意义。就是t0状态唯一决定t1.这样不需要考虑历史。
简单多了。
一般markov都是用矩阵的。
我个人认为烙印给你了很强的暗示。当然，也可能是误导。如果你没这方面的背景的话。

state

【在 l***n 的大作中提到】

: 烙印面试居然问我Markov chain 之类的coding 解法，我当场傻掉。
: given a list of words ["apple", "apce", appe"]
: 写个函数之类的，可以产生一些rules:
: like:
: 1. first letter is 'a' 100%
: 2. last letter is 'e' 100%
: 3. p followed by l 33%
: 3. p followed by c 33%
: ......
: 他想要Markov chain ,概率方面的方向去做。我都说我不是ml 方向的，要画一个state

l*n2013-05-16 07:05

51 楼

现在回想，的确不是很难，只是我对markov chain 定义不了解。没想到用matrix, 小
弟学艺不精。

话。

【在 s*****n 的大作中提到】

: 楼主好像没有明白markov过程的意义。就是t0状态唯一决定t1.这样不需要考虑历史。
: 简单多了。
: 一般markov都是用矩阵的。
: 我个人认为烙印给你了很强的暗示。当然，也可能是误导。如果你没这方面的背景的话。
:
: state

p*t2013-05-16 07:05

52 楼

这都什么题啊,实际工作中会用到吗?这是招数学专业的还是码工?

state

【在 l***n 的大作中提到】

: 烙印面试居然问我Markov chain 之类的coding 解法，我当场傻掉。
: given a list of words ["apple", "apce", appe"]
: 写个函数之类的，可以产生一些rules:
: like:
: 1. first letter is 'a' 100%
: 2. last letter is 'e' 100%
: 3. p followed by l 33%
: 3. p followed by c 33%
: ......
: 他想要Markov chain ,概率方面的方向去做。我都说我不是ml 方向的，要画一个state

y*g2013-05-16 07:05

53 楼

那要么问实际工作能遇到的？比如debug一下gfs的failure ？

【在 p*********t 的大作中提到】

: 这都什么题啊,实际工作中会用到吗?这是招数学专业的还是码工?
:
: state