Google onsite interview complete version

之前面试完发了一个简略的过程。今天接到recruiter的电话说没有通过，如果我愿意当software testing engineer的话可以加面两轮再看结果。我虽然答应了，但是即便录用我大概也不会去，因为testing这个工作实在太无聊了。再加上一年冷冻期，Google这条路就算是断了吧。之前说过出了结果之后就发一下具体过程，如下：

第一轮是个老白，人非常nice
第一题：平面上很多点，选取一条垂直于x轴的线，使得这些点对于这条线轴对称。
我的思路是先算出mean，然后把这些点按x轴排序，然后对于从第0个到第n/2个点去找对应的n-i，看是不是

1. x[i]+x[n-i]==2*mean<span lang="ZH-CN">，</span>y[i]==y[n-i]

复制代码

然后他问如果有很多点x轴坐标相同怎么办。我说可以对于每个i，令j=n-i,一直往前扫描到

1. <p class="MsoNormal" style="margin-bottom: 7.5pt; background-image: initial; background-attachment: initial; background-size: initial; background-origin: initial; background-clip: initial; background-position: initial; background-repeat: initial;">x[i]+x[j] != 2*mean</p>

复制代码

这样其实有问题，但是当时我们都没有发现。然后他问我这个算法的复杂度是多少，我说是O(nlogn+nt)，n是点的个数，t是最大x轴坐标重复点个数。
然后他问我这个最坏情况是什么，我说是O(n^2)，就是所有点分别在两个不同的x轴坐标上。
接下来问怎么改进，使得除去排序部分外其它是O(n)
我说可以先根据y坐标排序，然后根据x坐标排序，对于每个y坐标的点集做之前的操作。

第二题：给一个任意形状的二叉树，怎样用linked list把同一层的node全都串起来。
我写了一个bfs，用hash map存储每一层最后一个点
然后他问能不能不用hash map，我说可以用vector，效果一模一样
然后他又问能不能vector也不用，我说可以把二叉树存到数组里，标号从2^n-1到2^(n+1)-2的是一层。


第二轮是个不苟言笑的大白：
先问了下之前的一个pr

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

O(nlogn)的啊。

你可以限制heap大小为10个。但这样就没有accurate的算法了

你先用hashmap记下ip出现次数，然后用heap去找top10。这才恍然大悟。。。

然后写完程序，先被吐槽了下读入list为什么要用index访问；改成iterator之后又说heap不要放在循环里面，这样比较慢；改出来之后有吐槽了一发C++标准库没有heap这个玩意儿，那个叫priorityqueue。

最后分析了个复杂度就结束了。

这一轮也有点瞎，面的时候脑袋发昏没好好想。当时就想了几秒没想起来就问hint了。。。现在回想起来这一题其实蛮简单，感觉不过都是我自找的。。。

总结一下，最后不过的原因应该是蛮明显了，第二轮和第四轮都有点瞎，再加上本科GPA太低。今后还是要好好刷题好好做research才行。

谢谢lz分享面经，祝lz好运！

在坛子里看到这个题目好多次了，请问这个题目具体是啥样子的？是不是把二叉树traverse一遍，然后就跟lc那个Longest Consecutive Sequence  一样了？哪个大牛给指点一下？

第一题也遇到过呢，到底该咋过呢？是求所有x坐标的mean ?

第一题我的想法是先假设轴线x=a存在，那么a值就是所有点中x的最小值和最大值相加除2。然后再把所有点按离轴线距离排序，距离一样则按y值排。再遍历一遍排好序的点即可判断是不是所有点都能找到对称点。

第一题我的想法是
1 先求所有点的x的平均值，同时把所有的点存入一个hashmap中，key是x值，value是y的hashset
2 遍历这个map中key小于平均值的entrySet，检查 1）对应的另一边的x在不在map中
                                                                           2） 如果在，比较这两个x值的y的hashset是不是equal

peach=。= 发表于 2015-10-9 08:29
第一题我的想法是
1 先求所有点的x的平均值，同时把所有的点存入一个hashmap中，key是x值，value是y的hash ...

比较两个内有重复的set是否相同有点烦~~

最后一题 hashmap记下ip出现次数后 怎么用heap去找top10啊 ？ 没思路啊

补充内容 (2015-10-9 15:38):
我想还是限制heap大小为10 遍历一遍hashmap就好了吧

楼主第一题就是找x的median就行了吧，用quick selection可以做到O(n), 第二题就是leetcode原题Populating Next Right Pointers in Each Node II吧？

第二轮是和leetcode binary tree longest consecutive sequence一样吗？还是路径里既可以有parent to child也可以有child to parent呢？