一亩三分地论坛

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

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

Google面经 已挂

[复制链接] |试试Instant~ |关注本帖
lvlingsheng 发表于 2016-4-20 11:31:59 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
上周三面试的,今天接到电话说已经挂了。

Google的面试给我留下了很好的印象,因为做的比较规范,最后反馈也都是电话告知结果,非常正规的感觉。

我当时面试的时候运气不错,是一个美国小哥,题目也蛮简单的。第一题是给两个string,其中一个string比另外一个多了个字母,返回这个字母。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一题就用了最简单的比较,比较每一个字母(按照顺序就可以了),注意一下边界条件,最后一个的边界条件。

Follow up是如果字母顺序打乱了怎么找。我先说了HashMap,要写的时候想起来另外一个方法,就是把所有的ASICII加起来,减一下,得到的就是多出来的那个。 我就直接说了这个,然后写了这个。写完之后小哥问了一下时间空间复杂度,然后说你已经把本来要提升的东西做了、

然后给了个第三题,是说如果说要实现一个数据结构,要有insert(), delete(),medium(),mode()方法,怎么写。
. 鍥磋鎴戜滑@1point 3 acres
这题感觉是我最后被拒的原因,因为我感觉我没正确理解他的意思。因为这里你用LinkedList()也好,ArrayList()也好,总会有一个时间复杂度会很高,后面结束的时候想想可能是想让我比较每种结构的优缺点。

我当时是写了一个Arraylist的,他问如果找中位数怎么办,是不是会time complexity很高,然后我说每个结构都会有缺点,是个trade off。

最后时间也不够,因为是额外加的,草草结束了这题。

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
其实答完感觉还可以,不过最后还是挂了。

Move on了,不过HR还是很nice,今天电话告知我挂了之后问我要不要点学习资料,还发了学习资料,然后说8到12个月以后再见。 整体对google的招聘印象很好

评分

2

查看全部评分

duduhaha 发表于 2016-4-20 12:16:59 | 显示全部楼层
mode()是干啥的?

第三题用TreeMap就行了吧
回复 支持 反对

使用道具 举报

Dream_Hunter 发表于 2016-4-20 12:27:22 | 显示全部楼层
duduhaha 发表于 2016-4-20 12:16
mode()是干啥的?

第三题用TreeMap就行了吧

mode是求众数。也就是出现次数最多的数。这样需要返回所有的可能的mode嘛?
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-4-20 13:55:56 | 显示全部楼层
第一个题用异或做可以么,相加还是会溢出的吧,如果string很大的话
回复 支持 反对

使用道具 举报

 楼主| lvlingsheng 发表于 2016-4-20 13:57:31 | 显示全部楼层
mingzhou1987 发表于 2016-4-20 13:55. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一个题用异或做可以么,相加还是会溢出的吧,如果string很大的话
. 鍥磋鎴戜滑@1point 3 acres
异或应该也可以的
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-20 14:42:14 | 显示全部楼层
第一题两个string相同字符对应的index也一样吗?
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-20 14:42:41 | 显示全部楼层
请问 找mode element 有什么efficient的方法么
回复 支持 反对

使用道具 举报

 楼主| lvlingsheng 发表于 2016-4-20 14:43:13 | 显示全部楼层
caiqi8877 发表于 2016-4-20 14:42
第一题两个string相同字符对应的index也一样吗?

没错的
回复 支持 反对

使用道具 举报

 楼主| lvlingsheng 发表于 2016-4-20 14:43:57 | 显示全部楼层
adiggo 发表于 2016-4-20 14:42
请问 找mode element 有什么efficient的方法么

这里我觉得不管用什么数据结构,总会有问题的,要不就是mode差,要不就是insert差,要不就是找中位数差,应该是想让你讲trade off吧. 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-22 06:59:24 | 显示全部楼层
我觉得第二题可能面试官想考的是BST + Max Heap. 每个node里面加一个count就可以了,这样找中数,平均数都是O(1)  insert和delete是lgN
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-22 07:17:58 | 显示全部楼层
hidden_track 发表于 2016-4-22 06:59
我觉得第二题可能面试官想考的是BST + Max Heap. 每个node里面加一个count就可以了,这样找中数,平均数都 ...

两个priority queue可以很容易的找到medium,但是加上count之后,好像也得挨个挨个看哪个node是众数?可以写一下代码参考一下吗?
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-22 09:30:22 | 显示全部楼层
hidden_track 发表于 2016-4-22 06:59
我觉得第二题可能面试官想考的是BST + Max Heap. 每个node里面加一个count就可以了,这样找中数,平均数都 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
我觉得你的想法应该是对的,所有操作时间都是lgN,只不过BST的delete相对比较不好写呀。

补充内容 (2016-4-22 10:25):
仔细一想,最大堆也不好写,insert和delete分别该对最大堆做什么?求教
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-22 10:01:33 | 显示全部楼层
yueliu2366 发表于 2016-4-22 09:30
我觉得你的想法应该是对的,所有操作时间都是lgN,只不过BST的delete相对比较不好写呀。
. Waral 鍗氬鏈夋洿澶氭枃绔,
要我面,直接打开普林斯顿老头的代码开抄。。。。。。思想不难就是写起来麻烦点
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-22 10:38:21 | 显示全部楼层
yueliu2366 发表于 2016-4-22 09:30
我觉得你的想法应该是对的,所有操作时间都是lgN,只不过BST的delete相对比较不好写呀。

补充内容 (2016- ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
堆的话insert. delete确实比较麻烦....但我觉得面试官看思路吧....实在不行就先写个BST的版本,然后O(n)的时间找mode。。最后在提下用heap可以优化到O(1)
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-4-23 04:09:53 | 显示全部楼层
hidden_track 发表于 2016-4-22 06:59
我觉得第二题可能面试官想考的是BST + Max Heap. 每个node里面加一个count就可以了,这样找中数,平均数都 ...

找的不是平均数, 是medium, 用tree的话, 不能O(1)吧?
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-4-23 04:11:49 | 显示全部楼层
Mark6 发表于 2016-4-22 07:17
两个priority queue可以很容易的找到medium,但是加上count之后,好像也得挨个挨个看哪个node是众数?可 ...

不需要挨个看找众数, 只需要保存当前众数的count, 每次加入一个新的值的时候,比较count和众数的count, 并更新

补充内容 (2016-4-23 04:12):
不过需要用另外的数据结构保存每个数的Count
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-23 04:27:56 | 显示全部楼层
众数的部分搞一个HashMap<Integer, Integer> num----count;
再搞一个HashMap<Integer, HashSet<Integer>> count----num;
两个凑一块维护.

中位数的话,一个MinHeap, 一个MaxHeap. 维护size差小于1...
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-23 05:03:05 | 显示全部楼层
hyj143 发表于 2016-4-23 04:11.鏈枃鍘熷垱鑷1point3acres璁哄潧
不需要挨个看找众数, 只需要保存当前众数的count, 每次加入一个新的值的时候,比较count和众数的count ...

有道理!那在delete的时候也得更新,那如果到时delete到了当前的众数的节点,也就是当前众数不再是众数了,那还得挨个扫描剩下的所有的节点?

如果另外用一个heap 按每个数的count建堆怎么样?用来找众数。
然后另外两个heap 按每个数自身的大小建堆,用来找medium。。
回复 支持 反对

使用道具 举报

helloc93 发表于 2016-4-23 05:56:29 | 显示全部楼层
楼主可以分享下学习资料吗?google一直是dream,准备申他家全职
chhoward93@gmail.com
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-4-23 06:21:30 | 显示全部楼层
Mark6 发表于 2016-4-23 05:03. from: 1point3acres.com/bbs
有道理!那在delete的时候也得更新,那如果到时delete到了当前的众数的节点,也就是当前众数不再是众数了 ...

.鏈枃鍘熷垱鑷1point3acres璁哄潧对, 应该就是这样, 每次的操作都是Logn
我觉得从时间复杂度上来说, 这个应该很有优势了。 不顾占用空间有点大
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 23:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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