yelp面经

回馈地里，刚刚面试完，趁热把面经写下来。
面试人：YALIN 中国人，英语一般般，挺严肃的。

没有why yelp，只有一上来上我介

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

。

最后让分析代码。。。

八成跪了，大家加油吧！发出来攒人品。现在也是三无状态了，很难受。

请问楼主面的是什么方向?

我觉得reservoir sampling这种算法确实有一些人会不知道 感觉可以先用naive的做法过了再根据面试官需要optimize

sw7eets 发表于 2017-11-2 06:16
请问楼主面的是什么方向?

SDE intern

CrescentGG 发表于 2017-11-2 06:21
我觉得reservoir sampling这种算法确实有一些人会不知道 感觉可以先用naive的做法过了再根据面试官需要opti ...

对啊但是naive的方法不知道咋做。。。刚转码不到半年，所以水平有限。只胡乱写了一个reservoir sampling。。。

这题最优解可以用Fisher Yates Shuffle

cutehuazai 发表于 2017-11-2 06:54
这题最优解可以用Fisher Yates Shuffle

这两个算法类似吧

adrianliu729 发表于 2017-11-8 10:11
这两个算法类似吧

复杂度不一样

cutehuazai 发表于 2017-11-8 11:38
复杂度不一样

之前看面经好像大家都是用的reservior sampling, 想问下Fisher Yates Shuffle的复杂度多少？谢谢啦

补充内容 (2017-11-16 01:29):
额确实这题最优解是shuffle, O(K)， K是雷的个数。Reservior Sampling 的复杂度是O(H*W), H, W分别是矩阵的长宽。这个长方形不是无限的，个人觉得根本没必要用reservior sampling.