一亩三分地论坛

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

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

google两轮电面面经

[复制链接] |试试Instant~ |关注本帖
xuepanchen 发表于 2015-3-12 10:02:20 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other

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

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

x
今天刚面完GOOGLE二面,感觉不太好。发个面经和大家分享一下。

第一轮

应该是白人小哥,反正发音很标准。什么都没问,直接上题。

1. given two int arrays, determine whether one is permutation of the other。
做法很简单,先判断两个数组长度是否相同。之后对第一个数组建一个hashtable把所有出现的字符和出现的次数记录一下。然后扫一遍第二个数组,有相同的话就对应的出现次数减一。如果有字符的出现次数变成负数,就是false。


2. construct a binary search tree from a sorted int array
这题对建立的树完全没要求,我还特意问了建的tree要不要balanced,面试官说无所谓。我还是取中间的数作为root,然后recrusively的处理左右子树。因为我建立node的时候用的都是root=new node(val)操作,所以在最后都要用delete操作把开的内存收回来。平时刷题的时候从来不会在意这些,面试的时候写完了面试官说有一个问题,我看了半天说能不能给点hint,他说了memory leak我就懂了

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二轮


运气很好应该还是个白人小哥,他说了名字不过我没听清楚。先大致问了一下最近在做些什么,然后就简历上的一个project简单说了一下。之后上题,就一道题。

.1point3acres缃
在一个二维平面上,有很多个点。然后在原点有一个摄像机,摄像机可以看到一定角度内的东西,比如30度。然后问你这个摄像机要放在多少度角,它能看到的点最多。无论点离原点多远,只要在角度内都能看到。比如把摄像头放在0度的地方,那摄像头就能看到0到30度之内的所有点。
float GetBestDirection(float *arrX, float *arrY, int n, float f) {},arrX和arrY就是所有点的x和y坐标,n是一共n个点,然后f就是摄像机能看到多少的角度


我一开始想到leetcode上那道maximum points on a line。
我就说先建个hashtable,key是slope,value是有相同slope的点的个数。我说因为float有精度问题,可能同一条线上的点算出来的slope会有一点点差异但是就没法插到hashtable里去了,面试官说那你就当做没有点是在同一条直线上的。
然后我说还需要处理垂直线的特殊情况,还有就是相同slope的点可能是在对角的象限里面。等table建立好以后,用一个长度为摄像机所能看到角度的window,从table的头扫到尾,看哪个window里面的点最多。扫到最后的时候还要把最开头的点包含进去,相当于你扫过一圈又回到开始。
反正就是写了好半天,最后估计面试官也看不过去了,和我说有个函数叫float atan2(float, float)的函数可以用,我说挖槽,有这个函数,都不用考虑垂直或是在对角象限的问题了,太简单了
反正最后也就基本写了个大概,估计有不少bugs。面试官说时间也到了,有什么问题就问吧,然后就结束了。. 鍥磋鎴戜滑@1point 3 acres

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
说一点感想:
1. 不知道大家有没有这么觉得,刷题刷多了思维有点僵化,遇到一道题就开始往自己熟悉的方法上套,如果都套不上就会有点不知所措。我leetcode刷了两遍,一遍认真一遍回顾,CTCI大致刷了一遍。应该还是我做题太不认真,没有举一反三,融会贯通。
2. 本来也就是自己的第二家面试,很紧张。还是需要多打怪升级刷经验才行。写code不一定要bug free,但一定要体现出你思维的逻辑和严谨。第二面的题大家可以讨论讨论有什么好的做法,先谢过大家了.鐣欏璁哄潧-涓浜-涓夊垎鍦


最后祝大家都能好运,都能拿到满意的offer。也给自己求点人品,虽然希望不大还是求一求onsite :D



评分

1

查看全部评分

woshiee123 发表于 2015-3-15 09:45:44 | 显示全部楼层
第一面的第二题 收回了内存 不是刚建好的树就不存在了么?
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-4-27 15:43:29 | 显示全部楼层
woshiee123 发表于 2015-3-15 09:45. 鍥磋鎴戜滑@1point 3 acres
第一面的第二题 收回了内存 不是刚建好的树就不存在了么?

同问这个问题啊。。。
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-4-27 15:58:42 | 显示全部楼层
第二题把所有点得夹角排序,然后二分法找角度范围小的那一边,这样30度的区间肯定在这边选。如果一边区间范围小于30度,就往另一边一个一个延伸直到满30度?
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-28 02:19:17 | 显示全部楼层
woshiee123 发表于 2015-3-15 09:45. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一面的第二题 收回了内存 不是刚建好的树就不存在了么?

抱歉忘了说了,面试官是要求把树的节点打印出来,而不是存起来返回。所以全都打印完之后要把树删掉
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-28 02:19:33 | 显示全部楼层
wangxinlei 发表于 2015-4-27 15:43
同问这个问题啊。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
抱歉忘了说了,面试官是要求把树的节点打印出来,而不是存起来返回。所以全都打印完之后要把树删掉
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-28 02:24:03 | 显示全部楼层
wangxinlei 发表于 2015-4-27 15:58
第二题把所有点得夹角排序,然后二分法找角度范围小的那一边,这样30度的区间肯定在这边选。如果一边区间范 ...

二分法不对吧?可能是我没理解你的意思。比如0~30度有10个点,30~60度有30个点,60~90度有20个点,90~120度有20个点,按照二分的话第一步之后就只看60~120度范围了,但很有可能最多点的范围是在60度之前。
我的意思就是,虽然二分之后某一边可能角度范围比较大,但是其中可能会有点很密集的一部分,所以二分不能保证找到点最多的范围
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-4-28 02:34:37 | 显示全部楼层
xuepanchen 发表于 2015-4-28 02:24
二分法不对吧?可能是我没理解你的意思。比如0~30度有10个点,30~60度有30个点,60~90度有20个点,90~120 ...

楼主说的有道理,是我想简单了。
那可以存下区间,比如角度是15,就存-15-15,代表如果camera在-15到15之间肯定能看到。
然后对这n个区间先排序(按起始角度),对每个再求最多覆盖的?要O(n2)
不知道楼主用的什么方法?
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-28 05:00:19 | 显示全部楼层
wangxinlei 发表于 2015-4-28 02:34
楼主说的有道理,是我想简单了。
那可以存下区间,比如角度是15,就存-15-15,代表如果camera在-15到15 ...

我当时的做法是,先把所有点按照夹角排序好,然后维护一个大小为CAMERA视角的WINDOW,从0度开始扫一遍。始终保持WINDOW的大小,扫的过程中不断有点离开WINDOW也有点进入WINDOW,用一个变量存WINDOW所能涵盖的点个数的最大值。最后扫完返回这个最大值
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-4-28 06:55:43 | 显示全部楼层
xuepanchen 发表于 2015-4-28 05:00
我当时的做法是,先把所有点按照夹角排序好,然后维护一个大小为CAMERA视角的WINDOW,从0度开始扫一遍。 ...

这怎么扫一遍啊?一度一度的加么?那中间有小数的度数不是会忽略?
还是比如角度的排序为
{20,30.5,40,50,78.3,90}
先设window为20-50,扫整个array,记下有4个点,再把window设为30.5-60.5,扫整个array,记下有三个点,直到window为90-120,记下1个点。
这种?
回复 支持 反对

使用道具 举报

 楼主| xuepanchen 发表于 2015-4-28 08:24:04 | 显示全部楼层
wangxinlei 发表于 2015-4-28 06:55
这怎么扫一遍啊?一度一度的加么?那中间有小数的度数不是会忽略?
还是比如角度的排序为. 鍥磋鎴戜滑@1point 3 acres
{20,30.5,4 ...

我解释一下,假设排序之后的角度数组为{14,14.6,20,28.5,30.4,32.7,34.5,40,45,50},然后给你的摄像机视角为15度。WINDOW的左端从第一个数14开始,右端一直向右延伸,保证最右端的数字不大于14+15,获得的第一个WINDOW就是{14,14.6,20,28.5}。
之后每次WINDOW左端右移一位,右端尝试延伸,始终保证最右端的数字不大于起始数字加上视角角度。这样整个扫一遍你会陆续得到{14.6,20,28.5},{20,28.5,30.4,32.7,34.5},{28.5,30.4,32.7,34.5,40},{30.4,32.7,34.5,40,45},{32.7,34.5,40,45},{34.5,40,45},{34.5,40,45,50}
最后当右端扫到最后一个数了,就可以结束了,然后过程中记录最大值
写了好多。。。希望能看懂
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 22:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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