一亩三分地论坛

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

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

Google新鲜热乎电面

[复制链接] |试试Instant~ |关注本帖
ceciyyl 发表于 2016-9-9 05:51:08 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
一个前端妹子问了我这个题。。。。攒rp。。。 大家加油!!!Finding a 2D array inside a bigger 2D arrayExample:
big_grid
1234
1234
1234 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1234

small
12. from: 1point3acres.com/bbs
12

return true;

big:
1234. from: 1point3acres.com/bbs
1234
1234. 1point 3acres 璁哄潧
1234.鏈枃鍘熷垱鑷1point3acres璁哄潧

small:
22. Waral 鍗氬鏈夋洿澶氭枃绔,
22
. 1point 3acres 璁哄潧
return false
. From 1point 3acres bbs
. from: 1point3acres.com/bbs



评分

1

查看全部评分

aangel 发表于 2016-9-9 09:17:06 | 显示全部楼层
xihaokai1 发表于 2016-9-9 09:09
一些有tradeoff的“优化”:
1. dp记录大矩阵的sum, 然后在上面扫和小矩阵一样大小的submatrix,如果sum相 ...

最后都是要暴力比较小矩阵的,还不如直接在大矩阵里一个一个比较top leftmost point的值来的快
回复 支持 1 反对 0

使用道具 举报

happypig95 发表于 2016-10-19 23:56:35 | 显示全部楼层
2D Rabin-Karp Linear time Linear space. 呵呵了卷积
回复 支持 1 反对 0

使用道具 举报

aangel 发表于 2016-9-9 06:20:20 | 显示全部楼层
直接暴力解法?. 鍥磋鎴戜滑@1point 3 acres
在大的2D array里面一个一个找,找到左上角一致的数字后接着搜小的2D array,
有能优化的地方吗?
回复 支持 反对

使用道具 举报

 楼主| ceciyyl 发表于 2016-9-9 06:26:21 | 显示全部楼层
aangel 发表于 2016-9-9 06:20
直接暴力解法?
在大的2D array里面一个一个找,找到左上角一致的数字后接着搜小的2D array,
有能优化的 ...

我是暴力解的。。。走远了
回复 支持 反对

使用道具 举报

UpDownDOTA 发表于 2016-9-9 06:47:03 | 显示全部楼层
暴力解完是不是该问follow up了?有没有提示往什么方向优化呢
回复 支持 反对

使用道具 举报

daddyyang 发表于 2016-9-9 07:17:40 | 显示全部楼层
看着像dp解法...除了暴力解还有什么方法吗?
回复 支持 反对

使用道具 举报

南慕伦 发表于 2016-9-9 07:50:26 | 显示全部楼层
这个题挺难的啊,应该不是经典算法题,这个事情在图像里经常做,做法是用小图像在大图像上做卷积,找最大值点,然后这方面有很多优化算法,一个常见的优化好像是把小矩阵分解成两个向量的外积,然后横着做一次卷积,竖着再做一次卷积。
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-9-9 09:09:54 | 显示全部楼层
一些有tradeoff的“优化”:
1. dp记录大矩阵的sum, 然后在上面扫和小矩阵一样大小的submatrix,如果sum相等再进行暴力比较。. from: 1point3acres.com/bbs
2. 比1更specific一点,用histogram(aka 数组)纪录小矩阵的数据分布。然后用dp纪录大矩阵的数据分布, 然后看有match的再进行暴力比较。
回复 支持 反对

使用道具 举报

aangel 发表于 2016-9-9 09:18:14 | 显示全部楼层
南慕伦 发表于 2016-9-9 07:50
这个题挺难的啊,应该不是经典算法题,这个事情在图像里经常做,做法是用小图像在大图像上做卷积,找最大值 ...

看到卷积就遁了,
看来这题只能暴力解,估计是面试官想放水吧
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-9-9 09:30:11 | 显示全部楼层
aangel 发表于 2016-9-9 09:17. 1point3acres.com/bbs
最后都是要暴力比较小矩阵的,还不如直接在大矩阵里一个一个比较top leftmost point的值来的快

. 1point3acres.com/bbs有些case 你要比较到最后几个值才知道不match, 比如很差的情况
1111        111
1111        111
1111        112
1112
回复 支持 反对

使用道具 举报

ivanml 发表于 2016-9-9 10:23:37 | 显示全部楼层
一种想法是:先找左上角,找到之后对比四个角,如果都相同再逐一比较,虽然还是暴力解,但是实际情况中效率比每次找到左上角就开始比较整个小矩阵会高很多。。
回复 支持 反对

使用道具 举报

南慕伦 发表于 2016-9-10 05:10:50 | 显示全部楼层
aangel 发表于 2016-9-9 09:18
看到卷积就遁了, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
看来这题只能暴力解,估计是面试官想放水吧

啊,我同学在我卷积的基础上想到了一个类似的方法,因为这题是exact match,所以可以任意抽一行和抽一列出来,对于每行每列做KMP,找到那些行列都匹配到的点暴力验证。
. 1point 3acres 璁哄潧
在大多数情况下这个做法都非常快,只是对于特别构造的worse case会退化到暴力做法。
回复 支持 反对

使用道具 举报

熊笨笨 发表于 2016-10-18 15:33:57 | 显示全部楼层
啊 lz你pass了嘛
回复 支持 反对

使用道具 举报

 楼主| ceciyyl 发表于 2016-10-19 01:30:48 | 显示全部楼层

并没有 :(
回复 支持 反对

使用道具 举报

robinbach 发表于 2016-10-19 15:22:14 | 显示全部楼层
再接再厉 lz加油

补充一下个人对解法的一些看法,这里假设两个矩阵的大小是n^2 和 m^2. :. more info on 1point3acres.com
1. 卷积确实很快,尤其是matlab里,但是仍然 (m^2 * n^2),感觉一般用于模糊匹配多. 卷积的优化不了解,不做评论,不过感觉worst cast不会改变,和暴力解区别不是很大,基本都是DFS。楼上有人提到的用求和 或者 histogram 优化接近于BFS后DFS,确实会有显著提高,因为 求和 和 histogram 用类似 sliding window sum 的方法可以做到O(n^2) , 相对于整体的话,这一部分预处理的复杂度基本可以忽略。
2. 我目前能想到的最优解在worst case O(m^2 * n^2),amortized O(m^2 * n * logn)。不过基本上是纯BFS的算法,类似于histogram的进阶版,思路是参考2D string search, 详见:
http://exceptional-code.blogspot.com/2012/02/solving-boggle-game-recursion-prefix.html

基本思路就是先搜小矩阵的第一个元素,记录下幸存的点然后继续搜小矩阵第二个元素。
大概步骤:
建立hashset1把所有大矩阵的点放进去,建立空hashset2:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
外循环遍历小矩阵元素,设为S[i,j], 坐标 i,j =  0 ~ m:
  内循环遍历对每个在hashtable中的位置,设为L[x,y]:
    若 (S[i,j] == L[x,y] 并且 hashset1 中 x,y 的上一个点(一般为 x-1,y) 存在), 则把x,y 放进hashset2中
  内循环结束swap两个hashset
最后输出hashset2是否为空就行了
. more info on 1point3acres.com
这个算法的优点是重用性强,对于大量输入,或者小矩阵元素重复率很高的话,使用前缀树(prefix tree or trie)可以大幅提高性能。比如
1 2 1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1 2 2. Waral 鍗氬鏈夋洿澶氭枃绔,
1 2 3
这种例子就可以逐行建立前缀树搜索,不过面试半个小时我可写不出来前缀树

补充内容 (2016-10-19 15:28):
想想应该是 amortized O(m^2 * n)。如果矩阵中数字取0~K的话,内循环按照 T(n) = T(n/K) + O(n) 来算应该是O(n)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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