一亩三分地论坛

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

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

10.28 Google面经回馈(附个人解法)

[复制链接] |试试Instant~ |关注本帖
nevets 发表于 2016-11-2 22:08:42 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x
我面的是Google Singapore,所以题目对北美或者其他地区的朋友可能没什么帮助,但是大家满看一下吧。
-google 1point3acres
首先最大的感觉是懵逼,很多平时觉得 哦很简单 的题目能给你问出花来。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一面,三哥第一问:如何存储一个电话簿。追问:如果要求输入一个子串,如何给出所有包含该子串的所有名字。第二问:标准LRU实现。
. Waral 鍗氬鏈夋洿澶氭枃绔,
这题还算基础,没啥难点。第一问本问直接用trie就行,追问直接用suffix array+二分查找。LRU实现没出什么其他问题。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

第二面,俄罗斯大叔:第一问判断一个数是否中心对称,比如101,818这样的;第二问给定一个n,求n位数以内所有的中心对称数。

记得好像做过类似的题目,leetcode上可能有,但是忘了。第一问我的做法是生成中心对称然后比较是否相等,有个corner case是生成对称数的时候要用longlong存,因为可能会有166666666这样倒过来超界了的。第二问分奇偶讨论,奇数seed:0 1 2 5 8,偶数seed:11 22 55 69 88 96,然后放队列里,每次出队一个,然后两边加上0 1 2 5 6 8,其中6和9要注意一下。. 鍥磋鎴戜滑@1point 3 acres

第三面,国人大哥:如何只通过shuffle和remove构造最长的回文串,第一问能做出来就行,第二问要求除了新串之外只能用一个额外变量。

LC409 拓展,输出回文数版。本问不难,直接用hash统计每个char出现的个数,然后偶数全进去,奇数删一个再全进去就行,输出纯粹体力活,没啥说的。然后重点来了,这尼玛第二问是怎么回事(黑人问号??)一个变量没有hash你特么逗我?后来在提示下想到一个非常妙的解法:

用一个int32(可以看成是一个32位bool数组)记录每一个char是否出现过,然后开始读input,如果当前字符没有出现过,通过位运算在bithash里把这个字符对应的位mark为1表示出现过了;如果该字符出现过,清空该bit,然后加入输出。读完input之后看我的bithash是否为0,如果不为0,随便拿出一个mark了的bit对应的char append到输出,否则跳过这步。最后一步是翻转现在的输出串(要注意一下,如果之前一步加入了某个char,这里要从倒数第二位开始翻转)append到原输出串,操作完成。

看一个样例:
ababca 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

读到ab之后,这两位在bithash里被mark了;读到第三位a的时候,因为a已经被mark了,所以unmark并且加入输出;第四位b同理;第五第六位都只在bithash里mark,不加入输出。这时候的输出串是:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
ab
而且bithash不为0。所以这时候我们取出最低位1对应的char加入输出,于是输出变成 abc。由于加入了新字符,所以从倒数第二位开始翻转,于是得到最终输出abcba。

这个做法全程只用一个额外32位int作为hash,是原本开 int hash[26]的1/26。-google 1point3acres
. 鍥磋鎴戜滑@1point 3 acres
第四面,越南小哥:给两张手机上长网页的截图,输出一整张合并后的截图。

先解释一下题意,比如一个网页非常长,然后我想用手机把整个网页截下来。于是我分几次截图,每次截图一部分,但是为了让我的读者明白两张图的连接点在哪,所以我会截一些上一张图的底部,这样读者能通过对比两张图的相同部分来进行拼接。现在的问题就是我想用一个程序完成这个操作,怎么办。

于是难点就是,如何甄别一张图底部和另一图头部重叠的部分。这题本身不难,我先把每一行算一个hash出来,然后就相当于对两个数组进行比对。但是蛋疼的是corner case。有这么几个corner case需要考虑:
1. 加入两个截图算出来的行特征值是 [3,4,1,2,1,2], [1,2,1,2,5,6],这时候如果你从第一张图底部开始做match就会出事,因为会过早判定出现内容相同;. from: 1point3acres.com/bbs
2. 如果一个网页有恒定的漂浮物,header或者footer,怎么办。我这里是直接把两张图相减,对于一个区域内0值超过阈值的部分标示为common part不做处理,然后只处理非common part;
3. 如果header footer或者漂浮物99%相同,但只有略微区别怎么办。用2的办法直接干。

第五面,老三哥:给一棵树,每个节点有一个颜色,RGB中的一个,或者是empty,规定一棵树合法必须满足:1.一个颜色节点直接和empty相连,或;2.一个颜色节点通过相同颜色的节点和empty相连。验证一棵树合法。


到了这里我已经晕了,而且面试官似乎没有办法理解我的做法让我感到略微尴尬。而且这题到最后我发现了我code一个明显的bug,甚至可能是算法设计的问题,但是面试官似乎没有发现。

.1point3acres缃
我首先提出可以先找到所有的empty node,然后对相同颜色的node做floodfill然后check是否覆盖了整棵树。然而面试官直接shutdown了这个做法,说这棵树非常大,先找empty node太慢了。我说找empty node可以在读图的时候就做,面试官强行说不可以make the assumption。好吧,换做法。


想了老半天,感觉面试官觉得我是个连递归都不知道用的sb,开始提示说要不试试递归?我说肯定要递归但是怎么个递法我特么还没想好😂这里我有点急了,感觉最后一面不要崩,但是越这样想越头疼。然后大概过了好一会吧,我自己都不知道过了多久,可能是1分钟,也可能是5分钟,我想到了一个解法:
如果该节点不是空,那么以该节点为根的子树合法必须:
1. 和该节点不同颜色的儿子节点所在子树必须全部合法,并且;
2. 和该节点相同颜色的儿子节点所在子树中至少有一棵包含直系空节点。(这点在面试的时候做错了,完全没想到,太慌了)

总结. Waral 鍗氬鏈夋洿澶氭枃绔,
就我的面试而言,第五面直接错了加上是三哥面,基本稳跪了,不可能会给过的。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
.1point3acres缃
有一个面试技巧大家要记住,一定要和面试官交流,获得一些提示,这样能更清晰的design和优化算法。很多问题都不是面试官前一天准备然后第二天直接问的,很多问题的解答都是在经历了几十个面试者之后一步步的想出来的。像这次的第三面,我相信面试官最开始也只准备了hash做法,后来慢慢的发现,诶似乎可以简化掉hash,于是这个就成了一个followup了。然后要体会到这种解法,除非你真的很牛直接想到了,不然自己干想很难,甚至连方向都没有。

.1point3acres缃
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

1

查看全部评分

本帖被以下淘专辑推荐:

mr530 发表于 2016-11-3 02:04:10 | 显示全部楼层
感觉你前4轮都不错啊,就一轮不好。。google要求这么高?
回复 支持 反对

使用道具 举报

elizabethxiazhi 发表于 2016-11-3 02:07:57 | 显示全部楼层
可以问下LZ人在哪里为啥要面google singapore么,感觉比北美难啊,和google  us 是分开招人么
回复 支持 反对

使用道具 举报

 楼主| nevets 发表于 2016-11-3 11:17:44 | 显示全部楼层
mr530 发表于 2016-11-3 02:04
感觉你前4轮都不错啊,就一轮不好。。google要求这么高?

根据最后recruiter给我的feedback,有两面的面试官给我的评价比较负面,尤其是第五面的面试官给我的评价很低,大概就是说基础知识不好之类,然后就跪了😂另外一个可能是第三面我要了hint吧。
回复 支持 反对

使用道具 举报

 楼主| nevets 发表于 2016-11-3 11:19:17 | 显示全部楼层
elizabethxiazhi 发表于 2016-11-3 02:07.1point3acres缃
可以问下LZ人在哪里为啥要面google singapore么,感觉比北美难啊,和google  us 是分开招人么

因为我现在在新加坡工作,暂时也没有去美帝的打算 :p
回复 支持 反对

使用道具 举报

mr530 发表于 2016-11-3 12:26:09 | 显示全部楼层
nevets 发表于 2016-11-3 11:17
根据最后recruiter给我的feedback,有两面的面试官给我的评价比较负面,尤其是第五面的面试官给我的评价 ...

第三面的人略坑啊。。我觉得那个follow up现想出来已经很好了。。。
回复 支持 反对

使用道具 举报

 楼主| nevets 发表于 2016-11-3 15:47:09 | 显示全部楼层
mr530 发表于 2016-11-3 12:26
第三面的人略坑啊。。我觉得那个follow up现想出来已经很好了。。。

这也无可奈何😂 可能他的bar比较高吧
回复 支持 反对

使用道具 举报

cezheng2 发表于 2016-11-3 18:22:05 | 显示全部楼层
谢谢楼主分享。感觉楼主应该是面了一天到最后有点晕,个人感觉第五面的题目比前四面都简单。。。
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-11-3 19:27:27 | 显示全部楼层
楼主运气不好, 碰到烙印。。
回复 支持 反对

使用道具 举报

 楼主| nevets 发表于 2016-11-3 21:59:46 | 显示全部楼层
cezheng2 发表于 2016-11-3 18:22
谢谢楼主分享。感觉楼主应该是面了一天到最后有点晕,个人感觉第五面的题目比前四面都简单。。。

多谢安慰,当时感觉就是懵了 >< 平时一直觉得这种树遍历的题目难不到哪去,结果这次死在这上面也是捶胸顿足 :(
回复 支持 反对

使用道具 举报

 楼主| nevets 发表于 2016-11-3 22:00:06 | 显示全部楼层
qiuxuxing007 发表于 2016-11-3 19:27
楼主运气不好, 碰到烙印。。

都是命
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-11-4 08:03:16 | 显示全部楼层
第一问 lc 379, lru cache是不是就是lc 里面lru cache的题目一模一样?
回复 支持 反对

使用道具 举报

 楼主| nevets 发表于 2016-11-5 16:39:14 | 显示全部楼层
qiuxuxing007 发表于 2016-11-4 08:03. more info on 1point3acres.com
第一问 lc 379, lru cache是不是就是lc 里面lru cache的题目一模一样?

第一问不是LC 379,那题是看下一个可以使用的号码,而这题是名字检索。第二问就是经典LRU。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 16:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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