一亩三分地论坛

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

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

Google Onsite 10/26

[复制链接] |试试Instant~ |关注本帖
夜行码农耗子 发表于 2015-11-6 05:11:33 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Passfresh grad应届毕业生

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

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

x
昨天收到HR通知说已经通过了HC,正在焦急等待最后的结果,为了攒RP发一个面经希望能够帮助大家。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一面是个羞涩的印度小哥,题目说了一大堆但是基本上就是从N个数里面随机选出K个。楼主的做法非常Naive就是每次random一个数代表选择的,然后把这个数和最后一个数swap,然后继续做K次这样最后K个树就是选择出来的。Follow Up是给定的数字没有Fix Size,要求在任意时刻调用某Function都能生成随机的K个数字,楼主当时算概率算错了,小哥给我耐心的算了一遍。。做法挺简单的就是保存一个size 为K的数组,里面放着的是当前时刻选择出的数字,对每一个新的数字来的时候,该数字被选中的概率是 k/N,N为当前数字总和,如果选中了,那么要从之前保存的K个数字里面选择一个Drop,所有数字都是等概率的所以数组里任意元素被Drop的概率是1/K,然后用新的数字覆盖该位置就好。这样的话对于Stram我们只需要记一个Size为K的数组和一个count.每次调用该函数可以当成是在常数时间内完成。
第二面有点诡异,来了个白人小哥跟我说他是做图像是所以出一个图形处理的题,我当时就懵逼了因为不会,结果题目和图像没有任何关系 =- -=。题目是给一个Matrix代表一个图像,求每一行和每一列的和。。。。我当时反复确认了半天。。然后写了一个One Pass的方法,Follow Up是如果有Multi Thread的话应该怎么做,楼主又懵逼了因为不太会Multi Thread。想了想如果有什么很高端的方法可能需要考虑用锁而且效率并不一定高,于是和面试官说了这些之后写了个特别特别简单的方法- -就是把Matrix 尽可能的平均分成Block(先按行再按列),然后用MultiThread分别计算每个block的结果,这样就是2 pass因为行和列要分开算- -写完之后小哥竟然表示妥妥的- -,后面就聊了一会儿天。
第三面是一个白人阿姨非常和蔼,题目很简单就是给定了很多个string代表Path,求所有Path的最长公共Path。举个栗子就是/abc/def/g和/abc/def/h 的最长公共Path就是/abc/def。楼主第一反应就是Trie,跟阿姨说了之后阿姨只是笑说用那么麻烦吗,想了想好像不用- -于是就写了个非常Naive的方法,就是每次取一个path看一看在当前长度下是否满足所有Path在当前位置都包含,写完之后阿姨说我看你很想写Trie你可以写一个,写完之后阿姨说妥妥的。之后的Follow Up是如果需要得到的结果除了最长公共Path还需要知道比如每个当前目录下有多少Path之类的怎么办,我说这样的话Trie比较好,没有具体实现就扯了扯。再之后的题是那个经典问题就是一个Function有时候行有时候不行,确定不是输入的原因那么是什么原因,楼主在阿姨的启发下和面经的指导下装作脑洞大开说了一堆- -这里补充一个之前没看到的是我当时想到的就是也许会出现Buffer Overflow,这样的话因为不知道buffer外面是什么所以有可能这次能跑下次不行。面完这个阿姨说最后一个题给我个超级简单的,结果也的确是超级简单的,两个字符串一个比另一个多一个字母,如何找到那个不匹配的位置。我问阿姨有没有重复阿姨说你两种情况都说说,我说没有重复的话可以Binary Search有的话俩指针从头扫,当时的确没想到更好的方法,阿姨说可以。
第四面是个超帅的中国小哥,第一题就是Merge Internal。因为当时做这个题没有看别人的解法所以我就写了自己的做法,小哥表示他这个题面了很多人但是没人这么做,不知道我的方法对不对,他说直觉告诉他是对的,然后小哥苦思冥想了两分钟没有找到漏洞就说这办法可行。方法就是分别sort begin time 和end time。然后两个指针,如果begin time 小的话就说明在当前时间点有一个Internal要开始了那么count++,反之count--,记录一个最大值。我觉得挺常规的不知道别人都怎么做的,估计有更好的方法。之后的follow up是如果只有一个Room那么对于给定的一堆Internal求最多能举办多少个Meeting,楼主当时按照开始时间排序然后做了出来。做完小哥说这个题面了很多人依然没人这么做,苦思冥想之后说也是对的,之后我发现其实如果按照End Time排序会简单很多,虽然时间复杂度什么的都是一样的但是那样更好想。再之后小哥说来个Design吧,设计电梯那个,然后因为只有五分钟了小哥说这个算是额外的你写个Header File说说思路就好了,楼主就简单说了说,感觉不像在面试更像在聊天。面完之后小哥送我到停车场,一天的面试结束。
昨天接到电话HR说结果挺好的HC给的结果都是Recommended To Hire.因为楼主手上有个Offer昨天Deadline头脑一热就把那个Offer Decline了专心等这个,现在想想有点忐忑但愿一切都好吧。想着这半个月打Dota玩斧王从来不转玩PA从来不暴击,根据人品守恒定律人品余额应该还是有的,所以在此怒攒一波RP希望之后都顺顺利利的。
楼主的解法应该不算好还是希望大家如果有更好的想法能够分享。
希望大家都能有个好结果。
在此多问一句,HC过了之后对于New Grad来说后面出问题的几率大么。。。。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

MCwong 发表于 2015-11-6 05:50:39 | 显示全部楼层
第三面的naive讲法lz可以详细讲讲么? 我也是第一反应用trie,感觉trie还是好理解的。我还有一种解法,不知对不对(或者就是lz naive解法), 维护一个common path的String, one-pass, 每次都用common path和下一个Path String比较,找新的common path, 接着update common path. 扫完一遍最后的common path即为最长公共Path。
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-11-6 05:59:27 | 显示全部楼层
MCwong 发表于 2015-11-6 05:50
第三面的naive讲法lz可以详细讲讲么? 我也是第一反应用trie,感觉trie还是好理解的。我还有一种解法,不知 ...

是这么个意思!
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-11-6 06:01:13 | 显示全部楼层
MCwong 发表于 2015-11-6 05:50.鏈枃鍘熷垱鑷1point3acres璁哄潧
第三面的naive讲法lz可以详细讲讲么? 我也是第一反应用trie,感觉trie还是好理解的。我还有一种解法,不知 ...

不对,我是取第一个为common path,扫一遍,可以的话第二个。。一直到最后,你这个如果不匹配的话无法确定最长的啊- -
回复 支持 反对

使用道具 举报

言过饰非 发表于 2015-11-6 06:11:51 | 显示全部楼层
求问LZ四轮面试官的feedback是咋样的?全部positive嘛?我还在等HC所以想了解一下bar是咋样的,多谢多谢~~~
回复 支持 反对

使用道具 举报

MCwong 发表于 2015-11-6 06:14:26 | 显示全部楼层
夜行码农耗子 发表于 2015-11-6 06:01. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不对,我是取第一个为common path,扫一遍,可以的话第二个。。一直到最后,你这个如果不匹配的话无法确定 ...

可能我之前叙述的有点不清楚,Path的话总有一个"/"是公共的吧。
比如:-google 1point3acres
s1 = /abc/def,
s2 = /abc
s3 = /
s4 = /abc/def/ghi
. visit 1point3acres.com for more.我的想法就是维护一个cp,一开始cp就是s1.
然后cp和s2比, update cp = /abc
cp和s3, update cp = /
cp和s4, cp = /. from: 1point3acres.com/bbs
最后返回值就是"/"了,不知是不是lz naive方法的意思

回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-11-6 06:16:22 | 显示全部楼层
言过饰非 发表于 2015-11-6 06:11
求问LZ四轮面试官的feedback是咋样的?全部positive嘛?我还在等HC所以想了解一下bar是咋样的,多谢多谢~~~

HR给我打电话说都是Recommended Hire,我不知道是面试官的feedback还是HC的feedback。忐忑- -祝一切都好
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-11-6 06:16:52 | 显示全部楼层
MCwong 发表于 2015-11-6 06:14. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
可能我之前叙述的有点不清楚,Path的话总有一个"/"是公共的吧。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
比如:. from: 1point3acres.com/bbs
s1 = /abc/def,

恩恩,我理解错了~是这样
回复 支持 反对

使用道具 举报

言过饰非 发表于 2015-11-6 06:19:17 | 显示全部楼层
夜行码农耗子 发表于 2015-11-6 06:16
HR给我打电话说都是Recommended Hire,我不知道是面试官的feedback还是HC的feedback。忐忑- -祝一切都好
.鏈枃鍘熷垱鑷1point3acres璁哄潧
多谢~~ 一般过了HC都没啥问题,好运~~~
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-6 07:01:53 | 显示全部楼层
多谢分享。 LOL @ "半个月打Dota玩斧王从来不转玩PA从来不暴击"
回复 支持 反对

使用道具 举报

cocaptainco 发表于 2015-11-6 07:15:28 | 显示全部楼层
基本妥妥的。。。
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-11-6 07:43:17 | 显示全部楼层
marthew777 发表于 2015-11-6 07:01
多谢分享。 LOL @ "半个月打Dota玩斧王从来不转玩PA从来不暴击"

好基友开黑已经不带我了说我脸黑
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-6 09:58:54 | 显示全部楼层
夜行码农耗子 发表于 2015-11-6 07:43
好基友开黑已经不带我了说我脸黑
. 1point 3acres 璁哄潧
哈哈哈。。。
回复 支持 反对

使用道具 举报

ChloeF 发表于 2015-11-9 06:57:55 | 显示全部楼层
楼主 function一会行一会不行的面经你还有么
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-11-9 07:40:16 | 显示全部楼层
ChloeF 发表于 2015-11-9 06:57. 1point3acres.com/bbs
楼主 function一会行一会不行的面经你还有么

没有了- -你搜一下就在地里
回复 支持 反对

使用道具 举报

say543 发表于 2015-11-12 06:27:27 | 显示全部楼层
字符串一个比另一个多一个字母,如何找到那个不匹配的位置。binary search 要怎么做呢?
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-11-12 16:38:07 | 显示全部楼层
. more info on 1point3acres.com
楼主 function一会行一会不行 这个题你是怎么答的啊 我没搜到面经 55
回复 支持 反对

使用道具 举报

 楼主| 夜行码农耗子 发表于 2015-11-14 07:53:24 | 显示全部楼层
say543 发表于 2015-11-12 06:27
字符串一个比另一个多一个字母,如何找到那个不匹配的位置。binary search 要怎么做呢?

并不能做!这是当时面试官给我指出来的,我绞尽脑汁没想到怎么做。。
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-14 14:43:22 | 显示全部楼层
queeniejing 发表于 2015-11-12 16:38. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主 function一会行一会不行 这个题你是怎么答的啊 我没搜到面经 55
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
同问。这个答案是什么?
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-14 23:23:15 | 显示全部楼层
function一会行一会不行 这个题你是怎么答的啊 我没搜到面经 55 求啊~~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 11:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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