l*********y
发帖数: 52 | 1 请教大家两道和矩阵相关的google onsite题目，都是从面经中看到的~~
1： n x n parcels in city; matrix M contains the cost of each parcel;
budget B
largest rectangular area in the city you can afford.
2： 给你一个two dimensional array, array的元素是0或者1。问能不能找到一个矩
形，矩形的4个角都是1.
大家有没有好的解法，最优的时间复杂度是多少呢？可以一起讨论下，非常感谢！！ |
z***m
发帖数: 1602 | 2 第一题没有看明白
第二题，没一行，转成一个01序列，比如010101, 然后和第二行(010100)做add运算，
如果是0，就没有，如果有2个1，就是有这样的矩形。 |
c*****n
发帖数: 95 | 3 第一题应该就是find largest sum sub matrix 的变型吧。
遍历所有的矩形，如果其sum <= B 就试着更新最大面积 |
p*e
发帖数: 6785 | 4 niu
【在 z***m 的大作中提到】
: 第一题没有看明白
: 第二题，没一行，转成一个01序列，比如010101, 然后和第二行(010100)做add运算，
: 如果是0，就没有，如果有2个1，就是有这样的矩形。
|
d*****c
发帖数: 605 | 5 这个序列是binary的吗？还是直接加呢？我觉得不一定是跟下一行加吧，要loop下面所
有的？
请大牛指点
【在 z***m 的大作中提到】
: 第一题没有看明白
: 第二题，没一行，转成一个01序列，比如010101, 然后和第二行(010100)做add运算，
: 如果是0，就没有，如果有2个1，就是有这样的矩形。
|
o**********5
发帖数: 53 | 6 牛人说的 add 应该是 bitwise operation ^
a = 010101010
b = 101010101
然后，看看 (a^b) 的二进制表达式中有几个位置上的是大于1的。顺便还可以找出位置
来。
【在 d*****c 的大作中提到】
: 这个序列是binary的吗？还是直接加呢？我觉得不一定是跟下一行加吧，要loop下面所
: 有的？
: 请大牛指点
|
n***z
发帖数: 29 | 7 这样是要n^2吧，一行和下面每行相比，
但矩阵size超出32bit或者64bit呢，
general的方法即使用hashset还是n^3吧，
【在 o**********5 的大作中提到】
: 牛人说的 add 应该是 bitwise operation ^
: a = 010101010
: b = 101010101
: 然后，看看 (a^b) 的二进制表达式中有几个位置上的是大于1的。顺便还可以找出位置
: 来。
|
a******7
发帖数: 106 | 8 遍历所有的矩形 就是O(n^3)time
如果cost都是正的 应该可以做到 O(n^2) time, 需要额外O(n^2)space 算一个(0,0) ~
(i,j)和的矩阵A 再算一个(0,0) ~ (i,j)最小和的矩阵B
【在 c*****n 的大作中提到】
: 第一题应该就是find largest sum sub matrix 的变型吧。
: 遍历所有的矩形，如果其sum <= B 就试着更新最大面积
|
j*********6
发帖数: 407 | 9 没太看懂 能举个例子不？ 多谢！
【在 z***m 的大作中提到】
: 第一题没有看明白
: 第二题，没一行，转成一个01序列，比如010101, 然后和第二行(010100)做add运算，
: 如果是0，就没有，如果有2个1，就是有这样的矩形。
|
z***m
发帖数: 1602 | 10 不是牛人。
是需要每两行之间都要bitAdd一下， O(n^2)
当列数太大，超过64， 就用int数组吧。我想4G的bitmap都能实现，这种连续的内存区
间应该也不是太难吧。
【在 d*****c 的大作中提到】
: 这个序列是binary的吗？还是直接加呢？我觉得不一定是跟下一行加吧，要loop下面所
: 有的？
: 请大牛指点
|
|
|
b***e
发帖数: 1419 | 11 遍历所有的矩形是O(n^4)时间。
~
【在 a******7 的大作中提到】
: 遍历所有的矩形 就是O(n^3)time
: 如果cost都是正的 应该可以做到 O(n^2) time, 需要额外O(n^2)space 算一个(0,0) ~
: (i,j)和的矩阵A 再算一个(0,0) ~ (i,j)最小和的矩阵B
|
a******7
发帖数: 106 | 12 暴力的话是O(n^4) 可以用一个一唯数组保存上一次的结果 这样可以做到O(n^3)time O
(n)space
但我觉得这道题一定有O(n^2)的DP解法
【在 b***e 的大作中提到】
: 遍历所有的矩形是O(n^4)时间。
:
: ~
|
T*****u
发帖数: 7103 | 13 牛逼！第二题只是要求找有没有，并没有求最大最小。可以假定如果没有，那么1是很
少的。那就把所有的元素是1的点都存成序列，然后历遍所有的1的点，运算量应该不大。
【在 z***m 的大作中提到】
: 第一题没有看明白
: 第二题，没一行，转成一个01序列，比如010101, 然后和第二行(010100)做add运算，
: 如果是0，就没有，如果有2个1，就是有这样的矩形。
|
b***e
发帖数: 1419 | 14 什么叫保存上一次的结果？上一次是哪一次？直接暴力的话是O(n^6). 每一个矩形要求
和。这里n是边长，不是面积。你是不是搞混了？
O
【在 a******7 的大作中提到】
: 暴力的话是O(n^4) 可以用一个一唯数组保存上一次的结果 这样可以做到O(n^3)time O
: (n)space
: 但我觉得这道题一定有O(n^2)的DP解法
|
b******g
发帖数: 77 | 15 第一题：
1. 先用2D array 把 第i行 0-j列的和 存下来， 这样算 i行， j-k列的和只需要花O(
1)的时间
2. 对于 每一种 j-k 列， 建立一个windows，windows 包含 A[lo:hi][j:k]
如果A[lo:hi][j:k] 的和 大于 budget， ++lo；
不然的话 ++hi；
第一步会花 O（n*n), 第二步shi O（ n ^ 3 ) |
b******g
发帖数: 77 | 16 第二题：
建立一个 hashset， 储存 每一行 start 和 end 都为 1 的 组合。
for each row：
找到所有值为 1 的 index，生成 start，end 组合，对于每一个 （start，end）
如果（start， end）在 hashset里，return true
不然，就把（start， end） 加入hashset。
初看这种解法的复杂度是 N*N*N, 但是 所有可能的（start，end）的个数是 N*N，这
就是说，最多只用hash （start，end）N*N次
所以解法的复杂度是 N*N |
c******n
发帖数: 4965 | 17 你说AND instead of ADD 吧？
即使这样， 你的and. cost 和 检查 “两个1“的 cost 还是 o（n），
【在 z***m 的大作中提到】
: 第一题没有看明白
: 第二题，没一行，转成一个01序列，比如010101, 然后和第二行(010100)做add运算，
: 如果是0，就没有，如果有2个1，就是有这样的矩形。
|
m*****k
发帖数: 731 | 18 原矩阵M是m*n的话，
用个额外一维数组arr[n],
arr[0]=M[row_x:0]&M[row_y,0] ,
arr[i] = arr[i-1] + M[row_x,i]&M[row_y,i] where i>0,
if arr[i] == 2, return true;
time:O(m^2*n)
space:O(n)
【在 z***m 的大作中提到】
: 不是牛人。
: 是需要每两行之间都要bitAdd一下， O(n^2)
: 当列数太大，超过64， 就用int数组吧。我想4G的bitmap都能实现，这种连续的内存区
: 间应该也不是太难吧。
|
c******n
发帖数: 4965 | 19 上面讨论大概方向没错， 就要从一维max sum sub array 拓展。
两步走， 从 sum 到 limit budget max array length, 简单。 第二步， 从一维变
二维， 这比较难
【在 b***e 的大作中提到】
: 什么叫保存上一次的结果？上一次是哪一次？直接暴力的话是O(n^6). 每一个矩形要求
: 和。这里n是边长，不是面积。你是不是搞混了？
:
: O
|
c******n
发帖数: 4965 | 20 不要朝bitmap 想， 没用。 bit map 仅仅把你的复杂度降一个 constant, 没变。 就
当你所有的字长都是1好了
【在 z***m 的大作中提到】
: 不是牛人。
: 是需要每两行之间都要bitAdd一下， O(n^2)
: 当列数太大，超过64， 就用int数组吧。我想4G的bitmap都能实现，这种连续的内存区
: 间应该也不是太难吧。
|
|
|
c******n
发帖数: 4965 | 21 第一题我找到办法了
先做一维上的。 跟max sum subarray 类似， 把max 变成下面一个operation:
keep cumulative sum and its starting index, add the next number, if new sum
is larger than budget, keep moving the starting index to the right until
fits budget. keep the new sum.
然后用这个technique 把一维转为二维 http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/
用简单memoization 可以从n^6 变到n^4, 用以上technique 可以到 n^3
【在 l*********y 的大作中提到】
: 请教大家两道和矩阵相关的google onsite题目，都是从面经中看到的~~
: 1： n x n parcels in city; matrix M contains the cost of each parcel;
: budget B
: largest rectangular area in the city you can afford.
: 2： 给你一个two dimensional array, array的元素是0或者1。问能不能找到一个矩
: 形，矩形的4个角都是1.
: 大家有没有好的解法，最优的时间复杂度是多少呢？可以一起讨论下，非常感谢！！
|
s********l
发帖数: 998 | 22 第二题
我觉得 不用转换把~ 已经是0 和 1了
然后 && 就可以了把~
如果col = n ; row = m
那么就是 O(m^2 * n)
有没有O(m * n) 解法啊？
就算用转换成bit 也不用^ 应该用&把~
【在 o**********5 的大作中提到】
: 牛人说的 add 应该是 bitwise operation ^
: a = 010101010
: b = 101010101
: 然后，看看 (a^b) 的二进制表达式中有几个位置上的是大于1的。顺便还可以找出位置
: 来。
|
b***e
发帖数: 1419 | 23 http://www.mitbbs.com/article0/JobHunting/32674713_0.html
【在 s********l 的大作中提到】
: 第二题
: 我觉得 不用转换把~ 已经是0 和 1了
: 然后 && 就可以了把~
: 如果col = n ; row = m
: 那么就是 O(m^2 * n)
: 有没有O(m * n) 解法啊？
: 就算用转换成bit 也不用^ 应该用&把~
|
i***e
发帖数: 19 | 24
------------- O(N)
end）
----------------------------------------- O(N*N)
O(N*N*N) overall.
【在 b******g 的大作中提到】
: 第二题：
: 建立一个 hashset， 储存 每一行 start 和 end 都为 1 的 组合。
: for each row：
: 找到所有值为 1 的 index，生成 start，end 组合，对于每一个 （start，end）
: 如果（start， end）在 hashset里，return true
: 不然，就把（start， end） 加入hashset。
: 初看这种解法的复杂度是 N*N*N, 但是 所有可能的（start，end）的个数是 N*N，这
: 就是说，最多只用hash （start，end）N*N次
: 所以解法的复杂度是 N*N
|
w****3
发帖数: 232 | 25 你的这个有问题吧，这是三层循环，看了你的回复，不理解为什么内层循环是O(1)的。
你的定义也有点模糊啊，“map[i][j] records whether line i and line j have two
positions overlapping as 1s” 如果i,j都是表示行(值范围1-n)的话，那为什么在你
的程序
中赋值map的时候（map[currentOnes[k]][j]++），j的值范围是1-m?不会溢出？
当然也有可能是我没理解你的算法。
【在 b***e 的大作中提到】
: http://www.mitbbs.com/article0/JobHunting/32674713_0.html
|
w***w
发帖数: 84 | 26 如果大于NxN 鸽巢原理就一定有四角为1
【在 i***e 的大作中提到】
:
: ------------- O(N)
: end）
: ----------------------------------------- O(N*N)
: O(N*N*N) overall.
|
