Google Onsite (onsite 地点在欧洲，伦敦)
本人 2013 9月毕业的master,在欧洲上学,申请 mountain view Software engineer,
new Grad.
现场提供Chrome book+Google Docs,如果有需要,不必白板
1. 简单的 if n even then n = n/2, if n odd then n = 3*n-1;
终止条件是 n==1
这似乎是一个数学证明上的难题,面试要求只是让我 n总共的 even count 和 odd
count
面试官从一开始就表示会有overflow,并且我们无法知道overflow的上界是多少.
我先无视overflow 条件,写出一般解法
然后接着分析: if n == odd, 3*n + 1 is even, then we can do: n = (3*n+1)/2 =
n + (n+1)/2
发现依然无法解决overflow的问题
然我我建议用BigInteger(面试官提示:you are on the right track). 此时我仍没想
到更好的解法
于是用C++ 写了BigInteger(也就是大数组)的 一个 multiple 和 一个 divide 函数
接着面试官说对于每一位我用vector<int> 太浪费,怎么优化. 我说 可以用char/或者
把一个int来装8位
面试官依然不满意,要求我不能浪费任何资源,我才灵光一闪:bitset
好吧 time out. 估计没什么好feedback...
2. find min and max in an array. 我用了最基本的解法
if (arr[i]<min) min = arr[i]
else if (arr[i]>max) max = arr[i]
然后面试官直接告诉我 有一个算法(算法导论上好像见过):
compare arr[i], arr[i+1] -> tmin, tmax
compare min, tmin
compare max, tmax
然后问我我的算法时空复杂度,最坏情况,以及他的算法的时空复杂度和最坏情况
并让我比较哪个方法在什么时候好
Snake and ledder: 求从src 到dest至少需要要多少次dice(dice:1-6)
不需要写代码. 让我跟他讲解决思路
我就给他走了一遍BFS.
follow up是:"how you gonna test it". 我想不到好方法.于是说:设计多个算法.比较
result.
3. 这家伙出了一个貌似自己也不怎么会做的题:
在x,y平面上有一些正方形的房子. 如果用它top, down, left, righ(data type:
float)来描述这些房子的话, down永远是0 (房子不会在天上)
接着把所有房子的正方形涂黑,要我list 黑色区域的顶点
我先打算枚举所有的case.枚举到一半面试官不是很满意,给我一个hint,让我先focus
on x轴
我和他一起试了一下 发现他的建议还不如我的(其实当时我也是脑子一片空白,所以如
果真有好解法没想到也未可知)
我后来跟他说一个computer vision里面常用的contour following 于是这道题变得非
常简单
把float映射到int,然后做contour following
可惜.我现在白板上写的,发现不合适,写起来太慢太麻烦,转到用Google Docs的时候,只
够把整个prototype写好,里面的细节没时间写了..
最悲催的一轮.一开始在Chrome book 里写就好了
午饭,一个中国小哥带我吃的. 不敢吃很多啊
4. 一个疑似巴基斯坦哥.(老印也有可能)
Topological sort. 他不让我写完代码,让我建个图就完事了,不用写后面的sort (不知
道是不是在整我)
一个更儿戏的设计题 根本没让我整理思路 就他一直在follow up:
先问我怎么设计一个 刷卡开门系统的数据库. 我还打算画一个state machine 给他
(这里略过我具体的回答)
a. 他说不用,就考虑lock - unlock状态,假设每个卡有一个id
b. 假设不同的门有不同的priority
c. 假设有些人的id可以同时打开Google Lond 和 Google MV的门
d. 假设这个人的卡丢了
, etc.
整个过程我都在见招拆招(所以feedback可能不会很好). 如果一开始把所有东西都考虑
一遍一步到位就好了.
5. 一个中国人
上来先问我对什么技术感兴趣啊什么的. 我先跟他走了一遍我学CS五年的历程已经自学
的经历.并说喜欢C++的开发之类的
5.1. an arbitrary tree. split it into as many subtrees as you can. the
number of nodes of the subtree must be even.
递归呗. 不算难. 只是树的描述应该是
struct Node{
int data;
list<Node *> nodes;
};
我一开始写成vector了,后来改的list
5.2 an online stream, with infinite numbers, tell me the most frequent
number
经典题啊 见过好多次,可惜我每次都没到google搜一下好的做法..囧
我先建议用 array 计算count + heap 得到the most frequent number. 由于 max
number = 2^64
这个方法要消耗大量的空间
接着我建议用hash + heap.
然后我主动说 由于是infinite的. 如果我们空间不够的时候.我们需要抛弃一些数据
于是我建议抛弃 heap的底部那些数据..
面试官不会上这个网站吧.. 遮脸 奔走..
去面试就是为了圆个Google onsite梦,结果已经不重要了.
由于习惯见招拆招,不善于未雨绸缪,可能有些面试官不会喜欢.
Anyway. Good luck everyone.
No comments:
Post a Comment