一亩三分地论坛

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

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

1120 Google onsite + 1112PayPal on campus

[复制链接] |试试Instant~ |关注本帖
kl_hrz 发表于 2015-11-22 05:23:36 | 显示全部楼层 |阅读模式

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

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

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

x
LZ昨天面了Google,感觉已跪。思前想后,最终还是来po一个面经回馈地里。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一轮是个帅帅的国人小哥,给的题算查找吧。给定一个vector,找一对i, j 使得A[j]=A[i] + 1并且j - i最大。follow up是A[j] > A[i]即可,要nlogn。后面LZ脑卡并没有自己想出来解法。。。小哥给了大致解法让我implement查找,我说那就binary search然后写了写又跑了个test。

第二轮太戏剧性了。国人小哥面完我,问外面的三哥是不是下一轮面试官,三哥答曰我是来带他吃饭的。我心说schedule怎么还变了,说好的上午下午各两轮呢。。。anyway中国小哥走了,我也做好了吃饭的准备(心里还在反思上一轮),三哥忽然笑了,看着手机说我发现了一件很有趣的事,我是面试官不是lunch host,我们来做题吧。我顿时无语,心态没调回来,这一轮非常悲剧。第一题是判断两个树是否相似。相似的定义是根节点value一样且两个子树相似(可以左-左 + 右-右,也可以左-右 + 右-左,‘-’表示两棵树子树的对应关系)。recursion解决之后三哥问了时间复杂度,LZ开始脑卡,说是4^n,然后让优化。LZ就在白板上写啊写说感觉用个map搞类似dp并不能优化似的因为木有重复对比(LZ至今没想到怎么拿map合理存树的那个结构,当时是说map套map来存子树的对比结果)。。。三哥说要看你怎么用了,还提示我说array是怎么看相似的。。。总之又想了两分钟未果,三哥说要不我给你换个题吧。题目忘了不过似乎用BIT搞的,三哥表示可以。然后又出了一题说如何求3个8bit数的平均值(尽量准确),CPU是8位的且不支持浮点。LZ脑袋还是晕乎乎的,于是先跟他说了2个数的求法,然后说3个数好像不能只用位移和加法(竟然忘了除法这回事),直到最后忽然想起原来没有浮点除法还有整数除法,最后给的算式似乎也是有问题的。。。.1point3acres缃

真正的lunch host终于出现了,是个非常nice的新加坡小哥,他听说了我的悲惨遭遇表示会跟上面反映这事。。。LZ中午的食量大约是平常的五分之一,味增汤都喝不完。。。

下午第三轮,国人妹子+国人大叔host。妹子好Nice啊瞬间心里不那么紧张。妹子进来看了看黑板,慌张地问我说这是不是我上午面的题,我说是啊难道你也要问这个。。。她说是啊我得换个题了,第一次当面试官,并没有准备第二题。。。于是主面试官变成大叔,问了个sort linked list。。。LZ脑卡依旧先拿multimap搞的。。。然后大叔不满意,LZ给了mergesort,然后说了几种情况,跑了两个test。. visit 1point3acres.com for more.

第四轮是个酷炫的白人小哥,先是问的经典的二维矩阵update和query,然后出了个字符串题,问一个字符串是不是完全由同一个子串多次重复形成的。答完后时间快到了,就聊了聊,非常high。
. 鍥磋鎴戜滑@1point 3 acres
哎,说来说去还是LZ水平不够硬。。。而且真的是非常紧张= =LZ这个心理。。。哎。。。

顺带附上之前PayPal on campus题,就是run-length encoding和decoding。。。encoding时候还让我拿两种方法写while loop。。。前两天收到下一轮通知,似乎全是电面。。。

评分

6

查看全部评分

本帖被以下淘专辑推荐:

hebzai2005 发表于 2015-11-22 05:27:49 | 显示全部楼层
楼主应该给hr发email投诉一下三哥那轮的情况。
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-22 05:29:35 | 显示全部楼层
hebzai2005 发表于 2015-11-22 05:27
楼主应该给hr发email投诉一下三哥那轮的情况。

嗯,发了,HR表示会向三哥了解情况同时向HC反映。。。不知道会不会有用。。。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-11-22 05:59:46 | 显示全部楼层
楼主这好戏剧化。。紧张是正常的。我面其他公司onsite的时候。。一天吃不下饭..觉得肚子很饱.... 1point3acres.com/bbs
楼主加油。。祝你offer
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-22 06:06:01 | 显示全部楼层
三哥那轮真的好坑。。。。. more info on 1point3acres.com
请问第一轮使得A[j]=A[i] + 1并且j - i最大有没有时间复杂度和空间复杂度的限制?
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-22 07:03:32 | 显示全部楼层
leixiang5 发表于 2015-11-22 05:59
楼主这好戏剧化。。紧张是正常的。我面其他公司onsite的时候。。一天吃不下饭..觉得肚子很饱...
楼主加油 ...
. 1point 3acres 璁哄潧
哎,第一家就是Google,也是目前唯一一家。。。sigh。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. from: 1point3acres.com/bbs
谢谢祝福~
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-22 07:04:56 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-22 06:06
三哥那轮真的好坑。。。。
请问第一轮使得A[j]=A + 1并且j - i最大有没有时间复杂度和空间复杂度的限制?

我是直接hashmap存同一value最大和最小index做了个O(n)的。。。小哥似乎有其他和我略不同的做法不过对我的似乎也表示ok
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-11-22 07:36:33 | 显示全部楼层
楼主想请教一下:
第一题,小哥给的大致解法是什么?我觉得如果只要A[j] > A[i]的话,最优解怎么都要n^2,怎么才能nlogn呢?
第二题,三个八位数求平均,先加起来的话会overflow,求算每个数先取7位还是会overflow,该怎么做呢?
第三题,sort的时候要constant space吗?
第四题,字符串那个,时间是n^2么?就是假设子字符串长度是1,2,...n,看有没有满足的?还有更优解吗?求楼主不吝赐教啊!
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-22 10:28:38 | 显示全部楼层
silenceleaf 发表于 2015-11-22 07:36. visit 1point3acres.com for more.
楼主想请教一下:
第一题,小哥给的大致解法是什么?我觉得如果只要A[j] > A的话,最优解怎么都要n^2,怎 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
指教谈不上啦~

第一题小哥用另一个vector存了相当于cumulate min,比如{6, 2, 4, 5, 7}那就是{6, 2, 2, 2, 2},然后从后往前每个element做个查找就好。

第二题我从2个数入手和你想的差不多,相当于是(a >> 1) + (b >> 1) + ((a & 1) & (b & 1)),然后从此莫名给自己加上了个不能用除法只能用移位的限定,最后幡然悔悟。。。所以应该是a / 3 + b / 3 + c / 3 + (a % 3 + b % 3 + c % 3) / 3之类的吧。。。这个结果一定不会overflow因为它是三个不溢出的数的平均值。然而最后还是LZ脑卡,写成和2个数运算差不多的格式了,就是a / 3 + b / 3 + c / 3 + ((a & 1) & (b & 1) & (c & 1))。。。在回家的飞机上LZ想一头撞死。。。不过其实那轮我写出最后算式的时候三哥已经整理好东西准备走了,并没拍照或者记什么。。。

第三题,是的。现在想想可能quicksort更好一点。.1point3acres缃

第四题,我的思路是先求字符串长度的factor,然后在每次验证这个长为factor的子串能否符合条件之前先小小地剪枝一下,就是看s[factor]是不是与s[0]一样(虽然感觉用处不大。。。),如果一样再去检验后面的。这样大概是O(sqrt(n))?木有仔细验证过。。。

补充内容 (2015-11-22 10:31):
唔。。。我打的[ i ]都不显示。。。所以最后一段除了第一个factor表示的是一个vector以外,其他的都是factor[ i ]就是第(i + 1)个factor

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-22 10:28:54 | 显示全部楼层
silenceleaf 发表于 2015-11-22 07:36
楼主想请教一下:
第一题,小哥给的大致解法是什么?我觉得如果只要A[j] > A的话,最优解怎么都要n^2,怎 ...

指教谈不上啦~
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一题小哥用另一个vector存了相当于cumulate min,比如{6, 2, 4, 5, 7}那就是{6, 2, 2, 2, 2},然后从后往前每个element做个查找就好。.鐣欏璁哄潧-涓浜-涓夊垎鍦

第二题我从2个数入手和你想的差不多,相当于是(a >> 1) + (b >> 1) + ((a & 1) & (b & 1)),然后从此莫名给自己加上了个不能用除法只能用移位的限定,最后幡然悔悟。。。所以应该是a / 3 + b / 3 + c / 3 + (a % 3 + b % 3 + c % 3) / 3之类的吧。。。这个结果一定不会overflow因为它是三个不溢出的数的平均值。然而最后还是LZ脑卡,写成和2个数运算差不多的格式了,就是a / 3 + b / 3 + c / 3 + ((a & 1) & (b & 1) & (c & 1))。。。在回家的飞机上LZ想一头撞死。。。不过其实那轮我写出最后算式的时候三哥已经整理好东西准备走了,并没拍照或者记什么。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

第三题,是的。现在想想可能quicksort更好一点。

第四题,我的思路是先求字符串长度的factor,然后在每次验证这个长为factor的子串能否符合条件之前先小小地剪枝一下,就是看s[factor]是不是与s[0]一样(虽然感觉用处不大。。。),如果一样再去检验后面的。这样大概是O(sqrt(n))?木有仔细验证过。。。
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-11-22 10:48:25 | 显示全部楼层
kl_hrz 发表于 2015-11-22 10:28
指教谈不上啦~

第一题小哥用另一个vector存了相当于cumulate min,比如{6, 2, 4, 5, 7}那就是{6, 2, 2 ...

cumulate min的确很巧妙!那如果要A[j]=A + 1并且j - i最大,我的想法是sort一下数组,并且按照pair<val, position> 的方式sort,然后用two pointer的方式找相差最大的两个。你是用这种方式吗?
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-22 13:25:28 | 显示全部楼层
silenceleaf 发表于 2015-11-22 10:48.鐣欏璁哄潧-涓浜-涓夊垎鍦
cumulate min的确很巧妙!那如果要A[j]=A + 1并且j - i最大,我的想法是sort一下数组,并且按照pair 的方 ...

啊我没有sort,因为sort要nlogn。。。我就直接unordered_map<int, pair<int, int> >存每个val的第一次出现和最后一次出现的index,之后遍历这个hashmap找有木有key - 1就好了。。。于是就是O(n)。c++的unordered_map也是非常神奇,我不知道如何做到O(1)取begin和O(1)next的。。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-11-22 17:37:21 | 显示全部楼层
kl_hrz 发表于 2015-11-22 13:25
啊我没有sort,因为sort要nlogn。。。我就直接unordered_map存每个val的第一次出现和最后一次出现的index ...

那你说的要求nlogn的是follow up吗?用你说的那个方法新建一个cumulate min的方式,时间是n吧,为何是nlogn呢?
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-23 01:16:58 | 显示全部楼层
kl_hrz 发表于 2015-11-22 10:28
指教谈不上啦~
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一题小哥用另一个vector存了相当于cumulate min,比如{6, 2, 4, 5, 7}那就是{6, 2, 2 ...

三个8位数求平均。你可以把八位数拆成两个四位数就好了啊。分别对高四位和低四位求平均。再合并。
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-23 01:23:04 | 显示全部楼层
第一题是 2Sum。fullow up就先sort。然后binary search。
第二题:时间是T(n) = 4T(n/2) + 1 --> O(n^2). 优化没想出来:面试官给答案了么? 3个8位数求平均就是 将8位拆分成2两个4位分别处理。
第三题:就是mergesort。
第四题:啥是经典2d题?. Waral 鍗氬鏈夋洿澶氭枃绔,

楼主的题相比其它的不算最难的。
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-23 03:17:36 | 显示全部楼层
silenceleaf 发表于 2015-11-22 17:37
那你说的要求nlogn的是follow up吗?用你说的那个方法新建一个cumulate min的方式,时间是n吧,为何是nlo ...

第一题的follow up可能要求的是 A[j]-A 的最大值。这样才需要这个min的vector。而且应该O(n)就可以了。
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-23 08:42:49 | 显示全部楼层
silenceleaf 发表于 2015-11-22 17:37
那你说的要求nlogn的是follow up吗?用你说的那个方法新建一个cumulate min的方式,时间是n吧,为何是nlo ...

要二分法查找啊。。。

补充内容 (2015-11-23 08:54):. 鍥磋鎴戜滑@1point 3 acres
就是从后往前找j,看每个element对应前面哪一个index最小的可以符合要求的A[ i ]就好。搜一个比当前A[j]小的最大数是logn。我先说只要在0~j - 1范围搜,后来补充说这样有可能不行因为比如整个vec递减或者同值。。。
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-23 08:49:43 | 显示全部楼层
maomaoxiong 发表于 2015-11-23 01:23
第一题是 2Sum。fullow up就先sort。然后binary search。
第二题:时间是T(n) = 4T(n/2) + 1 --> O(n^2).  ...

第一题和2sum并没有关系吧。。。而且sort了之后index都乱掉了,我觉得并没有什么用。

以及的确不算难= =第二面就是坑。。。我掰了半天说按我的思路改hashmap没什么用,然后面试官给了hint也说是类似hashmap,不过我是至今没想出来。。。在这里也求各路大神指教= =
. Waral 鍗氬鏈夋洿澶氭枃绔,
3个8位数求平均真的可以这样拆么?我感觉会产生两部分误差哎。。。我最后给的处理方法大致是先各自除3之后求和,再算误差补上去,回来想了想感觉是可行的(虽然这题估计三哥还是会算我没做出来). From 1point 3acres bbs

补充内容 (2015-11-23 09:01):
唔你说第一题的原题么,那的确是。。。不过follow up感觉sort的确没啥用吧
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-11-26 13:03:06 | 显示全部楼层
第二题recursion的复杂度为什么是4 ^ n 呢, 用master method算应该是 n ^ 2?
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-26 13:10:43 | 显示全部楼层
LifeGoesOn 发表于 2015-11-26 13:03-google 1point3acres
第二题recursion的复杂度为什么是4 ^ n 呢, 用master method算应该是 n ^ 2?

. 1point3acres.com/bbs所以说脑卡= =想说4^(log2(n))=n^2写成了4^n,嗯。。。当时我写完就觉得不对,然后在白板前面纠结,三哥就笑着看我发傻。。。

而且LZ表示并不了解master method,大概需要补补基础了。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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