google onsite 分享 mountain view

原帖地址:一亩三分地

上周四去的onsite。之前过了一轮面经我分享过了。可以去我的帖子里找,应该容易找到。
一共4轮,感觉并没有地里其他面经那么难。感觉还不错,题目也都做出来了。却跪了不知道是不是跟政策和大选有关。

第一轮一个白人。开始给一共book 的class。里面有一些variable 比如string author;string title;等 叫我实现function,findbookbyauthor() and findbookbytitle(); 开始犹豫用两个hashmap会不会太占空间,跟面试官交流了一下,说没问题。那就开始写了。这个函数问题是同一个author肯能会有好多book,所以在map里面存的是一共linkedlist不是直接book。follow up一是怎么加一共排队序列,就是可能有一些人要预约这本书,再follow这个排队序列可能是有一些用户有高priority怎么处理,再follow up现在有一个rating,每本书都有评分,怎么找到所有books在给定的rating范围内。就好了。
后来你说是我总是要提醒,但是我感觉我是一写这有问题,自己还没开始检查自己的代码他就提醒我了,他不提醒我我也是会发现的嘛。。。

第二轮是个阿三, 这个我是真感觉坑。介绍一下一个项目,他自己根本没听我讲的样子,眼神游离。叫我写个function返回给定序列的所有子集。element就是integer。我开始写一个for循环n从1到n代表子集element个数,空的循环完加上,里面在调用helper返回对应个数的sub set combination。他竟然看不懂,看不懂!!!然后叫我走一遍{1,2,3}这个例子,我给他解释了好久,再加上他叫我求复杂度。。这里就浪费了十几分钟。最后他才说想用2^n的方法,就是所有子集应该是从n=0到n-1,对应的element可能加也可能不加进去,就这样迭代下去,复杂度是2^n。还说这个简单,当时还愣住了,难道真是这个简单,然后时间就到了,实际上现在想想不太对。

第三轮还是一个白人,开始warmup问我,如果现在开会有一个人急着走,但是他电脑里有100gb的数据怎么快速practical得拷到另一个电脑上。一顿扯淡。然后就到了一题最绕的了。plus 1,但是给的数可能很长,也行有千万位,怎么处理?这题开始被自己绕住了,吧自己和面试官都整糊涂了,不过最后还是做出思路吧helper写出来了。就是没有最优化到底,你们自己想会吧,我先不说我的方法。

第四轮是最好的一轮最后给feedback也是positive。不过感觉也不是很难。先说两个文件每行里面都是一个数字,很多很多行内存可能存不下了,要求做点乘,得到结果。就是两个文件每一行相乘之后,所有这样的乘积相加。而且两个文件里面数据很parse就是很多数字是0. 开始一下子忘了parse这个条件,就说先读个一定行数,比如100行,乘了相加,完了继续读一百行,如此反复到结束。后来她提醒说很多零,我想了想,还是说没区别,因为你数据不应该一行一行读然后判断,因为从disk读很慢,读了一行,看是不是零是零就跳过,处理再读一行再处理这样太慢。如果直接读一百行然后相乘的时候判断对应行是不是零和直接不判断相乘加入结果差不多,因为乘以零和加零速度都很快。没必要ifelse。最后她说好像是的。然后说我的解决方法没有问题但是她不是这个意思。她说想让我做一个structure压缩一下数据,压缩后想还原回去也是可以的。然后我觉得这样用array,arraylist或者nodelist都可以,最后我用了nodelist,然后写代码,一阵写,followup如果两个文件不同行数,怎么处理,就结尾的时候处理一下,改代码。第二题是positive sequence 找是不是存着连续数列使得相加和等于给定target。开始直接two pointer window得到结果,属于greedy algorithm,写完了,她看感觉不对,太快了。于是followup 说如果有negative number呢,我开始说negative也行吧,后来发现不行,然后我就用dp,blabla写完code。终于结束。最后一轮面了一个多小时。不过值了。

anyway,最后还是decline了。恩,看来得继续刷题,刷个跟熟练就好了。
给大家分享,希望有用。本人已经伤不起。。。。疗伤去了。