google onsite 目测要挂－回报大家

一开始我也是不愿意写的，刚刚好看到一起面的哥们写了，于是我就写吧。 大概是三轮可以拿good 一轮窑挂，所以结果应该还是挂。
anyway，上题。
总结：一题算法都没有。。。一个graph都没有。。。 一个linklist都没有。。。一个offer都没有！！！！！！！！

1.烙印，在面试前碰到了，刚刚好都等着，问我 你是哪个xxx么？ 我就是今天要面你的。。 当时我就心里想完了。。但是题目挺简单。
给一个infinite array 只有0 - 9 设计一个
def getprobability(n):得到某个数出现的概率。




我用的reservoie sampling 做的，然后我补充如果直接hashing 会overflow. 然后考虑到一multi thread情况，需要写两个函数，一个专门产生 sampling list
一个专门计算概率。 这里要有做个checker看看产生的list是不是有效，也就是 0-9数的概率和要为1
follow up:
现在你得到概率，你怎么按照概率产生刚刚的数。
两个方法，第一个直接用刚刚的array random index取数，但是问题是如果是multithread 调用这样做有问题。 第二个方法：定时产生所有数的accumulate probablilty 根据这个probabol

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

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

performance today? I think its good.
和国人大哥一起出来的，期间他说，中国人肯定要帮中国人的嘛！ 我最看不起烙印了。。。 哎。 感觉要对不起这这位大哥了。。

第二轮实在太💩。..另外希望看客加点分，有各种内推也希望帮帮忙。。。。






补充内容 (2015-4-6 02:26):
求内推 求米 求各种。。。

补充内容 (2015-4-9 22:15):
rejected. said my coding is not good enough. anyway... I've been there and did what ever I can do.

refurbish 发表于 2015-4-6 06:52
之前是在手机上看的，第一题求一下讨论。

如果要得到某个数出现的概率，用一个长度为11的数组来对相应的 ...

这样容易overflow...我刚刚开始想这样做，后来想了一下用reservior sampling 长度为L 的 array纪录这样后面再统计就不会 overflow....

refurbish 发表于 2015-4-6 01:10
感谢楼主分享，感觉楼主答的挺好呀，也许过于担心了。另外想问一下“you have more id than files”中id是 ...

比如有很多人在用 一些file 每个用的人都有一个ID 。。。 然后你想要除去duplicate files

ID File
1   Afile
2   Afile
3   Bfile

打算找hr 理论一下。。。 system design实在太蛋疼

感谢楼主分享，感觉楼主答的挺好呀，也许过于担心了。另外想问一下“you have more id than files”中id是什么含义？

靠 google的题越来越难了啊啊啊啊啊啊啊
现在都有design啦？LZ new grad？

houqingniao 发表于 2015-4-6 02:04
靠 google的题越来越难了啊啊啊啊啊啊啊
现在都有design啦？LZ new grad？

是的 2月毕业。opt在燃烧。。 。。。。。。我觉得我的题目都很非主流。。。感觉都是基于大数据 和multi thread...
除了最后一题。。encode decode...

楼主，Google最近缺人，你这状况，能offer的！期待你的好消息

duplicate file means the contents are same for some files with different id? like
id content
1 "aaa...."
2 "bbb..."
3 "aaa..."?

池大侠 发表于 2015-4-6 10:43
比如有很多人在用 一些file 每个用的人都有一个ID 。。。 然后你想要除去duplicate files

ID File

支持楼主理论！！！

1 billion files * 4kB = 4TB，要放到1TB的disk，难道能保证4倍的重复率？还是需要分布式存储？

lz能不能多提供点这个题目的信息和followup问题，不胜感激！

之前是在手机上看的，第一题求一下讨论。

如果要得到某个数出现的概率，用一个长度为11的数组来对相应的数字计数，最后一个记录总数，算得时候对应数的计数除一下总数就是该数出现的概率了。这个和reservoir sampling有什么关系呢？

refurbish 发表于 2015-4-6 06:46
支持楼主理论！！！

1 billion files * 4kB = 4TB，要放到1TB的disk，难道能保证4倍的重复率？还是需 ...

这道题follow up不多，主要是在讨论collusion 和location要怎么做。。。具体可以看看Google big table..
其实就是要我设计google bigtable..