一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3841|回复: 8
收起左侧

Google onsite interview complete version

[复制链接] |试试Instant~ |关注本帖
Kelu 发表于 2015-9-2 07:26:12 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - Onsite |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
之前面试完发了一个简略的过程。今天接到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轴坐标重复点个数。. Waral 鍗氬鏈夋洿澶氭枃绔,
然后他问我这个最坏情况是什么,我说是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的是一层。

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二轮是个不苟言笑的大白:
先问了下之前的一个project。然后出了一个二叉树找最长连续递增路径的问题。. visit 1point3acres.com for more.
. more info on 1point3acres.com
这个问题我在地里看到过的,当时觉得太简单就直接跳过了。。。没想到写出了bug T_T
写完之后他提示我说输入单个点会怎样,我发现有bug,赶紧改了一下. from: 1point3acres.com/bbs
然后他又问用什么测试数据测试,我就画了几种不同的树的形状,结果他并不满意,让我想想用什么数据测试出程序里的bug。
我有点偷懒,不想想数据,就直接去看程序,结果看了半天也没看出来。问他要hint,面试官告诉我如果这棵树只有左子树,节点分别是1-2-1-2会怎样,我才发现我在扫描到子节点比父节点小的时候没有reset长度。。。

接着他问算法复杂度,我说是O(n)的,n是点的个数。接着他问如果这是个图怎么办?用相同办法做复杂度是多少?
我说是O(n^2),因为dfs完一条路径之后你下次再访问这条路径的某个点的时候你还需要再次更新这条路径接下来的所有点。
解决方法是lazy update,就是当一个点的父节点没有都更新完的时候不更新这个点的子节点,这样复杂度仍然是O(n)的。. From 1point 3acres bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这一面感觉有点坑,只答了一道题,还没找到bug。

第三轮又是个大白:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
先问了下我之前有关多线程的project。然后问我mutex的两种用法,我说可以用conditional variable,也可以直接lock。conditional variable的好处是可以及时通知被block的线程阻塞解除。
-google 1point3acres
接下来出了一道设计题:假设有个类叫做box,有两个函数分别叫做inc()和get(),初始时call get()会得到0,每调用一次inc(),get()的结果会增加1。现在这个类的作者声称inc()和get()都是多线程safe的,但你不太信任他,你怎么测试这个类。
我说可以用4个线程,两个分别调用inc(),两个分别调用get()并且检查是不是一直递增的(不需要严格递增)。这4个线程要同时启动,并且需要执行足够长时间。
他问我执行多长,我说十几秒或者一两分钟就足够了。
接下来他问,如果返回了一个correct一个error怎么办?我说那就是错误。
那么两个correct呢?我们可以很安全的假设那个类是对的。
那么如果只执行了一秒,得到了两个correct呢?这就不好说了。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
什么情况下类是正确的,但程序会返回error?那只能是integer overflow了。

然后又问我会怎么实现这个类,我提出两个方法,一个是直接lock住类里的那个value,另一个是用semaphore。
优缺点?semaphore允许多个用户同时访问get(),但是如果get()并不多就会花费多余的时间操作semaphore。(这里漏掉了一个缺点,也就是下一个问题)
用semaphore的话,如果有很多很多用户在get()会发生什么?inc()可能会被一大堆get()阻塞住,一直无法执行。
怎么解决这个问题?给inc()加个timer,到时间就强行让get()停下来等待它执行完。
这个并不实际,因为如果inc()被阻塞了,timer根本不会开始。有别的办法么?可以弄个controller,建立一个queue,get()插在后面,inc()直接加塞到最前面。
. 1point3acres.com/bbs
第四轮是个老中:
第一题:excel表头A B C D... AA AB... ZZAAA...对应从1开始的数字
怎么把数字和表头相互convert。这题在表头convert数字的时候出了个小bug,还好及时找到了。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二题:给10个machine,每个有100G的log,全是ip地址。怎样找到出现次数top 10的ip
我说可以用mapreduce,一个map两个reduce,map把ip映射成integer(当时没意识到ip其实就是一个integer),然后第一个reduce找出例如说ip的前8位在某个区间里的top10,第二个reduce综合这些top10找出最终的top10

那么没有mapreduce怎么做?我们可以先让10个machine相互通信,让第i个machine只有ip%10==i的ip。先独立运行,然后再综合起来得到结果。
他可能觉得我完全没按照他的思路来,就先假设只有一个machine,问我怎么做。 我说可以用hashmap记下每个ip出现次数,然后排个序。
这个复杂度是O(nlogn)的,有没有O(n)的做法?我想了下没想出来
用heap。但是heap也是O(nlogn)的啊。
你可以限制heap大小为10个。但这样就没有accurate的算法了
你先用hashmap记下ip出现次数,然后用heap去找top10。这才恍然大悟。。。
然后写完程序,先被吐槽了下读入list为什么要用index访问;改成iterator之后又说heap不要放在循环里面,这样比较慢;改出来之后有吐槽了一发C++标准库没有heap这个玩意儿,那个叫priorityqueue。
最后分析了个复杂度就结束了。

这一轮也有点瞎,面的时候脑袋发昏没好好想。当时就想了几秒没想起来就问hint了。。。现在回想起来这一题其实蛮简单,感觉不过都是我自找的。。。
. visit 1point3acres.com for more.
总结一下,最后不过的原因应该是蛮明显了,第二轮和第四轮都有点瞎,再加上本科GPA太低。今后还是要好好刷题好好做research才行。


评分

2

查看全部评分

本帖被以下淘专辑推荐:

hbsophia 发表于 2015-9-3 12:59:59 | 显示全部楼层
谢谢lz分享面经,祝lz好运!

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

使用道具 举报

hbsophia 发表于 2015-9-3 13:01:30 | 显示全部楼层
第一题也遇到过呢,到底该咋过呢?是求所有x坐标的mean ?
回复 支持 反对

使用道具 举报

jkl51310 发表于 2015-9-6 11:18:43 | 显示全部楼层
第一题我的想法是先假设轴线x=a存在,那么a值就是所有点中x的最小值和最大值相加除2。然后再把所有点按离轴线距离排序,距离一样则按y值排。再遍历一遍排好序的点即可判断是不是所有点都能找到对称点。
回复 支持 反对

使用道具 举报

peach=。= 发表于 2015-10-9 08:29:21 | 显示全部楼层
第一题我的想法是. 鍥磋鎴戜滑@1point 3 acres
1 先求所有点的x的平均值,同时把所有的点存入一个hashmap中,key是x值,value是y的hashset
2 遍历这个map中key小于平均值的entrySet,检查 1)对应的另一边的x在不在map中
                                                                           2) 如果在,比较这两个x值的y的hashset是不是equal
回复 支持 反对

使用道具 举报

goo 发表于 2015-10-9 15:11:46 | 显示全部楼层
peach=。= 发表于 2015-10-9 08:29
第一题我的想法是
1 先求所有点的x的平均值,同时把所有的点存入一个hashmap中,key是x值,value是y的hash ...

比较两个内有重复的set是否相同有点烦~~
回复 支持 反对

使用道具 举报

goo 发表于 2015-10-9 15:27:04 | 显示全部楼层
最后一题 hashmap记下ip出现次数后 怎么用heap去找top10啊 ? 没思路啊

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

使用道具 举报

bobzhang2004 发表于 2015-12-7 23:54:25 | 显示全部楼层
楼主第一题就是找x的median就行了吧,用quick selection可以做到O(n), 第二题就是leetcode原题Populating Next Right Pointers in Each Node II吧?
回复 支持 反对

使用道具 举报

csmargaret 发表于 2015-12-27 13:50:00 | 显示全部楼层
第二轮是和leetcode binary tree longest consecutive sequence一样吗?还是路径里既可以有parent to child也可以有child to parent呢?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 10:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表