GG 12.8 实习电面

一学期很快过完了，老板让改的论文也没有头绪，在这发个实习面经攒攒人品吧。

第一轮是个印度小哥，问了两道LC median题。都刷过没啥好说的. 第一题从一个array里sample k elements with equal probability. 直接给出in place解。 follow up: Reservoir Sampling （就是array 太大了放不进内存只能遍历一遍咋办）都问了时间和空间复杂度。第二题：LC撕拔流原题，给小哥讲了minmax算法的principal，用bruteforce解了一下，后续给了

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

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

你的程序有bug！左思右想，我沉默两分钟说，抱歉我没找到...大叔直接定位到计算除法的那一行才想起来完全忘了division by zero了。只好尴尬的感谢大叔问了个小问题结束店面。

这周四问了HR，说送到下周一的HC for review了。希望能有好运气！

感谢楼主的面经！请问sample k elements with equal probability的题号楼主还记得吗，我搜关键词没有搜到

wsypeter 发表于 2017-12-18 07:21
感谢楼主的面经！请问sample k elements with equal probability的题号楼主还记得吗，我搜关键词没有搜到

唔...帖子里没说清楚，follow up是LC原题，因为之前的那个非常简单感觉就是个引子。实质就是高中数学的无放回取球，你可以直接用reservoir sampling做，也可以给sample过的球做标记每次在1-n之间筛找到没sample到的位置(k次)不过期望复杂度稍高，也可以参考shuffle array的原位算法 http://www.geeksforgeeks.org/shuffle-a-given-array/。

wsypeter 发表于 2017-12-17 15:21
感谢楼主的面经！请问sample k elements with equal probability的题号楼主还记得吗，我搜关键词没有搜到

伞舅爸  jglkjfdsbgd

UPDATE: 已过HC

恭喜楼主！

请问楼主，撕拔流有用到minmax算法吗

wjw779 发表于 2018-1-3 16:27
请问楼主，撕拔流有用到minmax算法吗

有啊，我方要min对方的score才能max自己的score，算是一个简易版吧，但思想是一样的

Fightandweight 发表于 2018-1-3 22:40
有啊，我方要min对方的score才能max自己的score，算是一个简易版吧，但思想是一样的

这个题目真的不好想，我看答案看了好久