近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 6099|回复: 43
收起左侧

google onsite 目测要挂-回报大家

[复制链接] |试试Instant~ |关注本帖
池大侠 发表于 2015-4-6 08:56:30 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
一开始我也是不愿意写的,刚刚好看到一起面的哥们写了,于是我就写吧。 大概是三轮可以拿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-google 1point3acres
follow up:
现在你得到概率,你怎么按照概率产生刚刚的数。
两个方法,第一个直接用刚刚的array random index取数,但是问题是如果是multithread 调用这样做有问题。 第二个方法:定时产生所有数的accumulate probablilty 根据这个probabolity array generate number即可。
答完烙印还挺满意,拍了照片。。

2. 这轮 design ...完全我不u知道我在干嘛。不知道可以argue 么,new grad考的desig......真心不会啊。。。
是国人大哥。。做chrome os 我承认我水。。。


1 billion files  each file 4k you have more id than files, which means files are dupliacte.
your computer has 4k memory 1TB disk.
design a method to remove duplicate files and store those files. visit 1point3acres.com for more.
given id track the file from your disk...




做法是  hashing files to disk and store the id. but hashing always has collusion, which means you need to  have another map<id, location>
写完简单的想法大哥拍了照片。。。然后follow up了一下我加了几个case 大哥又拍了照片。。。因为都是psudo code.... 我只用python....可是这题明显没法用。。
讲起来很复杂,后来才知道是google big table 但是是在准备材料system design的倒数第二条。。。

这轮我后面已经傻了,大哥开始问我linux 命令。。。 我感觉完全愣了,后来时间到了,大哥接了电话走了。。。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦
午饭 :一个南美mm带我吃的,没怎么聊,因为我面完第二轮心情不是很好。。。 . 1point3acres.com/bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后mm 把我早上面试的feedback纸弄丢了。。。。。。- -!!!!!!

. From 1point 3acres bbs
3. 俩白人, shadow不说话。又是chrome组的。。。
问题 现在我有log file. 纪录每秒哪些processes 发生
比如1-A 2-B,A 3-null, 4- C
写个get60(A)统计过去60秒 A发生的次数 follow up: getday(A) and what if u dont need exact number?

. From 1point 3acres bbs刚刚开始我写的几个object 来记录log file...后来最后一个问题他说dont need exact number..我就又用了reservior sample做了部分的题,然后设计了一下怎么logging events 的object... from: 1point3acres.com/bbs
因为不是算法,设计的东西可以自圆其说就好,他们问我就扯。。 然后最后他们俩都拍了照片。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我问了俩chrome os的问题 他们俩也貌似满意的走了。。

4. 国人大哥,很nice...国人大哥特别叮嘱我别泄题,所以具体我就不说了。 但是很简单貌似encode decode.. 主要是前面讨论了很久。 后面follow up一个很简单的问题。. From 1point 3acres bbs
最后问问题,我深感已经绝望: in general what do you think about my performance today? I think its good.
和国人大哥一起出来的,期间他说,中国人肯定要帮中国人的嘛! 我最看不起烙印了。。。 哎。 感觉要对不起这这位大哥了。。

第二轮实在太&#128169;。..另外希望看客加点分,有各种内推也希望帮帮忙。。。。






补充内容 (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.

评分

10

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 池大侠 发表于 2015-4-6 20:26:34 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
refurbish 发表于 2015-4-6 06:52
之前是在手机上看的,第一题求一下讨论。

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

这样容易overflow...我刚刚开始想这样做,后来想了一下用reservior sampling 长度为L 的 array纪录这样后面再统计就不会 overflow....
回复 支持 2 反对 0

使用道具 举报

 楼主| 池大侠 发表于 2015-4-6 10:43:38 | 显示全部楼层
关注一亩三分地微博:
Warald
refurbish 发表于 2015-4-6 01:10.鐣欏璁哄潧-涓浜-涓夊垎鍦
感谢楼主分享,感觉楼主答的挺好呀,也许过于担心了。另外想问一下“you have more id than files”中id是 ...

比如有很多人在用 一些file 每个用的人都有一个ID 。。。 然后你想要除去duplicate files. visit 1point3acres.com for more.

ID File
1   Afile
2   Afile
3   Bfile

打算找hr 理论一下。。。 system design实在太蛋疼
回复 支持 1 反对 0

使用道具 举报

refurbish 发表于 2015-4-6 10:10:59 来自手机 | 显示全部楼层
感谢楼主分享,感觉楼主答的挺好呀,也许过于担心了。另外想问一下“you have more id than files”中id是什么含义?
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-4-6 11:04:56 | 显示全部楼层
靠 google的题越来越难了啊啊啊啊啊啊啊
现在都有design啦?LZ new grad?
回复 支持 反对

使用道具 举报

 楼主| 池大侠 发表于 2015-4-6 11:26:17 | 显示全部楼层
houqingniao 发表于 2015-4-6 02:04
靠 google的题越来越难了啊啊啊啊啊啊啊
现在都有design啦?LZ new grad?

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

使用道具 举报

shinichish 发表于 2015-4-6 11:31:14 | 显示全部楼层
楼主,Google最近缺人,你这状况,能offer的!期待你的好消息
回复 支持 反对

使用道具 举报

fishyuze 发表于 2015-4-6 11:36:15 | 显示全部楼层
duplicate file means the contents are same for some files with different id? like
id content 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1 "aaa...."
2 "bbb...". 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
3 "aaa..."?
. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-4-6 15:46:36 | 显示全部楼层
池大侠 发表于 2015-4-6 10:43
比如有很多人在用 一些file 每个用的人都有一个ID 。。。 然后你想要除去duplicate files

ID File

支持楼主理论!!!

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

lz能不能多提供点这个题目的信息和followup问题,不胜感激!
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-4-6 15:52:17 | 显示全部楼层
之前是在手机上看的,第一题求一下讨论。
.1point3acres缃
如果要得到某个数出现的概率,用一个长度为11的数组来对相应的数字计数,最后一个记录总数,算得时候对应数的计数除一下总数就是该数出现的概率了。这个和reservoir sampling有什么关系呢?
回复 支持 反对

使用道具 举报

 楼主| 池大侠 发表于 2015-4-6 20:24:35 | 显示全部楼层
refurbish 发表于 2015-4-6 06:46
支持楼主理论!!!. Waral 鍗氬鏈夋洿澶氭枃绔,

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

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

使用道具 举报

 楼主| 池大侠 发表于 2015-4-6 20:24:59 | 显示全部楼层
fishyuze 发表于 2015-4-6 02:36. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
duplicate file means the contents are same for some files with different id? like
id content. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1 "a ...
. From 1point 3acres bbs
没具体到内容,就是assume他们都一样
回复 支持 反对

使用道具 举报

fishyuze 发表于 2015-4-6 22:43:39 | 显示全部楼层
池大侠 发表于 2015-4-6 20:24
没具体到内容,就是assume他们都一样
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我感觉主要难点就在怎么确定两个不同id的file是duplicate
可能我理解错了。。。
回复 支持 反对

使用道具 举报

wenruimeng 发表于 2015-4-7 00:43:42 | 显示全部楼层
一轮面的不好不一定要跪,耐心等待一下。
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-4-7 01:09:19 | 显示全部楼层
池大侠 发表于 2015-4-6 20:26
这样容易overflow...我刚刚开始想这样做,后来想了一下用reservior sampling 长度为L 的 array纪录这样后 ...
. 1point3acres.com/bbs
明白了,你这样做还真是很巧妙。赞一下!
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-4-7 01:24:13 | 显示全部楼层
池大侠 发表于 2015-4-6 20:24
这道题follow up不多,主要是在讨论collusion 和location要怎么做。。。具体可以看看Google big table..
...

就是看了,才觉得和你这个题目没啥关系。因为bigtable涉及到分布式存储,不只是文件存储,而且又要保证一定冗余-我记得是三倍。你这个可能不够存,另外bigtable的一个重要难点是要把文件分块,然后分布式存放,所以需要比较复杂的索引结构。你这个题目用个SHA256,基本上就没有collison的可能了,2^-256的hash collision可能性。
回复 支持 反对

使用道具 举报

 楼主| 池大侠 发表于 2015-4-7 01:56:24 | 显示全部楼层
refurbish 发表于 2015-4-6 16:24
就是看了,才觉得和你这个题目没啥关系。因为bigtable涉及到分布式存储,不只是文件存储,而且又要保证一 ...

嗯那个是hdfs的基础。。我也看过。。可是这题主要是感觉很底层。。。一直在讨论怎么取文件 存文件。。 然后文件大小。。 和平时准备的完全没什么关系。。。   
手足无措。。 大哥也很无奈。。
回复 支持 反对

使用道具 举报

 楼主| 池大侠 发表于 2015-4-7 01:58:36 | 显示全部楼层
refurbish 发表于 2015-4-6 16:09. visit 1point3acres.com for more.
明白了,你这样做还真是很巧妙。赞一下!
. 1point3acres.com/bbs
碰到烙印我觉得还是最好直接拿最优,我怕被整。因为如果先用count肯定会被follow 一堆问题。 思想虽然简单但是代码量我基本是写满再擦了半版。 满多小细节要考虑的。
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-4-7 02:10:23 | 显示全部楼层
池大侠 发表于 2015-4-7 01:58
碰到烙印我觉得还是最好直接拿最优,我怕被整。因为如果先用count肯定会被follow 一堆问题。 思想虽然简 ...

哈哈。老印有没有问选择L的策略是什么?
回复 支持 反对

使用道具 举报

 楼主| 池大侠 发表于 2015-4-7 02:49:23 | 显示全部楼层
refurbish 发表于 2015-4-6 17:10
哈哈。老印有没有问选择L的策略是什么?
. from: 1point3acres.com/bbs
我自己补充的。。。 我怕他问所以我说了一下。。 他主要还是挑一些multi thread的来follow up. 保证得到的L atomic
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-28 08:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表