g*****t
发帖数: 42 | 1 两个array, 要找公共elements, 没有duplicate
我说用bitmap
他说是sorted，
我说用for循环， O(n+m)
他说其中一个比另一个长的多
我说用binary search
他说那个长的太长了， 没办法放memory里，
我说还用binary search
他说要做一下preprocessing
还说了些提示， 实在听不清楚， 就换题了。
有没有高人给点拨一下？ |
w******1
发帖数: 520 | 2 这两个array 是 0 1 组成的还是 其他数字组成的， 还是字母组成的？ |
g*****t
发帖数: 42 | 3 integer
array 中间假设没有duplicate. |
x***y
发帖数: 633 | 4 build a B+ tree for the long array...
【在 g*****t 的大作中提到】
: 两个array, 要找公共elements, 没有duplicate
: 我说用bitmap
: 他说是sorted，
: 我说用for循环， O(n+m)
: 他说其中一个比另一个长的多
: 我说用binary search
: 他说那个长的太长了， 没办法放memory里，
: 我说还用binary search
: 他说要做一下preprocessing
: 还说了些提示， 实在听不清楚， 就换题了。
|
r******e
发帖数: 37 | 5 这位面试官的目的是要你分析各种方法的优劣以及针对不同情况的不同对待。即使你能
给已给所谓的完美答案而没有分析 也是没有用的，要分析 分析 |
g*****t
发帖数: 42 | 6 thanks.
【在 x***y 的大作中提到】
: build a B+ tree for the long array...
|
w******1
发帖数: 520 | 7 下午刚看了B+树， 还想呢， 这样的东西不会被问到。
结果可真就用到了 |
s*********t
发帖数: 1663 | 8 有没有大牛能详细讲解一下此题的答案？
感觉很经典的样子
【在 g*****t 的大作中提到】
: 两个array, 要找公共elements, 没有duplicate
: 我说用bitmap
: 他说是sorted，
: 我说用for循环， O(n+m)
: 他说其中一个比另一个长的多
: 我说用binary search
: 他说那个长的太长了， 没办法放memory里，
: 我说还用binary search
: 他说要做一下preprocessing
: 还说了些提示， 实在听不清楚， 就换题了。
|
g*****t
发帖数: 42 | 9 其实下一个题也很有意思， 开始我听的是， 说一个村里， 1%的人是真得病了， 用药
试10%的机会会给错误的结果。 抓来一个人一试， 反应positive, 问这个人真得病的
概率。
我说假设村里1000个人， 10个人真的病了， 用药能试出9个来， 990个人没得病， 用
药试出99个人来。 所以这个人真得病的概率大概是8%吧。
结果他说如果这人有病， 药会给出80%的positive, 如果没病， 会有10%的positive。
我没反应过来这药怎么对有病没病概率还不一样。 加上面试官印度口音太重， 他手
机信号也不好， 背景还有杂音， 我听的那个着急呀。
不过被拒也没关系， 水平不够, 愿不得别人。 |
H*M
发帖数: 1268 | 10 这个不就是个经典的Beyes公式嘛
【在 g*****t 的大作中提到】
: 其实下一个题也很有意思， 开始我听的是， 说一个村里， 1%的人是真得病了， 用药
: 试10%的机会会给错误的结果。 抓来一个人一试， 反应positive, 问这个人真得病的
: 概率。
: 我说假设村里1000个人， 10个人真的病了， 用药能试出9个来， 990个人没得病， 用
: 药试出99个人来。 所以这个人真得病的概率大概是8%吧。
: 结果他说如果这人有病， 药会给出80%的positive, 如果没病， 会有10%的positive。
: 我没反应过来这药怎么对有病没病概率还不一样。 加上面试官印度口音太重， 他手
: 机信号也不好， 背景还有杂音， 我听的那个着急呀。
: 不过被拒也没关系， 水平不够, 愿不得别人。
|
|
|
d*******8
发帖数: 785 | 11 是啊，应该就是 90%×1%/ （90%×1% + 10%×99%）
面试官那个得病确诊是80%怎么搞出来的？
【在 H*M 的大作中提到】
: 这个不就是个经典的Beyes公式嘛
|
m****u
发帖数: 3915 | 12 我觉得你说的是对的
【在 g*****t 的大作中提到】
: 其实下一个题也很有意思， 开始我听的是， 说一个村里， 1%的人是真得病了， 用药
: 试10%的机会会给错误的结果。 抓来一个人一试， 反应positive, 问这个人真得病的
: 概率。
: 我说假设村里1000个人， 10个人真的病了， 用药能试出9个来， 990个人没得病， 用
: 药试出99个人来。 所以这个人真得病的概率大概是8%吧。
: 结果他说如果这人有病， 药会给出80%的positive, 如果没病， 会有10%的positive。
: 我没反应过来这药怎么对有病没病概率还不一样。 加上面试官印度口音太重， 他手
: 机信号也不好， 背景还有杂音， 我听的那个着急呀。
: 不过被拒也没关系， 水平不够, 愿不得别人。
|
d******a
发帖数: 238 | 13 为什么不用merge sort(external sorting)的思想？如果1个比另一个长很多，当短的
数组遍历完后，就直接结束了。也不用把数组放在内存中。
【在 g*****t 的大作中提到】
: 两个array, 要找公共elements, 没有duplicate
: 我说用bitmap
: 他说是sorted，
: 我说用for循环， O(n+m)
: 他说其中一个比另一个长的多
: 我说用binary search
: 他说那个长的太长了， 没办法放memory里，
: 我说还用binary search
: 他说要做一下preprocessing
: 还说了些提示， 实在听不清楚， 就换题了。
|
r********g
发帖数: 1351 | 14 这个统计我觉得很绕...记得有个概念叫sensitivity & specification. value
prediction里
面把prediction分成四类：
TP （ture positive）：预测得病，结果正确
FP （false positive）: 预测得病，结果错误
TN (true negative): 预测没病，结果正确
FN （false negative）: 预测没病，结果错误
得病的人：TP+FN
第二个例子应该就是：
TP/(TP+FN) = 0.8
FP/(TN+FP) = 0.1
【在 g*****t 的大作中提到】
: 其实下一个题也很有意思， 开始我听的是， 说一个村里， 1%的人是真得病了， 用药
: 试10%的机会会给错误的结果。 抓来一个人一试， 反应positive, 问这个人真得病的
: 概率。
: 我说假设村里1000个人， 10个人真的病了， 用药能试出9个来， 990个人没得病， 用
: 药试出99个人来。 所以这个人真得病的概率大概是8%吧。
: 结果他说如果这人有病， 药会给出80%的positive, 如果没病， 会有10%的positive。
: 我没反应过来这药怎么对有病没病概率还不一样。 加上面试官印度口音太重， 他手
: 机信号也不好， 背景还有杂音， 我听的那个着急呀。
: 不过被拒也没关系， 水平不够, 愿不得别人。
|
a******t
发帖数: 34 | 15 搂主有统计背景吗？还是任何人都有可能遇到统计问题？ |
m****u
发帖数: 3915 | 16 这是简单的概率问题，我觉得任何人都可能遇到
【在 a******t 的大作中提到】
: 搂主有统计背景吗？还是任何人都有可能遇到统计问题？
|
k***e
发帖数: 556 | 17 学过machine learning 或者 pattern recognition就应该会做
没学过的话。。。
【在 a******t 的大作中提到】
: 搂主有统计背景吗？还是任何人都有可能遇到统计问题？
|
b******v
发帖数: 1493 | 18 Bayes公式
P(ill | pos)
= P(ill, pos) / P(pos)
= P(pos | ill) * P(ill) / [P(pos | ill)* P(ill) + P(pos | nonill)*P(nonill)]
= 0.8*0.01/[0.8*0.01+0.1*0.99]
= 8/(8+99)
= 8/107
大约是7.48%
【在 g*****t 的大作中提到】
: 其实下一个题也很有意思， 开始我听的是， 说一个村里， 1%的人是真得病了， 用药
: 试10%的机会会给错误的结果。 抓来一个人一试， 反应positive, 问这个人真得病的
: 概率。
: 我说假设村里1000个人， 10个人真的病了， 用药能试出9个来， 990个人没得病， 用
: 药试出99个人来。 所以这个人真得病的概率大概是8%吧。
: 结果他说如果这人有病， 药会给出80%的positive, 如果没病， 会有10%的positive。
: 我没反应过来这药怎么对有病没病概率还不一样。 加上面试官印度口音太重， 他手
: 机信号也不好， 背景还有杂音， 我听的那个着急呀。
: 不过被拒也没关系， 水平不够, 愿不得别人。
|
c**********n
发帖数: 516 | 19 re
)]
【在 b******v 的大作中提到】
: Bayes公式
: P(ill | pos)
: = P(ill, pos) / P(pos)
: = P(pos | ill) * P(ill) / [P(pos | ill)* P(ill) + P(pos | nonill)*P(nonill)]
: = 0.8*0.01/[0.8*0.01+0.1*0.99]
: = 8/(8+99)
: = 8/107
: 大约是7.48%
|
g*****t
发帖数: 42 | 20
倒是希望自己有些背景， 可惜啥都没有。
【在 a******t 的大作中提到】
: 搂主有统计背景吗？还是任何人都有可能遇到统计问题？
|
|
|
g*****t
发帖数: 42 | 21
)]
这就是我最后给的答案， 看样子蒙对了？
【在 b******v 的大作中提到】
: Bayes公式
: P(ill | pos)
: = P(ill, pos) / P(pos)
: = P(pos | ill) * P(ill) / [P(pos | ill)* P(ill) + P(pos | nonill)*P(nonill)]
: = 0.8*0.01/[0.8*0.01+0.1*0.99]
: = 8/(8+99)
: = 8/107
: 大约是7.48%
|
h*******x
发帖数: 12808 | 22 我怎么觉得这是先验概率求后验概率的问题啊，设I为一个人得病事件，R为检测呈阳性。
已知：P(I)=0.01,P(R|I）=0.9，让你求P(I|R).
P(I|R) = P(IR) / P(R)
P(IR)＝ Ｐ(I)*P(R|I) = 0.01*0.9 = 0.009
P(R)=P(I)*P(R|I) + [1-P(I)]*[1-P(R|I)] = 0.009+(1-0.01)*(1-0.9)=0.009+0.009=
0.108.
P(I|R)=0.009 / 0.108 = 8.33%
所以其实这个人得病概率还是不大，而且你懵的很准。
【在 g*****t 的大作中提到】
: 其实下一个题也很有意思， 开始我听的是， 说一个村里， 1%的人是真得病了， 用药
: 试10%的机会会给错误的结果。 抓来一个人一试， 反应positive, 问这个人真得病的
: 概率。
: 我说假设村里1000个人， 10个人真的病了， 用药能试出9个来， 990个人没得病， 用
: 药试出99个人来。 所以这个人真得病的概率大概是8%吧。
: 结果他说如果这人有病， 药会给出80%的positive, 如果没病， 会有10%的positive。
: 我没反应过来这药怎么对有病没病概率还不一样。 加上面试官印度口音太重， 他手
: 机信号也不好， 背景还有杂音， 我听的那个着急呀。
: 不过被拒也没关系， 水平不够, 愿不得别人。
|
h*******x
发帖数: 12808 | 23 对啊，就应该是这个结果啊。还是你牛啊，我还推导了半天，惭愧啊。
一般印度人考数学，都是这样。
【在 d*******8 的大作中提到】
: 是啊，应该就是 90%×1%/ （90%×1% + 10%×99%）
: 面试官那个得病确诊是80%怎么搞出来的？
|
h*******x
发帖数: 12808 | 24 你好像带错数了？
)]
用药
病的
， 用
positive。
他手
【在 b******v 的大作中提到】
: Bayes公式
: P(ill | pos)
: = P(ill, pos) / P(pos)
: = P(pos | ill) * P(ill) / [P(pos | ill)* P(ill) + P(pos | nonill)*P(nonill)]
: = 0.8*0.01/[0.8*0.01+0.1*0.99]
: = 8/(8+99)
: = 8/107
: 大约是7.48%
|
d*******8
发帖数: 785 | 25 汗。。我就对照了下贝叶斯公式。。以前面试的时候被考过..
【在 h*******x 的大作中提到】
: 对啊，就应该是这个结果啊。还是你牛啊，我还推导了半天，惭愧啊。
: 一般印度人考数学，都是这样。
|
s*********t
发帖数: 1663 | 26 唉，想来想去都觉得还是90%。。
我太弱智了
【在 h*******x 的大作中提到】
: 对啊，就应该是这个结果啊。还是你牛啊，我还推导了半天，惭愧啊。
: 一般印度人考数学，都是这样。
|
b******n
发帖数: 823 | 27 不用build B+ tree吧，假设内存可以放M个item，
每次从大array里面读M个数，然后用小array的数顺序在M里面做binary search，直到
小array中读出的数大于M中最后那个；再重复读M个数。。。
复杂度O(mlogM) <= O(m logn)
如果M是常数，复杂度O(m),但是I/O有O(n) |
