一亩三分地论坛

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

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

Google 实习 两轮电面+一轮加面 面经

[复制链接] |试试Instant~ |关注本帖
snooze 发表于 2016-2-2 16:44:07 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
Google面经. visit 1point3acres.com for more.
第一面:
三姐,
第一题:给两个相同的string A和B,然后其中一个在某个位置又新插入了一个char,找出这个char。-google 1point3acres
O(N)扫一遍就找出来了,思路说了然后码代码。
follow up:如果两个string 都被shffule过呢?直接想用两个map。三姐给hint“非要两个map麽”,好吧然后就优化成用一个map,思路说完就开始码代码。
然后自己没话找话,说follow up之前的原题,如果能给一个没有重复字符的假设的话,可以用二分搜索优化成O(logn),三姐说好啊你写写看。然后码代码。
之后问了一些list 和vector区别之类的问题。

第二面:
国人小哥,
聊简历聊了一会,然后说给一堆简历,算每个简历的top k个高频词。
如果词频统计好,其实就是找数组里top k大的元素。我就说有两种方法,quick select和heap。讲了一下两种方法的思路,问了一下时间复杂度,问了一下堆的实现原理,然后就开始code:让我自己选一种方法实现(选了heap的方法)。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
写完小哥就一直在看我代码,卡了很久(所以只做了一道题),说有问题,问为什么iterator我用''->"而不用".",可能小哥平时Java用的多吧。我说iterator是指针要用指针操作符,小哥说感觉还是不对...然后扯了半天,终于move on,说在一百万份简历中想找和当前简历最相似的一份,问怎么做。我说统计高频词,然后比较。小哥说如果名字,邮箱这样词频很低,但能让两份简历相关性提高很多的词怎么办。(我才意识到他想做的是简历查重?),我就说训练分类器,识别简历上类似名字,邮箱,电话这样的field(会出现在特定的position),让他们权重变大。考虑效率的话,可以上hadoop做。感觉和小哥交流莫名其妙的不顺畅,感觉跪在这一面,果然一周后让加面。

第三面:
白人小哥,人很nice
1. Leetcode 原题Alien Dictionary 稍微改动:求原顺序和新顺序的对应关系。
如正常顺序是abc...xyz,新顺序是正常顺序的一个permutation,如cab...zxy。
那么要求的就是a->c, b->a..., 这样的对应关系。
问了一些问题,诸如两个相邻的string是不是只能确定图中的一条边?我说是。小哥说good, it's a trick question.... more info on 1point3acres.com

2. Find identical subtree
. Waral 鍗氬鏈夋洿澶氭枃绔,
先给了个O(N^3)的Naive方法,小哥说能优化吗?
我说可以通过判断树高来优化。
小哥说还能优化吗?
我就说可以考虑把tree序列化成一个string后,变为找相同substring。但我又说,想要为一确定一棵tree似乎同时需要inorder和preorder traverse才行。
小哥说没事,假设我们现在有一个修改过的preorder traverse方法,能够唯一地确定tree,那怎么做。.鐣欏璁哄潧-涓浜-涓夊垎鍦
我说那就好办了,借助KMP算法,可以把复杂度降成O(N^2),讲了一下具体思路。
小哥说good idea。还有没有别的方法呢?
想不出来了。。。经小哥提醒,可以设计一个hash function,get到idea后(具体看下面的链接),然后我设计的hash function好像有些问题。。。小哥说没事,时间也差不多了,你来问问题吧。. 1point3acres.com/bbs

(后来查了资料,设计hash function的方法时间复杂度是O(N^2) 详情可参考:http://stackoverflow.com/questio ... es-from-binary-tree) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


一周前通知进Pool,发面经攒人品求match. 1point3acres.com/bbs
. From 1point 3acres bbs


补充内容 (2016-2-14 07:13):
已match,祝大家都有好的offer!
update一下timeline:
1/6/2016 一面二面
1/22/2016 三面. 1point3acres.com/bbs
1/27/2016 进pool.鐣欏璁哄潧-涓浜-涓夊垎鍦
2/11/2016 Match成功

评分

2

查看全部评分

本帖被以下淘专辑推荐:

面无表情 发表于 2016-2-5 02:28:47 | 显示全部楼层
顶~楼主好棒,也是过五关斩六将,leetcode刷了好多的选手啊,赞
回复 支持 反对

使用道具 举报

tong-1324 发表于 2016-2-5 05:53:47 | 显示全部楼层
恭喜~~~稳稳的match!
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-2-5 06:30:30 | 显示全部楼层
LZ Find identical subtree 这个题没弄明白意思==NAIVE的方法为啥是O(N^3)?为什么最后用hashing做?
回复 支持 反对

使用道具 举报

 楼主| snooze 发表于 2016-2-5 07:41:13 | 显示全部楼层
DreamBoy 发表于 2016-2-5 06:30
LZ Find identical subtree 这个题没弄明白意思==NAIVE的方法为啥是O(N^3)?为什么最后用hashing做?

先实现一个比较两个root tree是否相同的函数compare(root1, root2),这个函数的复杂度是O(N). 然后对于原始tree中的所有两两节点的pair(假设是 a 和 b),调用compare(a, b)判断以a,b为root的两个子🌲是否相同。共有O(n^2)这样的pair,所以总时间复杂度是O(N^3)。hashing的方法是小哥提示的,应该是他的expectation solution。
回复 支持 反对

使用道具 举报

 楼主| snooze 发表于 2016-2-5 07:42:49 | 显示全部楼层
tong-1324 发表于 2016-2-5 05:53
恭喜~~~稳稳的match!

谢谢JT~
回复 支持 反对

使用道具 举报

 楼主| snooze 发表于 2016-2-5 07:45:42 | 显示全部楼层
面无表情 发表于 2016-2-5 02:28. 1point3acres.com/bbs
顶~楼主好棒,也是过五关斩六将,leetcode刷了好多的选手啊,赞

谢谢LA的大神
回复 支持 反对

使用道具 举报

loloxfx 发表于 2016-2-7 08:46:41 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

loloxfx 发表于 2016-2-7 08:47:10 | 显示全部楼层
哇!求match。。然后就可以帮忙refer了!!
回复 支持 反对

使用道具 举报

 楼主| snooze 发表于 2016-2-9 12:01:23 | 显示全部楼层
loloxfx 发表于 2016-2-7 08:47
哇!求match。。然后就可以帮忙refer了!!

必须的
回复 支持 反对

使用道具 举报

新宿车站 发表于 2016-2-28 09:07:45 | 显示全部楼层
我也被加面 了。。。求问LZ我能不能问问HR为啥被加面。。。。能不能套出一点信息可以针对性的准备?
回复 支持 反对

使用道具 举报

a66119685 发表于 2016-2-28 12:59:15 | 显示全部楼层
膜拜大神~~问下大神学习经验~~~除了刷leetcode还要做什么呢~~或者leetcode要刷多少遍呢~~
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-29 04:28:07 | 显示全部楼层
lz Find identical subtree
. 1point 3acres 璁哄潧
假如已经是2个string的话,用KMP比较的话, 不好不是应该是O(n), 为啥是O(n^2)?
-google 1point3acres
Hash function的输入是什么? 如果二叉树有变化的(insert或者delettion)的话,怎么update hashcode呢?. 鍥磋鎴戜滑@1point 3 acres

谢谢
回复 支持 反对

使用道具 举报

Shane_seu 发表于 2016-3-3 15:58:36 | 显示全部楼层
Con学长!好腻害!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 12:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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