家onsite面经

http://www.mitbbs.com/article_t1/JobHunting/32162725_0_3.html

 

这周周二的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)

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

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s