一亩三分地论坛

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

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

G家已被HC挂,发面经,求安慰。。。附两面的完整code

[复制链接] |试试Instant~ |关注本帖
生活在大农村 发表于 2014-11-25 10:01:01 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 博士 全职@Google - 网上海投 - Onsite |Fail

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

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

x
今天接到HR电话,表示HC不推荐move forward,虽然意料之中,还是可惜了这次机会了。

面经来了,安慰。。。。。顺求大米。。。。
. from: 1point3acres.com/bbs
1. Research Discussion 没写代码,只是讨论研究问题,论文题目。
2. Shadow Interview。 找单词游戏,4*4 找出在一个字典里的单词。字典应该提供什么API?代码见附件。
3. 给定一个方法:Stringdict(int index) 返回字典中第index单词。写一个方法,给单词输出index代码见附件。
午餐
4. 临时来的,骑自行车,出一身汗。。。。 很随意的一个人,问linuxsys call,没太明白问的是什么,说ls系统里发生了什么?之后代码题,给一个list,把重复的去掉。先写笨办法,一个新list,一个HashSet,从第一个到最后一个,如果set里没重复就加到新的list。然后要求inplace。接着问复杂度,一开始说是n,没考虑到从数组中删除时其实也是O(n)的。如果用链表倒是应该是O(n).最后例行讨论了他什么的project
5. 感觉最好的一个。234进制表示。原始办法,得到113,然后写一个函数来转换任意整数为nbase。写到一半,想到如果base超过36怎么办?不让用户转换!顺利完成,并简单测试。最后10分钟,BST,输出minto max之间的所有数。只说了想法。画了个实例,一开始找的停止遍历条件不对,后来讨论得到正确的条件,然后结束。

总结:
失败的原因在于自己刷题不够啊。刷题真的是王道啊。。。血的教训!拿谷歌练手第一面。。。。。


. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2014-11-25 10:31):.1point3acres缃
有没有大神在,求内推啊。。。

补充内容 (2014-11-26 05:06):
版主在吗?不顾NDA我把内容都发出来了竟然不给加大米啊?麻烦把这帖子删了吧。谢谢!

Interview code.pdf

278.9 KB, 阅读权限: 1, 下载次数: 485, 下载积分: 大米 -1 升

onsite

评分

17

查看全部评分

stellari 发表于 2015-6-26 01:03:55 | 显示全部楼层
volcano 发表于 2015-6-25 16:20
请问能解释下为什么不直接binarySearch吗?这个方法找区间和直接binary search 的time complexity 应该都 ...

这题我确实看不出为何不直接Binary Search。之前某位网友提到“先确定单词处于1,2,4,8,。。。, 2^(k-1), 2^k中的哪个范围,然后再Binary Search”,我的理解他是说“先用线性查找确定一个范围,再用二分法”。如果是这种方式,就会面临一个load imbalance的问题。就是:如果单词在字典中排序靠前,那么会很快容易被找到,但是如果靠后的话,就会需要找很多次。比如字典中有2^16个词,那么,用binary search可以保证在16次查找中找到任意一个词。但是,如果用那种先确定范围的方法则会出现这种情况,比如要找的单词是词典的最后一个词,它在2^15~2^16范围内。那么要先用15次线性查找才能找到这个范围,然后再用15次二分查找找到最后一个词,总共是30次查找。这比二分查找差多了。

我看楼主附件中的代码,也是纯二分搜索。并没有所谓的先确定范围这一说。
回复 支持 1 反对 0

使用道具 举报

rettyye3 发表于 2014-11-25 10:26:48 | 显示全部楼层
patpat

第三个应该是先 1, 2, 4, 8, ..., 2^k, 2^(k+1)... 这样比 确定了区间之后再二分吧?

第五个 超过36 可以用其他字母来替代么? ascii就能扩展到200多进制吧
回复 支持 反对

使用道具 举报

 楼主| 生活在大农村 发表于 2014-11-25 10:29:34 | 显示全部楼层
rettyye3 发表于 2014-11-25 10:26
patpat

第三个应该是先 1, 2, 4, 8, ..., 2^k, 2^(k+1)... 这样比 确定了区间之后再二分吧?

3. 应该都可以吧,就看字典原来有多长了。跟面试官讨论就可以了。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
5. 为了简单,直接归定不可以超过36.
回复 支持 反对

使用道具 举报

shirleywwww 发表于 2014-11-25 11:07:02 | 显示全部楼层
⊙﹏⊙b汗,我遇到的题跟你这些比起来简直弱爆了……
回复 支持 反对

使用道具 举报

 楼主| 生活在大农村 发表于 2014-11-25 11:08:29 | 显示全部楼层
shirleywwww 发表于 2014-11-25 11:07
⊙﹏⊙b汗,我遇到的题跟你这些比起来简直弱爆了……

你的更简单吗?看来真是看RP了。。。。有offer了吗?
回复 支持 反对

使用道具 举报

Dexter_syr 发表于 2014-11-25 11:14:06 | 显示全部楼层
求问lz哪里面的啊? NYC or MV?
回复 支持 反对

使用道具 举报

Dexter_syr 发表于 2014-11-25 11:14:39 | 显示全部楼层
shirleywwww 发表于 2014-11-25 11:07. 1point 3acres 璁哄潧
⊙﹏⊙b汗,我遇到的题跟你这些比起来简直弱爆了……

求问大神哪里面的啊? NYC or MV ?
回复 支持 反对

使用道具 举报

 楼主| 生活在大农村 发表于 2014-11-25 11:15:18 | 显示全部楼层
Dexter_syr 发表于 2014-11-25 11:14. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
求问lz哪里面的啊? NYC or MV?

我在MTV面的。。。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2014-11-25 11:46:25 | 显示全部楼层
为啥超过36不能转换?
回复 支持 反对

使用道具 举报

 楼主| 生活在大农村 发表于 2014-11-25 11:55:59 | 显示全部楼层
houqingniao 发表于 2014-11-25 11:46
为啥超过36不能转换?

可以转换,只要能找到字母使用就行了。懒
回复 支持 反对

使用道具 举报

shirleywwww 发表于 2014-11-25 12:36:34 | 显示全部楼层
Dexter_syr 发表于 2014-11-25 11:14. more info on 1point3acres.com
求问大神哪里面的啊? NYC or MV ?

在MTV面的
回复 支持 反对

使用道具 举报

shirleywwww 发表于 2014-11-25 12:38:26 | 显示全部楼层
生活在大农村 发表于 2014-11-25 11:08. From 1point 3acres bbs
你的更简单吗?看来真是看RP了。。。。有offer了吗?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我面的有一个是面经里的,但当时做的跟看面经时想的解法不一样。
有一个是类似你这个字符串去重的,其他都不难,就是followup有点小trick。
有offer了
回复 支持 反对

使用道具 举报

 楼主| 生活在大农村 发表于 2014-11-26 05:04:30 | 显示全部楼层
shirleywwww 发表于 2014-11-25 12:38
我面的有一个是面经里的,但当时做的跟看面经时想的解法不一样。
有一个是类似你这个字符串去重的,其他 ...

恭喜啦!
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-26 07:47:29 | 显示全部楼层
rettyye3 发表于 2014-11-25 10:26. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
patpat

第三个应该是先 1, 2, 4, 8, ..., 2^k, 2^(k+1)... 这样比 确定了区间之后再二分吧?

你的想法是对的,就是比较2^k的元素和要查找的。确定一个search 区间[2^{k - 1}, 2^{k}].然后再做binary search
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-26 07:48:58 | 显示全部楼层
houqingniao 发表于 2014-11-25 11:46
为啥超过36不能转换?

楼主的意思可能是说,大于10 的数都用一个字母表示。一共26个字母+ 10 个digits = 36个。
回复 支持 反对

使用道具 举报

 楼主| 生活在大农村 发表于 2014-11-26 07:59:06 | 显示全部楼层
averillzheng 发表于 2014-11-26 07:48
楼主的意思可能是说,大于10 的数都用一个字母表示。一共26个字母+ 10 个digits = 36个。

是的,其实有几个字母并不重要在这个问题里。我是这么觉得。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-26 10:27:02 | 显示全部楼层
楼主能解释一下,第4题的O(n) in place的算法吗? 难道list是有序的?
回复 支持 反对

使用道具 举报

hardworking 发表于 2014-11-27 10:57:36 | 显示全部楼层
楼主你好, 你说的第4list是个listnode链表呢?还是说arraylist<string>?是有序还是无序呢
回复 支持 反对

使用道具 举报

safeng 发表于 2014-12-4 04:58:38 | 显示全部楼层
shirleywwww 发表于 2014-11-25 12:38
我面的有一个是面经里的,但当时做的跟看面经时想的解法不一样。
有一个是类似你这个字符串去重的,其他 ...
. 鍥磋鎴戜滑@1point 3 acres
我感觉我面的比lz要难,也有offer了,赶脚lz应该多做做题啊,然后感觉如果OS学过了,sys call和ls啥都应该都不是问题~~
不知道shirley为啥说比lz简单,会了不难,难了不会,是不是问到的有些是准备过了,觉得简单了呢?PS:shirley你是女生吗,听说狗狗挺看重diversity~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 08:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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