当前在线人数8793
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
G家onsite面经
[版面:待字闺中][首篇作者:lvhemi] , 2012年06月28日11:21:57 ,9900次阅读,57次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
lvhemi
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: lvhemi (驴和咪), 信区: JobHunting
标  题: G家onsite面经
发信站: BBS 未名空间站 (Thu Jun 28 11:21:57 2012, 美东)

这周周二的onsite,一共五轮面试。安排比较混乱,其中一个interviewer,我干等了
半个小时,no show。联系HR,才知道这个interviewer已经休假5个月。所以后来又加
了一个interviewer。
感觉google的面试根本不考虑candidate的背景和经历,只考coding。我有朋友做到了
CS Top-4的正教授,去google面试仍然是一样的流程。这个确实让人非常frustrated。
1. Thesis discussion:老印,data base出身,鸡同鸭讲,面得很费劲,互相感觉都
不是很好。
2. 老中,coding:给一个N个node的BST,给一个Key,返回与key最接近的m个node(m<N
).
我开始说可以做inorder traverse,用一个priority queue保存跟key最近的m个value
,复杂度O(n);存在average O(log n)的算法,但不好写。结果还是被要求写O(log n)
的code。

这个算法不是很难(不确定是不是最优),但是在30分钟写出来确实不容易。
我的基本思路还是用priority queue,现在BST中查找key,返回指向value=key的node(
如果存在)或者应该插入该key的node(key不在BST中),然后从该node开始向前向后各m
次判断前驱或者后继是不是应该插入priority queue.

主要函数code最后虽然写出来了,不过lookUp、successor和predecessor这三个子函数
没来得及写。

3. 白人。问了一个随机采样方面的问题,比较简单。

3.5 lunch。以前实验室的一个哥们带我lunch然后骑着自行车在g campus逛了一圈

4.0 老中,no show

4.1 老白,讨论了一些research问题。然后最后5分钟的时候考了一个coding:给一个
很大的数组(比如全世界每个人的salary),找median

5.两个老印(其中一个负责观察):设计一个集合数据结构(set,只存unique的value)要求
能在O(1)时间内insert,delete,random query(比如目前set中有n个元素,给一个介
于1到n的随机数k,可以在O(1)时间内返回第k个value)

总体感觉面得非常不顺。不过自己尽力了,也没什么遗憾。希望对即将去面试的朋友有
所帮助。


--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 131.107.]

 
[分页:1 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996