一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4763|回复: 43
收起左侧

google onsite 目测要挂-回报大家

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

1.烙印,在面试前碰到了,刚刚好都等着,问我 你是哪个xxx么? 我就是今天要面你的。。 当时我就心里想完了。。但是题目挺简单。
给一个infinite array 只有0 - 9 设计一个. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
def getprobability(n):得到某个数出现的概率。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

. 1point3acres.com/bbs

我用的reservoie sampling 做的,然后我补充如果直接hashing 会overflow. 然后考虑到一multi thread情况,需要写两个函数,一个专门产生 sampling list
一个专门计算概率。 这里要有做个checker看看产生的list是不是有效,也就是 0-9数的概率和要为1
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
given id track the file from your disk...

. more info on 1point3acres.com


做法是  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带我吃的,没怎么聊,因为我面完第二轮心情不是很好。。。 . 鍥磋鎴戜滑@1point 3 acres

然后mm 把我早上面试的feedback纸弄丢了。。。。。。- -!!!!!!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

刚刚开始我写的几个object 来记录log file...后来最后一个问题他说dont need exact number..我就又用了reservior sample做了部分的题,然后设计了一下怎么logging events 的object..
因为不是算法,设计的东西可以自圆其说就好,他们问我就扯。。 然后最后他们俩都拍了照片。。
我问了俩chrome os的问题 他们俩也貌似满意的走了。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

4. 国人大哥,很nice...国人大哥特别叮嘱我别泄题,所以具体我就不说了。 但是很简单貌似encode decode.. 主要是前面讨论了很久。 后面follow up一个很简单的问题。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
最后问问题,我深感已经绝望: in general what do you think about my performance today? I think its good..鏈枃鍘熷垱鑷1point3acres璁哄潧
和国人大哥一起出来的,期间他说,中国人肯定要帮中国人的嘛! 我最看不起烙印了。。。 哎。 感觉要对不起这这位大哥了。。

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


. 1point 3acres 璁哄潧


. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-4-6 02:26):. 鍥磋鎴戜滑@1point 3 acres
求内推 求米 求各种。。。

补充内容 (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 | 显示全部楼层
refurbish 发表于 2015-4-6 06:52
之前是在手机上看的,第一题求一下讨论。

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

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

使用道具 举报

 楼主| 池大侠 发表于 2015-4-6 10:43:38 | 显示全部楼层
refurbish 发表于 2015-4-6 01:10
感谢楼主分享,感觉楼主答的挺好呀,也许过于担心了。另外想问一下“you have more id than files”中id是 ...

比如有很多人在用 一些file 每个用的人都有一个ID 。。。 然后你想要除去duplicate files
. more info on 1point3acres.com
ID File. more info on 1point3acres.com
1   Afile
2   Afile. From 1point 3acres bbs
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的题越来越难了啊啊啊啊啊啊啊. visit 1point3acres.com for more.
现在都有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. Waral 鍗氬鏈夋洿澶氭枃绔,
1 "aaa...."
2 "bbb..."
3 "aaa..."?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

回复 支持 反对

使用道具 举报

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

ID File

支持楼主理论!!!

1 billion files * 4kB = 4TB,要放到1TB的disk,难道能保证4倍的重复率?还是需要分布式存储?. From 1point 3acres bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
lz能不能多提供点这个题目的信息和followup问题,不胜感激!
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-4-6 15:52:17 | 显示全部楼层
之前是在手机上看的,第一题求一下讨论。

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

使用道具 举报

 楼主| 池大侠 发表于 2015-4-6 20:24:35 | 显示全部楼层
refurbish 发表于 2015-4-6 06:46
支持楼主理论!!!. 鍥磋鎴戜滑@1point 3 acres
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1 billion files * 4kB = 4TB,要放到1TB的disk,难道能保证4倍的重复率?还是需 ...
. 1point 3acres 璁哄潧
这道题follow up不多,主要是在讨论collusion 和location要怎么做。。。具体可以看看Google big table... visit 1point3acres.com for more.
其实就是要我设计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 ...

没具体到内容,就是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. 1point 3acres 璁哄潧
这样容易overflow...我刚刚开始想这样做,后来想了一下用reservior sampling 长度为L 的 array纪录这样后 ...

明白了,你这样做还真是很巧妙。赞一下!
回复 支持 反对

使用道具 举报

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. from: 1point3acres.com/bbs
就是看了,才觉得和你这个题目没啥关系。因为bigtable涉及到分布式存储,不只是文件存储,而且又要保证一 ...

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

使用道具 举报

 楼主| 池大侠 发表于 2015-4-7 01:58:36 | 显示全部楼层
refurbish 发表于 2015-4-6 16:09
明白了,你这样做还真是很巧妙。赞一下!
.鏈枃鍘熷垱鑷1point3acres璁哄潧
碰到烙印我觉得还是最好直接拿最优,我怕被整。因为如果先用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的策略是什么?

我自己补充的。。。 我怕他问所以我说了一下。。 他主要还是挑一些multi thread的来follow up. 保证得到的L atomic
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 11:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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