我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
查看: 3975|回复: 14
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
snooze 发表于 2016-2-2 16:44:07 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

x
Google面经. 牛人云集,一亩三分地
第一面:.留学论坛-一亩-三分地
三姐,. from: 1point3acres
第一题:给两个相同的string A和B,然后其中一个在某个位置又新插入了一个char,找出这个char。
O(N)扫一遍就找出来了,思路说了然后码代码。
follow up:如果两个string 都被shffule过呢?直接想用两个map。三姐给hint“非要两个map麽”,好吧然后就优化成用一个map,思路说完就开始码代码。
然后自己没话找话,说follow up之前的原题,如果能给一个没有重复字符的假设的话,可以用二分搜索优化成O(logn),三姐说好啊你写写看。然后码代码。
之后问了一些list 和vector区别之类的问题。
. 牛人云集,一亩三分地
第二面:
国人小哥,. visit 1point3acres for more.
聊简历聊了一会,然后说给一堆简历,算每个简历的top k个高频词。
如果词频统计好,其实就是找数组里top k大的元素。我就说有两种方法,quick select和heap。讲了一下两种方法的思路,问了一下时间复杂度,问了一下堆的实现原理,然后就开始code:让我自己选一种方法实现(选了heap的方法)。
写完小哥就一直在看我代码,卡了很久(所以只做了一道题),说有问题,问为什么iterator我用''->"而不用".",可能小哥平时Java用的多吧。我说iterator是指针要用指针操作符,小哥说感觉还是不对...然后扯了半天,终于move on,说在一百万份简历中想找和当前简历最相似的一份,问怎么做。我说统计高频词,然后比较。小哥说如果名字,邮箱这样词频很低,但能让两份简历相关性提高很多的词怎么办。(我才意识到他想做的是简历查重?),我就说训练分类器,识别简历上类似名字,邮箱,电话这样的field(会出现在特定的position),让他们权重变大。考虑效率的话,可以上hadoop做。感觉和小哥交流莫名其妙的不顺畅,感觉跪在这一面,果然一周后让加面。
. 1point 3acres 论坛
第三面:
白人小哥,人很nice
1. Leetcode 原题Alien Dictionary 稍微改动:求原顺序和新顺序的对应关系。-google 1point3acres
如正常顺序是abc...xyz,新顺序是正常顺序的一个permutation,如cab...zxy。
那么要求的就是a->c, b->a..., 这样的对应关系。
问了一些问题,诸如两个相邻的string是不是只能确定图中的一条边?我说是。小哥说good, it's a trick question...
. 留学申请论坛-一亩三分地
2. Find identical subtree

先给了个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好像有些问题。。。小哥说没事,时间也差不多了,你来问问题吧。

(后来查了资料,设计hash function的方法时间复杂度是O(N^2) 详情可参考:http://stackoverflow.com/questio ... es-from-binary-tree)


一周前通知进Pool,发面经攒人品求match



补充内容 (2016-2-14 07:13):
已match,祝大家都有好的offer!
update一下timeline:
1/6/2016 一面二面
1/22/2016 三面
1/27/2016 进pool
2/11/2016 Match成功

评分

2

查看全部评分


上一篇:Amazon intern 电面
下一篇:HackerRank自家OA拿好不谢

本帖被以下淘专辑推荐:

我的人缘0
面无表情 发表于 2016-2-5 02:28:47 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
顶~楼主好棒,也是过五关斩六将,leetcode刷了好多的选手啊,赞
回复 支持 反对

使用道具 举报

我的人缘0
tong-1324 发表于 2016-2-5 05:53:47 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
恭喜~~~稳稳的match!
回复 支持 反对

使用道具 举报

我的人缘0
DreamBoy 发表于 2016-2-5 06:30:30 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
LZ Find identical subtree 这个题没弄明白意思==NAIVE的方法为啥是O(N^3)?为什么最后用hashing做?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| snooze 发表于 2016-2-5 07:41:13 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
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。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| snooze 发表于 2016-2-5 07:42:49 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
tong-1324 发表于 2016-2-5 05:53
恭喜~~~稳稳的match!
. 围观我们@1point 3 acres
谢谢JT~
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| snooze 发表于 2016-2-5 07:45:42 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
面无表情 发表于 2016-2-5 02:28 来源一亩.三分地论坛.
顶~楼主好棒,也是过五关斩六将,leetcode刷了好多的选手啊,赞

谢谢LA的大神
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
loloxfx 发表于 2016-2-7 08:46:41 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

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

使用道具 举报

我的人缘0
loloxfx 发表于 2016-2-7 08:47:10 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
哇!求match。。然后就可以帮忙refer了!!
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| snooze 发表于 2016-2-9 12:01:23 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
loloxfx 发表于 2016-2-7 08:47
哇!求match。。然后就可以帮忙refer了!!

必须的
回复 支持 反对

使用道具 举报

我的人缘0
新宿车站 发表于 2016-2-28 09:07:45 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
我也被加面 了。。。求问LZ我能不能问问HR为啥被加面。。。。能不能套出一点信息可以针对性的准备?
回复 支持 反对

使用道具 举报

我的人缘0
a66119685 发表于 2016-2-28 12:59:15 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
膜拜大神~~问下大神学习经验~~~除了刷leetcode还要做什么呢~~或者leetcode要刷多少遍呢~~
回复 支持 反对

使用道具 举报

我的人缘0
guixi107 发表于 2016-2-29 04:28:07 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
lz Find identical subtree

假如已经是2个string的话,用KMP比较的话, 不好不是应该是O(n), 为啥是O(n^2)?.留学论坛-一亩-三分地

Hash function的输入是什么? 如果二叉树有变化的(insert或者delettion)的话,怎么update hashcode呢?

谢谢
回复 支持 反对

使用道具 举报

我的人缘0
Shane_seu 发表于 2016-3-3 15:58:36 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
Con学长!好腻害!
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-28 16:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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