40道经典DS/ML面试题解答，求指导 - 未名空间MITBBS历史存档

40道经典DS/ML面试题解答，求指导# DataSciences - 数据科学

t*x2015-01-11 08:01

1 楼

亲们，本人就要回国发展了，因此急需出售一些带不走的留学物品。
1.三合一打印机（另外还有一辆mini奶白色的，13款的1.6排量刚开19200公里价钱
方面可以详谈）
2.购物必备小推车
3.女士自行车（8-9成新）5下图尼康d3s相机
4.ZOOM全新山地车(带原装配件)
5.9成新苹果笔记本电脑（ipad3 32G）
6.苹果（iphone6 16G）土豪金 9成新
7.BF专业全套学习资料及CFA原装教材已出
8.双层可折叠餐桌
9.（奥特朗）0即热式电热水器
10.佳能Power shot A620相机
11.洗衣机,吸尘器等全套床上用品
12.9普联0便携式3G转Wifi路由器已出
13.我囤了一套雅思语法、预测、阅读等书籍
14.九阳新款豆浆机（直接打干豆）
15.(瑞美特)折叠餐桌椅,1桌2椅(送餐具）
16.13 英寸 MacBook Air （基本都是8 9成新
17.(安娜苏Anna Sui）（奥利ORLY）(迪奥Dior）已出
18.asio PX-130电钢琴,含琴桌,琴凳
19.课堂必备索尼数码录音笔（SONY）ICD-TX50金属质感
20.台式电脑,型号X64,主板华硕,处理器英特尔
21.Logitech（罗技）Z323音响
22.三星高清平板电视50寸.
23.8成新山地车一辆，牌子为ZOOM，买车者送山地车配件，打气筒，防盗车锁，和雨
披。
24.三菱冰箱,目前为止性能良好,并且一点都不臭,容量也不小
物品太多不能一一上传有物品图片可浏览，这是我的主页http://www.jxjcpm.cn/ETa3v 主页有二手物品照片，价格以及详细介绍,
您看看是否满意,满意请回复谢谢！主页右上角有我的电话，有什么不懂请与我电话联
系！

u*u2015-01-11 08:01

2 楼

发几个美女片片轻松一下 :)
电影里余虹最美的一瞬
余虹在酒吧很吊的样子
旁白：我总是太努力，跑得太远
周伟说，我们分手吧
在宿舍，带上耳机，哈哈笑着，激情重新燃起
余虹和卡拉OK男。“你不喜欢我，我也不喜欢你，但只要你和我在一起。。。”
他们终于相见了，无言，余虹瞟了周伟一眼
李缇的碑文

c*y2015-01-11 08:01

3 楼

25个
外板来吃包子的，必须保证发够10个帖，（水贴不算）

e*n2015-01-11 08:01

4 楼

原题见
http://www.mitbbs.com/article_t/DataSciences/10029.html
专门开一个贴，尝试逐题解答。本人菜鸟，求大牛指导
1. Given a coin you don’t know it’s fair or unfair. Throw it 6 times and
get 1 tail and 5 head. Determine whether it’s fair or not. What’s your
confidence value?
我的答案是：
H0: the coin is fair
Ha: the coin is unfair
X is the number of heads
Rejection region: |X - 3| > 2, i.e., X = 0,1,5,or 6
significance level alpha:
alpha = P(reject H0 | H0 is true)
=P(X=0,1,5,6 | H0 is true)
= (choose(6,0)+choose(6,1)+choose(6,5)+choose(6,6))*(1/2)^6
= (1+6+6+1)*(0.5^6) = 0.21875
because alpha > 0.05, we do not have enough evidence to reject H0, and we
accpte H0, so the coin is fair
confidence value 不知该如何计算，求指教

u*u2015-01-11 08:01

5 楼

谢谢酒妹，删掉了。
女主角郝蕾，东北人
http://zh.wikipedia.org/wiki/%E9%83%9D%E8%95%BE

l*s2015-01-11 08:01

6 楼

恭喜板斧上任！版上再match 25个

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

: 25个
: 外板来吃包子的，必须保证发够10个帖，（水贴不算）

c*22015-01-11 08:01

7 楼

这是一个经典的Hypothesis testing问题吧，LZ说的是exact binomial test.
比较常用的，还有利用Central Limit Theorem构造的test, 也就是intro stat课教的
one sample proportion test, test statistics 就是 Z=(p_hat-p)/ sqrt(p(1-p)/N)
, 比较standard normal distribution就可以。
confidence interval也是可以根据CLT推得。
通常这个问题还有更难的一个版本，就是 p_hat 很小的时候，用CLT是有问题的，具体
的例子比如，ads click rate, 可能10000次里面只有1～2次click，这时候，要估计
confidence interval用CLT是不合适的，这好像也是Google常考面试题之一，具体的改
进方法，可以参考Wilson estimator，或者用Bayes的思路，LZ可以读读Wiki的解释:
http://en.wikipedia.org/wiki/Binomial_proportion_confidence_int

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

: 原题见
: http://www.mitbbs.com/article_t/DataSciences/10029.html
: 专门开一个贴，尝试逐题解答。本人菜鸟，求大牛指导
: 1. Given a coin you don’t know it’s fair or unfair. Throw it 6 times and
: get 1 tail and 5 head. Determine whether it’s fair or not. What’s your
: confidence value?
: 我的答案是：
: H0: the coin is fair
: Ha: the coin is unfair
: X is the number of heads

i*t2015-01-11 08:01

8 楼

又来了。

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

: 发几个美女片片轻松一下 :)
: 电影里余虹最美的一瞬
: 余虹在酒吧很吊的样子
: 旁白：我总是太努力，跑得太远
: 周伟说，我们分手吧
: 在宿舍，带上耳机，哈哈笑着，激情重新燃起
: 余虹和卡拉OK男。“你不喜欢我，我也不喜欢你，但只要你和我在一起。。。”
: 他们终于相见了，无言，余虹瞟了周伟一眼
: 李缇的碑文

k*e2015-01-11 08:01

9 楼

吃！

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

: 25个
: 外板来吃包子的，必须保证发够10个帖，（水贴不算）

l*c2015-01-11 08:01

10 楼

支持等看~~

wh2015-01-11 08:01

11 楼

本版文青静静写过专帖，我觉得写得比电影好看，哈哈。
发信人: stillstill (大不同), 信区: WebRadio
标题: 和
发信站: BBS 未名空间站 (Thu Dec 25 19:49:34 2008), 站内
看这个片的时候，纯粹是冲着禁片的名头去的。我承认我猎奇心重，看到是禁片，就觉
得不看人生都不圆满。电影本身，就情节和结构来说，个人觉得一般般。毕竟有涉及到
敏感话题，点到为止，却又不敢说的太明白。让看的人有种吃馒头堵在嗓子眼，上不来
下不去的感觉。但是对于其中被许多人诟病的频繁出现的性场面，却觉得未必导演只是
企图用这种方式当噱头来吸引眼球。我宁可觉得从这里，看到的是当时那些年轻人内心
的躁动不安和惶恐无助。一方面人们的思想体系被很多外来的东西所冲击，开始不再盲
从正面的政治宣传；另一方面却又不知道怎么去释放这些冲击所带来的压力。
尤其喜欢里面的插曲，有种压抑的躁动感,很奇妙的感觉。

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

: 发几个美女片片轻松一下 :)
: 电影里余虹最美的一瞬
: 余虹在酒吧很吊的样子
: 旁白：我总是太努力，跑得太远
: 周伟说，我们分手吧
: 在宿舍，带上耳机，哈哈笑着，激情重新燃起
: 余虹和卡拉OK男。“你不喜欢我，我也不喜欢你，但只要你和我在一起。。。”
: 他们终于相见了，无言，余虹瞟了周伟一眼
: 李缇的碑文

t*n2015-01-11 08:01

12 楼

re

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

: 25个
: 外板来吃包子的，必须保证发够10个帖，（水贴不算）

t*62015-01-11 08:01

13 楼

第1题可以用Bayes rule吧
Prior：Beta（a,b） *a, b 选择取决于你想让prior多strong
Likelihood: Y~iid Bernouli(p) H~Binomial(n,p) *H is total number of head,
T is total # of tail
Posterior: Beta(a+H, b+T)
至于怎么求Beta(a+H, b+T) 的confidence interval，参见http://stats.stackexchange.com/questions/82475/calculate-the-confidence-interval-for-the-mean-of-a-beta-distribution
1. dbeta() 需用R软件
2. Bootstrap from rbeta() simulation 需用R软件
3. Asymptotic confidence intervals 如楼上所说

wh2015-01-11 08:01

14 楼

这是本版资深专家波哥和呆大的批判：
发信人: iamwhatieat (我吃故我在), 信区: WebRadio
标题: Re: 颐和园
发信站: BBS 未名空间站 (Mon Sep 28 15:00:50 2009, 美东)
这片看完挺难过的，为演员们，真不容易，给这么个烂本子卖肉卖力气，还特投入。。
想起俺们村老实巴交一辈子的父老乡亲们，一年到头脸朝黄土背朝天，汗珠子掉地上摔
八半，种得都是他妈假种子。
看得出来，导演想打造中国版的生命中不能承受之轻啥的，可他以为烧辆军车，扇俩嘴
巴，到柏林跳个楼，点缀些新闻镜头，然后把那些还嫌空的胶片用黑乎乎的传教士姿势
一填，再配上老歌和故作沧桑的旁白，就攒成一史诗了。根子其实还在不诚实，没那个
体验，硬装，结果全是拧巴，骗自己还行，当观众都跟他一样傻叉。
发信人: ngaido (ngaido), 信区: WebRadio
标题: Re: 颐和园
发信站: BBS 未名空间站 (Mon Sep 28 15:26:40 2009, 美东)
Re.
该片与史无关。
导演还是挺用劲的，可惜能力不够。
发信人: iamwhatieat (我

m*72015-01-11 08:01

15 楼

re baozi

t*62015-01-11 08:01

16 楼

我也搭车问40题中的一个rare event的题：
26.If I want to build a classifier, but the data is very unbalanced. I have
a few positive samples but a lot of negative samples. What should I do?
貌似这道题说的就是click through rate/credit fraudulent这种极小概率事件的
training方法。我的思路如下，求大牛指正：
1. Resampling 降噪，但resampling不会降低bias
2. 临床试验里的case control matching 缺点：慢，control subject的选择很
arbitrary
3. Empirical Bayes，prior是empirical_rate.这是目前想到的最靠铺的了，但是没用
过，不知道R和Python有什么好的package没，做过的说说？

s*a2015-01-11 08:01

17 楼

呼唤静静。

c*y2015-01-11 08:01

18 楼

看要求：
”外板来吃包子的，必须保证发够10个帖，（水贴不算）“

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

: re baozi

B*42015-01-11 08:01

19 楼

这个问题我也迷糊了很久，查了不少资料，但还不是100%有把握。希望学统计的来指正
一下。
p-value是说在零假设（H0)之下出现看到该情况或者更极端情况的概率，也就是假设硬
币是fair的，抛6次出现5个head或者6个head的概率。因为我们考虑对称性，所以还要
考虑到1个head或者0个head的情况。楼主的p-value计算是对的。
significance level α只是预先设定的一个判定p-value的阈值（即多小的概率算小概
率事件），如果p<=α，我们认为零假设不对(因为在H0之下居然观察到了一个小概率事
件，肯定假设H0有问题）。反之，如果p>α,我们接受零假设H0。
根据wikipedia "given the availability of a hypothesis testing procedure that
can test the null hypothesis θ = θ0 against the alternative that θ ≠ θ
0 for any value of θ0, then a confidence interval with confidence level γ
= 1 − α can be defined as containing any number θ0 for which the
corresponding null hypothesis is not rejected at significance level α.",如
果我们设定α为5%，则我们可以说confidence level是95%。
但是我觉得这个说法不是面试者真正想要问的答案，因为α是你事先设定的，可以为10
%，5%或1%。但和给的观测结果都没啥关系，仅仅是用来接受还是拒绝假设的。现在我
们求出p-value比较大，所以我们应该接受这个假设硬币是fair的。但究竟这样假设有
多大可能是对的呢？我认为应该用Hoeffding's inequality来求这个confidence value
(confidence level).
假设tail=0, head=1,那么样本均值u为5/6, 而实际均值v为1/2, 差为1/3。根据
Hoeffding's inequality,
Pr(|u-v| > 1/3) <= 2exp(-2*(1/9)*6) = 2/exp(4/3) = 53%
所以confidence value是47%.

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

: 原题见
: http://www.mitbbs.com/article_t/DataSciences/10029.html
: 专门开一个贴，尝试逐题解答。本人菜鸟，求大牛指导
: 1. Given a coin you don’t know it’s fair or unfair. Throw it 6 times and
: get 1 tail and 5 head. Determine whether it’s fair or not. What’s your
: confidence value?
: 我的答案是：
: H0: the coin is fair
: Ha: the coin is unfair
: X is the number of heads

n*o2015-01-11 08:01

20 楼

我最早和九斤同学讨论过一次。话题出现几次，就疲了。

【在 wh 的大作中提到】

: 这是本版资深专家波哥和呆大的批判：
: 发信人: iamwhatieat (我吃故我在), 信区: WebRadio
: 标题: Re: 颐和园
: 发信站: BBS 未名空间站 (Mon Sep 28 15:00:50 2009, 美东)
: 这片看完挺难过的，为演员们，真不容易，给这么个烂本子卖肉卖力气，还特投入。。
: 想起俺们村老实巴交一辈子的父老乡亲们，一年到头脸朝黄土背朝天，汗珠子掉地上摔
: 八半，种得都是他妈假种子。
: 看得出来，导演想打造中国版的生命中不能承受之轻啥的，可他以为烧辆军车，扇俩嘴
: 巴，到柏林跳个楼，点缀些新闻镜头，然后把那些还嫌空的胶片用黑乎乎的传教士姿势
: 一填，再配上老歌和故作沧桑的旁白，就攒成一史诗了。根子其实还在不诚实，没那个

L*k2015-01-11 08:01

21 楼

吃。佛版不算外版吧？

B*42015-01-11 08:01

22 楼

我还有一个解法就是，我们可以不拘泥于significance level α通常为5%，1%。既然
我们算出p-value = 0.22,我们可以把α定为0.22,那么confidence level 为 0.78。
这个和我之前说的47%不矛盾，因为Hoeffding's Inequality得到的是个比较宽松的上
限。

that

【在 B********4 的大作中提到】

: 这个问题我也迷糊了很久，查了不少资料，但还不是100%有把握。希望学统计的来指正
: 一下。
: p-value是说在零假设（H0)之下出现看到该情况或者更极端情况的概率，也就是假设硬
: 币是fair的，抛6次出现5个head或者6个head的概率。因为我们考虑对称性，所以还要
: 考虑到1个head或者0个head的情况。楼主的p-value计算是对的。
: significance level α只是预先设定的一个判定p-value的阈值（即多小的概率算小概
: 率事件），如果p<=α，我们认为零假设不对(因为在H0之下居然观察到了一个小概率事
: 件，肯定假设H0有问题）。反之，如果p>α,我们接受零假设H0。
: 根据wikipedia "given the availability of a hypothesis testing procedure that
: can test the null hypothesis θ = θ0 against the alternative that θ ≠ θ

l*i2015-01-11 08:01

23 楼

我觉得颐和园里，郝蕾最美的一个镜头是光着身子咧着嘴巴笑
是在看预告片的时候看到那个镜头的太美了。
话说回到郝蕾，我本来一直很喜欢她的，还曾经对邓超李光洁很是愤愤然
但是前天晚上，领导show给我看郝蕾的博客，对她的好感顿然消失。
她太喜欢用感叹号了，每句话结尾都用感叹号的人，实在是太扫胃口

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

: 发几个美女片片轻松一下 :)
: 电影里余虹最美的一瞬
: 余虹在酒吧很吊的样子
: 旁白：我总是太努力，跑得太远
: 周伟说，我们分手吧
: 在宿舍，带上耳机，哈哈笑着，激情重新燃起
: 余虹和卡拉OK男。“你不喜欢我，我也不喜欢你，但只要你和我在一起。。。”
: 他们终于相见了，无言，余虹瞟了周伟一眼
: 李缇的碑文

h*s2015-01-11 08:01

24 楼

排

l*82015-01-11 08:01

25 楼

你那个permutation的算法，也许是我没看清楚，但是好像没看到你怎么处理重复出现
的字母造成重复字串的情况？

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

: 原题见
: http://www.mitbbs.com/article_t/DataSciences/10029.html
: 专门开一个贴，尝试逐题解答。本人菜鸟，求大牛指导
: 1. Given a coin you don’t know it’s fair or unfair. Throw it 6 times and
: get 1 tail and 5 head. Determine whether it’s fair or not. What’s your
: confidence value?
: 我的答案是：
: H0: the coin is fair
: Ha: the coin is unfair
: X is the number of heads

l*i2015-01-11 08:01

26 楼

倒数第三张是啥照片？好奇ing

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

: 谢谢酒妹，删掉了。
: 女主角郝蕾，东北人
: http://zh.wikipedia.org/wiki/%E9%83%9D%E8%95%BE

c*y2015-01-11 08:01

27 楼

算，10个帖，快发

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

: 吃。佛版不算外版吧？

n*n2015-01-11 08:01

28 楼

我所理解的confidence value是指我们观测到的值/差别不是单纯的由于取样的随机性
造成的。对于这个具体问题，如果coin fair的话， P(T=1,h=5|F)=1/32.也就是说，如
果是fair, 只有1/32的可能性出现这样的问题，也就是说我们可以认为coin不是fair的
，不是fair的confidence level就是1-1/32。

that

【在 B********4 的大作中提到】

: 这个问题我也迷糊了很久，查了不少资料，但还不是100%有把握。希望学统计的来指正
: 一下。
: p-value是说在零假设（H0)之下出现看到该情况或者更极端情况的概率，也就是假设硬
: 币是fair的，抛6次出现5个head或者6个head的概率。因为我们考虑对称性，所以还要
: 考虑到1个head或者0个head的情况。楼主的p-value计算是对的。
: significance level α只是预先设定的一个判定p-value的阈值（即多小的概率算小概
: 率事件），如果p<=α，我们认为零假设不对(因为在H0之下居然观察到了一个小概率事
: 件，肯定假设H0有问题）。反之，如果p>α,我们接受零假设H0。
: 根据wikipedia "given the availability of a hypothesis testing procedure that
: can test the null hypothesis θ = θ0 against the alternative that θ ≠ θ

M*N2015-01-11 08:01

29 楼

博客在哪里？

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

: 我觉得颐和园里，郝蕾最美的一个镜头是光着身子咧着嘴巴笑
: 是在看预告片的时候看到那个镜头的太美了。
: 话说回到郝蕾，我本来一直很喜欢她的，还曾经对邓超李光洁很是愤愤然
: 但是前天晚上，领导show给我看郝蕾的博客，对她的好感顿然消失。
: 她太喜欢用感叹号了，每句话结尾都用感叹号的人，实在是太扫胃口

g*r2015-01-11 08:01

30 楼

chi。

e*n2015-01-11 08:01

31 楼

原题见
http://www.mitbbs.com/article_t/DataSciences/10029.html
专门开一个贴，尝试逐题解答。本人菜鸟，求大牛指导
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
1. Given a coin you don’t know it’s fair or unfair. Throw it 6 times and
get 1 tail and 5 head. Determine whether it’s fair or not. What’s your
confidence value?
我的答案是：
H0: the coin is fair
Ha: the coin is unfair
X is the number of heads
Rejection region: |X - 3| > 2, i.e., X = 0,1,5,or 6
significance level alpha:
alpha = P(reject H0 | H0 is true)
=P(X=0,1,5,6 | H0 is true)
= (choose(6,0)+choose(6,1)+choose(6,5)+choose(6,6))*(1/2)^6
= (1+6+6+1)*(0.5^6) = 0.21875
because alpha > 0.05, we do not have enough evidence to reject H0, and we
accpte H0, so the coin is fair
confidence value 不知该如何计算，求指教
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
3. Which regression methods are you familiar? How to evaluate regression
result?
答案：
I'm familiar with Lasso and Ridge methods.
They are both linear models, and the prediction formulation is:
f(x) = beta_0 + sum_{i=1}^p beta_i x_i
We can evaluate the regression results using mean squared error (MSE):
1/n sum_i ( y_i - beta_0 + sum_{i=1}^p beta_i x_i)^2
To learn the coefficients, we have
-Ridge
min sum_i ( y_i - beta_0 + sum_{i=1}^p beta_i x_i)^2 + lambda sum_{i=1}^p
beta_i^2
-Lasso
min sum_i ( y_i - beta_0 + sum_{i=1}^p beta_i x_i)^2 + lambda sum_{i=1}^p |
beta_i|
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
4. Write down the formula for logistic regression. How to determine the
coefficients given the data?
答案：
* Formula: 假设我们处理二类分类问题，y in {1,0}
Pr(y=1|x) = exp(beta' x)/(1+exp(beta' x))
Pr(y=0|x) = 1/(1+exp(beta' x))
其中beta是coefficient
y=1 if Pr(y=1|x) >= Pr(y=0|x), and y = 0, otherwise.
* Determine the coefficients given the data: 假设我们有n个data points, {(xi,
yi)}, i=1,..,n, where yi in {1,0}
要通过likelihood maximization 来求beta
max_beta g(beta),
g(beta)是目标函数
g(beta) = sum_i log [ Pr(y=yi|x=xi)]
= sum_i [yi beta'xi - log(1+exp(beta'xi))]
我们用Newton-Raphson update来优化这个目标函数，在每个iteration中
beta^new = beta^old - [(g(beta)'')^-1 g(beta)']|_(beta=beta^old)
where
g(beta)' = sum_i xi(yi - p(yi=1|x=xi)),
g(beta)'' = - sum_i xi xi' p(yi=1|x=xi) (1-p(yi=1|x=xi))
defining z=[y1, ..., yn]',
p=[p(yi=1|x=x1), ..., p(yi=1|x=xn)]'
W=diag(p(yi=1|x=x1)(1-p(yi=1|x=x1)), ..., p(yi=1|x=xn)(1-p(yi=1|x=xn)))
X=[x1;...;xn]
we have g(beta)' = X'(z-p), and g(beta)'' = - X' W X
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
5. How do you evaluate regression?
For example, in this particular case:
item click-through-rate predicted rate
1 0.04 0.06
2 0.68 0.78
3 0.27 0.19
4 0.52 0.57
…
答案：
Using mean squared error:
1/n sum_i (click_through_rate_i - predicted_rate_i)^2
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
6. What’s the formula for SVM? What is decision boundary?
答案：
formula of SVM is
f(x) = w'x
min_{w, xi_i} 1/2 ||w||_2^2 + C sum_i xi_i
s.t. for any i:
1 - y_i w' x_i <= xi, 0 <= xi.
decision boundary:
In a statistical-classification problem with two classes, a decision
boundary or decision surface is a hypersurface that partitions the
underlying vector space into two sets, one for each class. The classifier
will classify all the points on one side of the decision boundary as
belonging to one class and all those on the other side as belonging to the
other class.
x: f(x) = 0
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
7. A field with unknown number of rabbits. Catch 100 rabbits and put a label
on each of them. A few days later, catch 300 rabbits and found 60 with
labels. Estimate how many rabbits are there?
这个题是point estimation 的问题。答案是 X = 100*(300/60) = 200，这个数字是
Maximum likelihood estimator
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
8. Given 10 coins with 1 unfair coin and 9 fair coins. The unfair coin has &
#8532; prob. to be head. Now random select 1 coin and throw it 3 times. You
observe head, head, tail. What’s the probability that the selected coin is
the unfair one?
这个题目考的是Bayes’ Rule
答案：
P(unfair coin| observe head, head, tail)
= 1- P(fair coin| observe head, head, tail)
根据Bayes’ Rule：
P(fair coin| observe head, head, tail)
= P(fair coin) * P(observe head, head, tail| fair coin)/
[P(fair coin) * P(observe head, head, tail| fair coin)+
P(unfair coin) * P(observe head, head, tail| unfair coin)]
其中
P(fair coin) = 9/10
P(unfair coin) = 1/10
P(observe head, head, tail| fair coin) = (1/2)^3
P(observe head, head, tail| unfair coin) = (0.8532^2)* (1-0.8532)
代入得到
P(fair coin| observe head, head, tail)
= (9/10*(1/2)^3)/(9/10*(1/2)^3 + 1/10*(0.8532^2)* (1-0.8532))
= 0.9132508
所以P(unfair coin| observe head, head, tail)
= 1 - 0.9132508
= 0.0867492
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
12. Generate all the permutation of a string.
For example, abc, acb, cba, …
答案：
import java.util.ArrayList;
public class permuteSolution{
public ArrayList> permute(String str1) {
char[] num = str1.toCharArray();
ArrayList> result = new ArrayList
>();
//start from an empty list
result.add(new ArrayList());
for (int i = 0; i < num.length; i++) {
//list of list in current iteration of the array num
ArrayList> current = new ArrayListCharacter>>();
for (ArrayList l : result) {
// # of locations to insert is largest index + 1
for (int j = 0; j < l.size()+1; j++) {
// + add num[i] to different locations
l.add(j, num[i]);
ArrayList temp = new ArrayList(l);
current.add(temp);
//System.out.println(temp);
// - remove num[i] add
l.remove(j);
}
}
result = new ArrayList>(current);
}
return result;
}
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
17. What’s the difference between classification and regression?
答案：
Classification tries to separate the dataset into classes belonging to the
response variable. Usually the response variable has two classes: Yes or No
(1 or 0). If the target variable can also have more than 2 categories.
Regression tries to predict numeric or continuous response variables. For
example, the predicted price of a consumer good.
The main difference between classification and regression lies on the
response they try to predict: continuous response of regression, and
discrete class label of classification.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
18. Can you explain how decision tree works? How to build a decision tree
from data?
答案：
A decision tree has decision blocks and terminating blocks where some
conclusion has been reached. Each decision block is based on a feature/
variable/predictor. By making a decision in a decision block, we
are lead to a left/ right branch of a decision block, which is other
decision blocks or to a terminating block.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
19. What is regularization in regression? Why do regularization? How to do
regularization?
答案：
regularization is a method to improve the linear model of regression, by
shrinking the coefficients to zeros. The reason to do this is to select the
variables relevant to the response, and removing the irrelevant variables,
so that the prediction accuracy and the interpretability of the model can be
improved. The way to do regularization is to add a regularization term to
the objective of regression problem, and optimize it. This term can be a l1
norm (lasso) or l2 norm (ridge) of the coefficient vector.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
20. What is gradient descent? stochastic gradient descent?
答案：
Gradient descent is a first-order optimization algorithm. To find a local
minimum of a function using gradient descent, one takes steps proportional
to the negative of the gradient (or of the approximate gradient) of the
function at the current point. If instead one takes steps proportional to
the positive of the gradient, one approaches a local maximum of that
function; the procedure is then known as gradient ascent.
In both gradient descent (GD) and stochastic gradient descent (SGD), you
update a set of parameters in an iterative manner to minimize an error
function.
While in GD, you have to run through ALL the samples in your training set to
do a single update for a parameter in a particular iteration, in SGD, on
the other hand, you use ONLY ONE training sample from your training set to
do the update for a parameter in a particular iteration.
Thus, if the number of training samples are large, in fact very large, then
using gradient descent may take too long because in every iteration when you
are updating the values of the parameters, you are running through the
complete training set. On the other hand, using SGD will be faster because
you use only one training sample and it starts improving itself right away
from the first sample.
SGD often converges much faster compared to GD but the error function is not
as well minimized as in the case of GD. Often in most cases, the close
approximation that you get in SGD for the parameter values are enough
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
29. Write a function to compute sqrt(X). Write a function to compute pow(x,
n) [square root and power)
答案：
public double sqrt1(double x){
double result = x/2;
double low = 0;
double high = Math.max(x,1);
while(Math.abs(x/result - result) > 0.00001){
if(x>result*result) {
low = result;
} else {
high =result;
}
result = (high+low)/2;
//System.out.println(result);
}
return result;
}

l*i2015-01-11 08:01

32 楼

http://blog.sina.com.cn/haolei111

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

: 博客在哪里？

l*b2015-01-11 08:01

33 楼

吃。。。

c*22015-01-11 08:01

34 楼

这是一个经典的Hypothesis testing问题吧，LZ说的是exact binomial test.
比较常用的，还有利用Central Limit Theorem构造的test, 也就是intro stat课教的
one sample proportion test, test statistics 就是 Z=(p_hat-p)/ sqrt(p(1-p)/N)
, 比较standard normal distribution就可以。
confidence interval也是可以根据CLT推得。
通常这个问题还有更难的一个版本，就是 p_hat 很小的时候，用CLT是有问题的，具体
的例子比如，ads click rate, 可能10000次里面只有1～2次click，这时候，要估计
confidence interval用CLT是不合适的，这好像也是Google常考面试题之一，具体的改
进方法，可以参考Wilson estimator，或者用Bayes的思路，LZ可以读读Wiki的解释:
http://en.wikipedia.org/wiki/Binomial_proportion_confidence_int

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

: 原题见
: http://www.mitbbs.com/article_t/DataSciences/10029.html
: 专门开一个贴，尝试逐题解答。本人菜鸟，求大牛指导
: >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
: 1. Given a coin you don’t know it’s fair or unfair. Throw it 6 times and
: get 1 tail and 5 head. Determine whether it’s fair or not. What’s your
: confidence value?
: 我的答案是：
: H0: the coin is fair
: Ha: the coin is unfair

M*N2015-01-11 08:01

35 楼

。。。
感叹号总在不该出来的地方冒出来，把我吓一跳，这文章读着要得心脏病了。

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

: http://blog.sina.com.cn/haolei111

x*c2015-01-11 08:01

36 楼

吃，快发

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

: 25个
: 外板来吃包子的，必须保证发够10个帖，（水贴不算）

l*c2015-01-11 08:01

37 楼

支持等看~~

wh2015-01-11 08:01

38 楼

是。静静写这篇的时候，我还说你对此发表过高深意见。这也没办法，灌水总是流水作
业，后来的人不知道前面的人讨论过什么。唉我想想我也是，灌了两年很多话都说过了
不想再说了。以前浙版说到杭州我总有话说。现在只后悔没有好好地写几篇完整的杭州
，以前的热情都给零零碎碎打磨掉了。

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

: 我最早和九斤同学讨论过一次。话题出现几次，就疲了。

c*y2015-01-11 08:01

39 楼

10个帖，发完给你

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

: 吃，快发

t*62015-01-11 08:01

40 楼

第1题可以用Bayes rule吧
Prior：Beta（a,b） *a, b 选择取决于你想让prior多strong
Likelihood: Y~iid Bernouli(p) H~Binomial(n,p) *H is total number of head,
T is total # of tail
Posterior: Beta(a+H, b+T)
至于怎么求Beta(a+H, b+T) 的confidence interval，参见http://stats.stackexchange.com/questions/82475/calculate-the-confidence-interval-for-the-mean-of-a-beta-distribution
1. dbeta() 需用R软件
2. Bootstrap from rbeta() simulation 需用R软件
3. Asymptotic confidence intervals 如楼上所说

wh2015-01-11 08:01

41 楼

查到静静20个帖子，最近的是17号。但没有一篇被mark过。可能没吃到包子很不爽。不
过她好像出差不少，可能没时间灌水。

L*k2015-01-11 08:01

42 楼

太黑了。

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

: 算，10个帖，快发

t*62015-01-11 08:01

43 楼

我也搭车问40题中的一个rare event的题：
26.If I want to build a classifier, but the data is very unbalanced. I have
a few positive samples but a lot of negative samples. What should I do?
貌似这道题说的就是click through rate/credit fraudulent这种极小概率事件的
training方法。我的思路如下，求大牛指正：
1. Resampling 降噪，但resampling不会降低bias
2. 临床试验里的case control matching 缺点：慢，control subject的选择很
arbitrary
3. Empirical Bayes，prior是empirical_rate.这是目前想到的最靠铺的了，但是没用
过，不知道R和Python有什么好的package没，做过的说说？

wh2015-01-11 08:01

44 楼

嗯。要有节制。《上海堡垒》里的男主角说他从来不用感叹号。最后催促女孩逃生的电
话留言里唯一用了一次，希望女孩能注意到。我发现灌水不用感叹号很难。

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

: 我觉得颐和园里，郝蕾最美的一个镜头是光着身子咧着嘴巴笑
: 是在看预告片的时候看到那个镜头的太美了。
: 话说回到郝蕾，我本来一直很喜欢她的，还曾经对邓超李光洁很是愤愤然
: 但是前天晚上，领导show给我看郝蕾的博客，对她的好感顿然消失。
: 她太喜欢用感叹号了，每句话结尾都用感叹号的人，实在是太扫胃口

p*82015-01-11 08:01

45 楼

吃！

B*42015-01-11 08:01

46 楼

这个问题我也迷糊了很久，查了不少资料，但还不是100%有把握。希望学统计的来指正
一下。
p-value是说在零假设（H0)之下出现看到该情况或者更极端情况的概率，也就是假设硬
币是fair的，抛6次出现5个head或者6个head的概率。因为我们考虑对称性，所以还要
考虑到1个head或者0个head的情况。楼主的p-value计算是对的。
significance level α只是预先设定的一个判定p-value的阈值（即多小的概率算小概
率事件），如果p<=α，我们认为零假设不对(因为在H0之下居然观察到了一个小概率事
件，肯定假设H0有问题）。反之，如果p>α,我们接受零假设H0。
根据wikipedia "given the availability of a hypothesis testing procedure that
can test the null hypothesis θ = θ0 against the alternative that θ ≠ θ
0 for any value of θ0, then a confidence interval with confidence level γ
= 1 − α can be defined as containing any number θ0 for which the
corresponding null hypothesis is not rejected at significance level α.",如
果我们设定α为5%，则我们可以说confidence level是95%。
但是我觉得这个说法不是面试者真正想要问的答案，因为α是你事先设定的，可以为10
%，5%或1%。但和给的观测结果都没啥关系，仅仅是用来接受还是拒绝假设的。现在我
们求出p-value比较大，所以我们应该接受这个假设硬币是fair的。但究竟这样假设有
多大可能是对的呢？我认为应该用Hoeffding's inequality来求这个confidence value
(confidence level).
假设tail=0, head=1,那么样本均值u为5/6, 而实际均值v为1/2, 差为1/3。根据
Hoeffding's inequality,
Pr(|u-v| > 1/3) <= 2exp(-2*(1/9)*6) = 2/exp(4/3) = 53%
所以confidence value是47%.

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

: 原题见
: http://www.mitbbs.com/article_t/DataSciences/10029.html
: 专门开一个贴，尝试逐题解答。本人菜鸟，求大牛指导
: >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
: 1. Given a coin you don’t know it’s fair or unfair. Throw it 6 times and
: get 1 tail and 5 head. Determine whether it’s fair or not. What’s your
: confidence value?
: 我的答案是：
: H0: the coin is fair
: Ha: the coin is unfair

a*e2015-01-11 08:01

47 楼

哈哈，你一提郝蕾笑，我就想起顺溜他姐，咧着嘴憨厚的热切的看自己弟弟吃饭。但是
郝蕾再怎么扮乡土，也还是不像农村姐姐。
她比巩俐的功力还差得远呢，慢慢修炼吧。

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

: 我觉得颐和园里，郝蕾最美的一个镜头是光着身子咧着嘴巴笑
: 是在看预告片的时候看到那个镜头的太美了。
: 话说回到郝蕾，我本来一直很喜欢她的，还曾经对邓超李光洁很是愤愤然
: 但是前天晚上，领导show给我看郝蕾的博客，对她的好感顿然消失。
: 她太喜欢用感叹号了，每句话结尾都用感叹号的人，实在是太扫胃口

l*s2015-01-11 08:01

48 楼

wk，怎么突然冒出这么多吃货

B*42015-01-11 08:01

49 楼

我还有一个解法就是，我们可以不拘泥于significance level α通常为5%，1%。既然
我们算出p-value = 0.22,我们可以把α定为0.22,那么confidence level 为 0.78。
这个和我之前说的47%不矛盾，因为Hoeffding's Inequality得到的是个比较宽松的上
限。

that

【在 B********4 的大作中提到】

: 这个问题我也迷糊了很久，查了不少资料，但还不是100%有把握。希望学统计的来指正
: 一下。
: p-value是说在零假设（H0)之下出现看到该情况或者更极端情况的概率，也就是假设硬
: 币是fair的，抛6次出现5个head或者6个head的概率。因为我们考虑对称性，所以还要
: 考虑到1个head或者0个head的情况。楼主的p-value计算是对的。
: significance level α只是预先设定的一个判定p-value的阈值（即多小的概率算小概
: 率事件），如果p<=α，我们认为零假设不对(因为在H0之下居然观察到了一个小概率事
: 件，肯定假设H0有问题）。反之，如果p>α,我们接受零假设H0。
: 根据wikipedia "given the availability of a hypothesis testing procedure that
: can test the null hypothesis θ = θ0 against the alternative that θ ≠ θ

c*h2015-01-11 08:01

50 楼

巩俐那是骨子里的，你看那秋香演的。。。

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

: 哈哈，你一提郝蕾笑，我就想起顺溜他姐，咧着嘴憨厚的热切的看自己弟弟吃饭。但是
: 郝蕾再怎么扮乡土，也还是不像农村姐姐。
: 她比巩俐的功力还差得远呢，慢慢修炼吧。

m*72015-01-11 08:01

51 楼

你自己找了个吃货当板斧

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

: wk，怎么突然冒出这么多吃货

l*82015-01-11 08:01

52 楼

你那个permutation的算法，也许是我没看清楚，但是好像没看到你怎么处理重复出现
的字母造成重复字串的情况？

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

: 原题见
: http://www.mitbbs.com/article_t/DataSciences/10029.html
: 专门开一个贴，尝试逐题解答。本人菜鸟，求大牛指导
: >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
: 1. Given a coin you don’t know it’s fair or unfair. Throw it 6 times and
: get 1 tail and 5 head. Determine whether it’s fair or not. What’s your
: confidence value?
: 我的答案是：
: H0: the coin is fair
: Ha: the coin is unfair

a*e2015-01-11 08:01

53 楼

巩俐一笑是比较憨厚的感觉。但她人高马大，极有气场，所以演时髦欢场女子也能很有
说服力。

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

: 巩俐那是骨子里的，你看那秋香演的。。。

d*g2015-01-11 08:01

54 楼

re

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

: 25个
: 外板来吃包子的，必须保证发够10个帖，（水贴不算）

n*n2015-01-11 08:01

55 楼

我所理解的confidence value是指我们观测到的值/差别不是单纯的由于取样的随机性
造成的。对于这个具体问题，如果coin fair的话， P(T=1,h=5|F)=1/32.也就是说，如
果是fair, 只有1/32的可能性出现这样的问题，也就是说我们可以认为coin不是fair的
，不是fair的confidence level就是1-1/32。

that

【在 B********4 的大作中提到】

: 这个问题我也迷糊了很久，查了不少资料，但还不是100%有把握。希望学统计的来指正
: 一下。
: p-value是说在零假设（H0)之下出现看到该情况或者更极端情况的概率，也就是假设硬
: 币是fair的，抛6次出现5个head或者6个head的概率。因为我们考虑对称性，所以还要
: 考虑到1个head或者0个head的情况。楼主的p-value计算是对的。
: significance level α只是预先设定的一个判定p-value的阈值（即多小的概率算小概
: 率事件），如果p<=α，我们认为零假设不对(因为在H0之下居然观察到了一个小概率事
: 件，肯定假设H0有问题）。反之，如果p>α,我们接受零假设H0。
: 根据wikipedia "given the availability of a hypothesis testing procedure that
: can test the null hypothesis θ = θ0 against the alternative that θ ≠ θ

i*t2015-01-11 08:01

56 楼

同意。小金宝那个大腿舞，你让周迅去踢，绝对没有效果。

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

: 巩俐一笑是比较憨厚的感觉。但她人高马大，极有气场，所以演时髦欢场女子也能很有
: 说服力。

b*e2015-01-11 08:01

57 楼

cong

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

: 25个
: 外板来吃包子的，必须保证发够10个帖，（水贴不算）

b*s2015-01-11 08:01

58 楼

这里样本太少，不可以用CLT
一般我们用success/failure condition （》=10）来演算是否可以CLT，

N)

【在 c*******2 的大作中提到】

: 这是一个经典的Hypothesis testing问题吧，LZ说的是exact binomial test.
: 比较常用的，还有利用Central Limit Theorem构造的test, 也就是intro stat课教的
: one sample proportion test, test statistics 就是 Z=(p_hat-p)/ sqrt(p(1-p)/N)
: , 比较standard normal distribution就可以。
: confidence interval也是可以根据CLT推得。
: 通常这个问题还有更难的一个版本，就是 p_hat 很小的时候，用CLT是有问题的，具体
: 的例子比如，ads click rate, 可能10000次里面只有1～2次click，这时候，要估计
: confidence interval用CLT是不合适的，这好像也是Google常考面试题之一，具体的改
: 进方法，可以参考Wilson estimator，或者用Bayes的思路，LZ可以读读Wiki的解释:
: http://en.wikipedia.org/wiki/Binomial_proportion_confidence_int

l*i2015-01-11 08:01

59 楼

顺溜顺溜顺溜我念叨了3遍终于想起来顺溜是谁了
那个片子我看了几集就看不下去了那时候他姐姐还没出场呢

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

: 哈哈，你一提郝蕾笑，我就想起顺溜他姐，咧着嘴憨厚的热切的看自己弟弟吃饭。但是
: 郝蕾再怎么扮乡土，也还是不像农村姐姐。
: 她比巩俐的功力还差得远呢，慢慢修炼吧。

s*62015-01-11 08:01

60 楼

co chi!

b*s2015-01-11 08:01

61 楼

Ha是two side，所以要考虑对称性
至于你最后给的那个什么不等式，只是给了一个上界而已啊，还不如alpha来得有用，
毕竟5%的type I error保证下,出错率比较少了

that

【在 B********4 的大作中提到】

: 这个问题我也迷糊了很久，查了不少资料，但还不是100%有把握。希望学统计的来指正
: 一下。
: p-value是说在零假设（H0)之下出现看到该情况或者更极端情况的概率，也就是假设硬
: 币是fair的，抛6次出现5个head或者6个head的概率。因为我们考虑对称性，所以还要
: 考虑到1个head或者0个head的情况。楼主的p-value计算是对的。
: significance level α只是预先设定的一个判定p-value的阈值（即多小的概率算小概
: 率事件），如果p<=α，我们认为零假设不对(因为在H0之下居然观察到了一个小概率事
: 件，肯定假设H0有问题）。反之，如果p>α,我们接受零假设H0。
: 根据wikipedia "given the availability of a hypothesis testing procedure that
: can test the null hypothesis θ = θ0 against the alternative that θ ≠ θ

s*a2015-01-11 08:01

62 楼

我跟去看，其实还好。我并没有觉得看到感叹号就心惊肉跳的样子，不过这可能和我时
常纳闷为什么我们人看到感叹号会心跳，看到问号可能就会同时想到文豪有关哈。
这张脸不错。