Google新鲜热乎电面

一个前端妹子问了我这个题。。。。攒rp。。。 大家加油！！！Finding a 2D array inside a bigger 2D array

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
se

2D Rabin-Karp Linear time Linear space. 呵呵了卷积

xihaokai1 发表于 2016-9-9 09:09
一些有tradeoff的“优化”：
1. dp记录大矩阵的sum, 然后在上面扫和小矩阵一样大小的submatrix，如果sum相 ...

最后都是要暴力比较小矩阵的，还不如直接在大矩阵里一个一个比较top leftmost point的值来的快

再接再厉 lz加油

补充一下个人对解法的一些看法，这里假设两个矩阵的大小是n^2 和 m^2. ：
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是否为空就行了

这个算法的优点是重用性强，对于大量输入,或者小矩阵元素重复率很高的话，使用前缀树(prefix tree or trie)可以大幅提高性能。比如
1 2 1
1 2 2
1 2 3
这种例子就可以逐行建立前缀树搜索，不过面试半个小时我可写不出来前缀树

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

直接暴力解法？
在大的2D array里面一个一个找，找到左上角一致的数字后接着搜小的2D array,
有能优化的地方吗？

aangel 发表于 2016-9-9 06:20
直接暴力解法？
在大的2D array里面一个一个找，找到左上角一致的数字后接着搜小的2D array,
有能优化的 ...

我是暴力解的。。。走远了

暴力解完是不是该问follow up了？有没有提示往什么方向优化呢

看着像dp解法...除了暴力解还有什么方法吗？

这个题挺难的啊，应该不是经典算法题，这个事情在图像里经常做，做法是用小图像在大图像上做卷积，找最大值点，然后这方面有很多优化算法，一个常见的优化好像是把小矩阵分解成两个向量的外积，然后横着做一次卷积，竖着再做一次卷积。

一些有tradeoff的“优化”：
1. dp记录大矩阵的sum, 然后在上面扫和小矩阵一样大小的submatrix，如果sum相等再进行暴力比较。
2. 比1更specific一点，用histogram（aka 数组）纪录小矩阵的数据分布。然后用dp纪录大矩阵的数据分布, 然后看有match的再进行暴力比较。

南慕伦 发表于 2016-9-9 07:50
这个题挺难的啊，应该不是经典算法题，这个事情在图像里经常做，做法是用小图像在大图像上做卷积，找最大值 ...

看到卷积就遁了，
看来这题只能暴力解，估计是面试官想放水吧

aangel 发表于 2016-9-9 09:17
最后都是要暴力比较小矩阵的，还不如直接在大矩阵里一个一个比较top leftmost point的值来的快

有些case 你要比较到最后几个值才知道不match， 比如很差的情况
1111        111
1111        111
1111        112
1112