大家喜欢open floor plan吗？ - 未名空间MITBBS历史存档

大家喜欢open floor plan吗？# Living

g*t2009-12-31 08:12

1 楼

两个array, 要找公共elements, 没有duplicate
我说用bitmap
他说是sorted，
我说用for循环， O(n+m)
他说其中一个比另一个长的多
我说用binary search
他说那个长的太长了，没办法放memory里，
我说还用binary search
他说要做一下preprocessing
还说了些提示，实在听不清楚，就换题了。
有没有高人给点拨一下？

z*t2009-12-31 08:12

2 楼

RT，站内PM

q*n2009-12-31 08:12

3 楼

看上一个房子，挺漂亮的。但是有点纠结它的floor plan，我是喜欢open一点的，但是
它太open了，dining room就一面墙，其他都是柱子，厨房连着family room，family
room 背后就是living room，但是living room，连着的墙面挖了两拱门形状的洞。就
是感觉墙太少，不太好放东西。lg觉得太open了，有点不太隐私。比如开party，打牌
小组和ktv、wii小组会互相干扰。
而且厨房太open，做饭会有油。
问问大家，大家都喜欢这么open的layout吗？

w*12009-12-31 08:12

4 楼

这两个array 是 0 1 组成的还是其他数字组成的，还是字母组成的？

r*o2009-12-31 08:12

5 楼

自己加道墙也不是多难的事，比拆墙容易

g*t2009-12-31 08:12

6 楼

integer
array 中间假设没有duplicate.

f*s2009-12-31 08:12

7 楼

太open,我不太喜欢。可是resale可能不错。

x*y2009-12-31 08:12

8 楼

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
: 还说了些提示，实在听不清楚，就换题了。

z*n2009-12-31 08:12

9 楼

party不怕open吧，又不是学习小组。open还显得更热闹

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

: 看上一个房子，挺漂亮的。但是有点纠结它的floor plan，我是喜欢open一点的，但是
: 它太open了，dining room就一面墙，其他都是柱子，厨房连着family room，family
: room 背后就是living room，但是living room，连着的墙面挖了两拱门形状的洞。就
: 是感觉墙太少，不太好放东西。lg觉得太open了，有点不太隐私。比如开party，打牌
: 小组和ktv、wii小组会互相干扰。
: 而且厨房太open，做饭会有油。
: 问问大家，大家都喜欢这么open的layout吗？

r*e2009-12-31 08:12

10 楼

这位面试官的目的是要你分析各种方法的优劣以及针对不同情况的不同对待。即使你能
给已给所谓的完美答案而没有分析也是没有用的，要分析分析

q*n2009-12-31 08:12

11 楼

有道理！不知道这种open的刷漆是不是都要一个颜色才协调啊？

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

: party不怕open吧，又不是学习小组。open还显得更热闹

g*t2009-12-31 08:12

12 楼

thanks.

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

: build a B+ tree for the long array...

h*y2009-12-31 08:12

13 楼

我就喜欢这样的。我也喜欢设计的时候把承重墙用柱子代替
你看的这个是custom home吧，我没见过一般的tract home这么建的

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

: 看上一个房子，挺漂亮的。但是有点纠结它的floor plan，我是喜欢open一点的，但是
: 它太open了，dining room就一面墙，其他都是柱子，厨房连着family room，family
: room 背后就是living room，但是living room，连着的墙面挖了两拱门形状的洞。就
: 是感觉墙太少，不太好放东西。lg觉得太open了，有点不太隐私。比如开party，打牌
: 小组和ktv、wii小组会互相干扰。
: 而且厨房太open，做饭会有油。
: 问问大家，大家都喜欢这么open的layout吗？

w*12009-12-31 08:12

14 楼

下午刚看了B+树，还想呢，这样的东西不会被问到。
结果可真就用到了

j*u2009-12-31 08:12

15 楼

这不更好吗

s*t2009-12-31 08:12

16 楼

有没有大牛能详细讲解一下此题的答案？
感觉很经典的样子

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

: 两个array, 要找公共elements, 没有duplicate
: 我说用bitmap
: 他说是sorted，
: 我说用for循环， O(n+m)
: 他说其中一个比另一个长的多
: 我说用binary search
: 他说那个长的太长了，没办法放memory里，
: 我说还用binary search
: 他说要做一下preprocessing
: 还说了些提示，实在听不清楚，就换题了。

g*t2009-12-31 08:12

17 楼

其实下一个题也很有意思，开始我听的是，说一个村里， 1%的人是真得病了，用药
试10%的机会会给错误的结果。抓来一个人一试，反应positive, 问这个人真得病的
概率。
我说假设村里1000个人， 10个人真的病了，用药能试出9个来， 990个人没得病，用
药试出99个人来。所以这个人真得病的概率大概是8%吧。
结果他说如果这人有病，药会给出80%的positive, 如果没病，会有10%的positive。
我没反应过来这药怎么对有病没病概率还不一样。加上面试官印度口音太重，他手
机信号也不好，背景还有杂音，我听的那个着急呀。
不过被拒也没关系，水平不够, 愿不得别人。

H*M2009-12-31 08:12

18 楼

这个不就是个经典的Beyes公式嘛

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

: 其实下一个题也很有意思，开始我听的是，说一个村里， 1%的人是真得病了，用药
: 试10%的机会会给错误的结果。抓来一个人一试，反应positive, 问这个人真得病的
: 概率。
: 我说假设村里1000个人， 10个人真的病了，用药能试出9个来， 990个人没得病，用
: 药试出99个人来。所以这个人真得病的概率大概是8%吧。
: 结果他说如果这人有病，药会给出80%的positive, 如果没病，会有10%的positive。
: 我没反应过来这药怎么对有病没病概率还不一样。加上面试官印度口音太重，他手
: 机信号也不好，背景还有杂音，我听的那个着急呀。
: 不过被拒也没关系，水平不够, 愿不得别人。

d*82009-12-31 08:12

19 楼

是啊，应该就是 90%×1%/ （90%×1% + 10%×99%）
面试官那个得病确诊是80%怎么搞出来的？

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

: 这个不就是个经典的Beyes公式嘛

m*u2009-12-31 08:12

20 楼

我觉得你说的是对的

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

: 其实下一个题也很有意思，开始我听的是，说一个村里， 1%的人是真得病了，用药
: 试10%的机会会给错误的结果。抓来一个人一试，反应positive, 问这个人真得病的
: 概率。
: 我说假设村里1000个人， 10个人真的病了，用药能试出9个来， 990个人没得病，用
: 药试出99个人来。所以这个人真得病的概率大概是8%吧。
: 结果他说如果这人有病，药会给出80%的positive, 如果没病，会有10%的positive。
: 我没反应过来这药怎么对有病没病概率还不一样。加上面试官印度口音太重，他手
: 机信号也不好，背景还有杂音，我听的那个着急呀。
: 不过被拒也没关系，水平不够, 愿不得别人。

d*a2009-12-31 08:12

21 楼

为什么不用merge sort(external sorting)的思想？如果1个比另一个长很多，当短的
数组遍历完后，就直接结束了。也不用把数组放在内存中。

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

: 两个array, 要找公共elements, 没有duplicate
: 我说用bitmap
: 他说是sorted，
: 我说用for循环， O(n+m)
: 他说其中一个比另一个长的多
: 我说用binary search
: 他说那个长的太长了，没办法放memory里，
: 我说还用binary search
: 他说要做一下preprocessing
: 还说了些提示，实在听不清楚，就换题了。

r*g2009-12-31 08:12

22 楼

这个统计我觉得很绕...记得有个概念叫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*t2009-12-31 08:12

23 楼

搂主有统计背景吗？还是任何人都有可能遇到统计问题？

m*u2009-12-31 08:12

24 楼

这是简单的概率问题，我觉得任何人都可能遇到

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

: 搂主有统计背景吗？还是任何人都有可能遇到统计问题？

k*e2009-12-31 08:12

25 楼

学过machine learning 或者 pattern recognition就应该会做
没学过的话。。。

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

: 搂主有统计背景吗？还是任何人都有可能遇到统计问题？

b*v2009-12-31 08:12

26 楼

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*n2009-12-31 08:12

27 楼

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*t2009-12-31 08:12

28 楼

倒是希望自己有些背景，可惜啥都没有。

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

: 搂主有统计背景吗？还是任何人都有可能遇到统计问题？

g*t2009-12-31 08:12

29 楼

)]
这就是我最后给的答案，看样子蒙对了？

【在 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*x2009-12-31 08:12

30 楼

: 其实下一个题也很有意思，开始我听的是，说一个村里， 1%的人是真得病了，用药
: 试10%的机会会给错误的结果。抓来一个人一试，反应positive, 问这个人真得病的
: 概率。
: 我说假设村里1000个人， 10个人真的病了，用药能试出9个来， 990个人没得病，用
: 药试出99个人来。所以这个人真得病的概率大概是8%吧。
: 结果他说如果这人有病，药会给出80%的positive, 如果没病，会有10%的positive。
: 我没反应过来这药怎么对有病没病概率还不一样。加上面试官印度口音太重，他手
: 机信号也不好，背景还有杂音，我听的那个着急呀。
: 不过被拒也没关系，水平不够, 愿不得别人。

h*x2009-12-31 08:12

31 楼

对啊，就应该是这个结果啊。还是你牛啊，我还推导了半天，惭愧啊。
一般印度人考数学，都是这样。

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

: 是啊，应该就是 90%×1%/ （90%×1% + 10%×99%）
: 面试官那个得病确诊是80%怎么搞出来的？

h*x2009-12-31 08:12

32 楼

你好像带错数了？

)]
用药
病的
，用
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*82009-12-31 08:12

33 楼

汗。。我就对照了下贝叶斯公式。。以前面试的时候被考过..

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

: 对啊，就应该是这个结果啊。还是你牛啊，我还推导了半天，惭愧啊。
: 一般印度人考数学，都是这样。

s*t2009-12-31 08:12

34 楼

唉，想来想去都觉得还是90%。。
我太弱智了

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

: 对啊，就应该是这个结果啊。还是你牛啊，我还推导了半天，惭愧啊。
: 一般印度人考数学，都是这样。

b*n2009-12-31 08:12

35 楼

不用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)