一亩三分地论坛

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

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

谷歌MTV Onsite面经

[复制链接] |试试Instant~ |关注本帖
crimsonfaith91 发表于 2016-9-21 12:32:40 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Google - 猎头 - Onsite |Otherfresh grad应届毕业生

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

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

x
第一轮:
(1) buy and sell stock with cooldown

第二轮:
(1) longest substring with at most k distinct characters
(2) 给一个byte array(一张黑白pixel的图片),怎么把它排成一个2D matrix。排后图片要make sense。
      e.g., given byte array = 110011001000
              应该把array排成:
              1100        110
              1100  或   011  或  其他等?
              1000        001
                              000
              第一种排法比较适合方形物体,第二种排法比较适合条状物体。

. from: 1point3acres.com/bbs
午饭:和一个小哥吃饭
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第三轮:
(1) 给两段话,看有多大程度的plagiarism。
(2) 给一个sorted array和一个target,找出与target的差最少的c个数。要求log(c)算法,注意不是log(n)。

第四轮:
(1) 给a bunch of relations in a company。
      e.g., {a-c, a and c are siblings}
              {a-b, b is a boss}
              {a-e, a and e are siblings}
      因为b是a的上司、a和e是同事,请测出b也是e的上司。
问题是design数据结构O(1)返回x是不是y的上司、上上司或上上上司等

帮朋友发的。大家加油!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

hxtang 发表于 2016-9-21 22:37:04 | 显示全部楼层
WhatsFLAG 发表于 2016-9-21 22:12
请问一下,排序的2c数组怎么二分找最接近target的c连续数字呢?

刚才脑残了各种typo...加上用了index i感觉把回答完全弄乱了
重新打一下:
假设target的index是k
二分搜子数组第一个元素的index j, k-c<=j<=k
子数组最后一个元素index j+c, k<=j+c<=k+c
(不等号是不是需要取等我没有细想,但是不影响最后结果和复杂度)
它们到target的距离是. 1point3acres.com/bbs
d1 = target - a[j]
d2 = a[j+c]-target
目标是希望|d1-d2|尽量小。因此就是搜a[j]+a[j+c]中和2*target距离最近的值
. Waral 鍗氬鏈夋洿澶氭枃绔,因为a sorted,所以a[j]+a[j+c]也sorted,就是标准二分找closest number

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

pottermarkken 发表于 2016-9-22 11:04:56 | 显示全部楼层
多谢LZ 分享面经!
回复 支持 1 反对 0

使用道具 举报

hxtang 发表于 2016-9-21 22:31:34 | 显示全部楼层
WhatsFLAG 发表于 2016-9-21 22:12 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
请问一下,排序的2c数组怎么二分找最接近target的c连续数字呢?

否则二分搜子数组第一个元素的index i, 范围在target的index前c个到target
. more info on 1point3acres.com子数组最后一个元素index i+c,范围在target的index到之后c个
它们到target的距离是. more info on 1point3acres.com
d1 = target - a
d2 = a[i+c]-target
目标是希望|d1-d2|尽量小。因此就是搜a+a[i+c]中和2*target距离最近的值
因为a sorted,所以a+a[i+c]也sorted,就是标准二分找closest number
回复 支持 1 反对 0

使用道具 举报

hxtang 发表于 2016-9-21 19:54:59 | 显示全部楼层
domofeng 发表于 2016-9-21 12:47 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
想问下楼主,

1. 给一个byte array(一张黑白pixel的图片), 这个题目是open ending? 要code吗?

sorted array找target那个问题,我猜是已知target位置的。这样可以直接从数组里圈定2c个candidate。
再从这里面找c个连续的数就是二分查找。
回复 支持 1 反对 0

使用道具 举报

hxtang 发表于 2016-9-22 02:03:22 | 显示全部楼层
WhatsFLAG 发表于 2016-9-22 01:06
您认为这个建模过程是考察什么能力的,我怎么感觉好像发明了一条定理一般。。。面试现场做出来感觉对现在 ...

其实我觉得就两点(1)你是不是理解sorted array和binary search (2)你看到题是试图去解决这个问题还是试图找模版往题上套。

我觉得大多数人(1)都能做得很好,但是(2)因为大家都刷题,所以有找模版的习惯,所以比较难做到。
比如这个题,如果你立足于去想怎么在很多candidate window里选出那个optimal的,那么自己画几个例子d1=d2的想法就出来了。如果你立足于想怎么binary search,就会卡住。

可惜的是现在的普遍做法就是刷(背)LC,越刷越套路...//顺路吐槽前几天被某内推“建议”再多刷几遍LC...
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-9-21 12:40:36 | 显示全部楼层
第四轮是怎么做到O(1)的呀?
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-21 12:42:09 | 显示全部楼层
第二轮(2)和第三轮(1)是open problem?
第三轮(2)挺有意思的,不过应该target在sorted array中位置是给定的,而且返回c个数的range就行吧。
回复 支持 反对

使用道具 举报

domofeng 发表于 2016-9-21 12:47:37 | 显示全部楼层
想问下楼主,

1. 给一个byte array(一张黑白pixel的图片), 这个题目是open ending? 要code吗?
2. 给一个sorted array和一个target,找出与target的差最少的c个数。要求log(c)算法,注意不是log(n)。 如何log(c)呀, 找到target在array中的位置就要log(n)呀?
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-21 21:19:02 | 显示全部楼层
hxtang 发表于 2016-9-21 04:54
sorted array找target那个问题,我猜是已知target位置的。这样可以直接从数组里圈定2c个candidate。
再 ...

感觉很有道理....
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-21 22:12:46 | 显示全部楼层
hxtang 发表于 2016-9-21 19:54
sorted array找target那个问题,我猜是已知target位置的。这样可以直接从数组里圈定2c个candidate。
再 ...

请问一下,排序的2c数组怎么二分找最接近target的c连续数字呢?
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-21 23:23:48 | 显示全部楼层
hxtang 发表于 2016-9-21 22:37
刚才脑残了各种typo...加上用了index i感觉把回答完全弄乱了
重新打一下:
假设target的index是k

感谢您的回复,“目标是希望 | d1 - d2 | 尽量小”对于我来说是这个题最没能想到的,感觉好捉急啊
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-21 23:50:18 | 显示全部楼层
WhatsFLAG 发表于 2016-9-21 23:23 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感谢您的回复,“目标是希望 | d1 - d2 | 尽量小”对于我来说是这个题最没能想到的,感觉好捉急啊

那里是要绕一下
我是先想了个简单的case,就是d1=d2的时候肯定已经找到了
再拓展出去想d1和d2不等的话怎么办,自己随便举了个例子就figure out了。
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-22 00:13:15 | 显示全部楼层
第四轮怎么解呢?o1的查询怎么做呢?
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-22 00:27:46 | 显示全部楼层
william_gong 发表于 2016-9-22 00:13
第四轮怎么解呢?o1的查询怎么做呢?

我猜建graph的时间不算在O(1)查询里
建graph可以先用sibling关系union find把人分组。union find用path compression扁平化,这样每个人一步能找到本组的representative (root)。然后扫一遍boss关系建一个hash map,如果a是b的boss,b的root是r,则建一个r->a的mapping

这样找一个人的老板分两步,首先找root,然后找root的老板,O(1)
找一个人老板的k次方就是2k步,只要k是常数就还是O(1)
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-22 00:30:34 | 显示全部楼层
hxtang 发表于 2016-9-22 00:27.鐣欏璁哄潧-涓浜-涓夊垎鍦
我猜建graph的时间不算在O(1)查询里
建graph可以先用sibling关系union find把人分组。union find用path  ...

我第一反应也是union find加hashmap,但这样有个问题, 如果是
boss(a,b)
boss(b,c)
boss(c,d)...
这种情况下时间复杂度会变成O(n)
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-22 00:43:14 | 显示全部楼层
william_gong 发表于 2016-9-22 00:30
我第一反应也是union find加hashmap,但这样有个问题, 如果是. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
boss(a,b). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
boss(b,c)
. 1point 3acres 璁哄潧
如果boss^n的n是变量,可以每个union find的root不仅存parent,还存祖先。这个只要有了parent信息以后dfs一遍就可以了。
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-22 01:06:50 | 显示全部楼层
hxtang 发表于 2016-9-21 23:50
那里是要绕一下
我是先想了个简单的case,就是d1=d2的时候肯定已经找到了
再拓展出去想d1和d2不等的话 ...

您认为这个建模过程是考察什么能力的,我怎么感觉好像发明了一条定理一般。。。面试现场做出来感觉对现在的我来说几乎不可能啊
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2016-9-22 05:04:41 | 显示全部楼层
wtcupup 发表于 2016-9-21 12:40. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第四轮是怎么做到O(1)的呀?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
初步想法是用hashmap + treemap / union-find。
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2016-9-22 05:06:46 | 显示全部楼层
hxtang 发表于 2016-9-21 12:42
第二轮(2)和第三轮(1)是open problem?
第三轮(2)挺有意思的,不过应该target在sorted array中位置是给定的 ...

第二轮(2)也许要用ML。. more info on 1point3acres.com
第三轮(1)个人觉得用rabin-karp会比较好。
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-22 05:12:28 | 显示全部楼层
hxtang 发表于 2016-9-22 02:03. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
其实我觉得就两点(1)你是不是理解sorted array和binary search (2)你看到题是试图去解决这个问题还是试图 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
我认为您给出的观点极具有有价值,谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 04:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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