EAD/AP combo 卡上个月收到，昨天又收到AP的纸质批准 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

EAD/AP combo 卡上个月收到，昨天又收到AP的纸质批准

EAD/AP combo 卡上个月收到，昨天又收到AP的纸质批准# Immigration - 落地生根

l*y2013-06-25 07:06

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.
大家有没有好的解法，最优的时间复杂度是多少呢？可以一起讨论下，非常感谢！！

f*32013-06-25 07:06

2 楼

EAD/AP combo 卡上个月收到，昨天又收到AP的纸质批准，这是什么情况？大家有碰到
类似情况吗？
快回国了，到底要用哪个入关？combo卡？还是AP纸质批准通知书？

z*m2013-06-25 07:06

3 楼

第一题没有看明白
第二题，没一行，转成一个01序列，比如010101, 然后和第二行(010100)做add运算，
如果是0，就没有，如果有2个1，就是有这样的矩形。

z*b2013-06-25 07:06

4 楼

按道理应该combo就可以了
不放心就全带上吧

【在 f******3 的大作中提到】

: EAD/AP combo 卡上个月收到，昨天又收到AP的纸质批准，这是什么情况？大家有碰到
: 类似情况吗？
: 快回国了，到底要用哪个入关？combo卡？还是AP纸质批准通知书？

c*n2013-06-25 07:06

5 楼

第一题应该就是find largest sum sub matrix 的变型吧。
遍历所有的矩形，如果其sum <= B 就试着更新最大面积

p*e2013-06-25 07:06

6 楼

niu

【在 z***m 的大作中提到】

: 第一题没有看明白
: 第二题，没一行，转成一个01序列，比如010101, 然后和第二行(010100)做add运算，
: 如果是0，就没有，如果有2个1，就是有这样的矩形。

d*c2013-06-25 07:06

7 楼

这个序列是binary的吗？还是直接加呢？我觉得不一定是跟下一行加吧，要loop下面所
有的？
请大牛指点

【在 z***m 的大作中提到】

o*52013-06-25 07:06

8 楼

牛人说的 add 应该是 bitwise operation ^
a = 010101010
b = 101010101
然后，看看 (a^b) 的二进制表达式中有几个位置上的是大于1的。顺便还可以找出位置
来。

【在 d*****c 的大作中提到】

: 这个序列是binary的吗？还是直接加呢？我觉得不一定是跟下一行加吧，要loop下面所
: 有的？
: 请大牛指点

n*z2013-06-25 07:06

9 楼

这样是要n^2吧，一行和下面每行相比，
但矩阵size超出32bit或者64bit呢，
general的方法即使用hashset还是n^3吧，

【在 o**********5 的大作中提到】

: 牛人说的 add 应该是 bitwise operation ^
: a = 010101010
: b = 101010101
: 然后，看看 (a^b) 的二进制表达式中有几个位置上的是大于1的。顺便还可以找出位置
: 来。

a*72013-06-25 07:06

10 楼

遍历所有的矩形就是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*62013-06-25 07:06

11 楼

没太看懂能举个例子不？多谢！

【在 z***m 的大作中提到】

z*m2013-06-25 07:06

12 楼

不是牛人。
是需要每两行之间都要bitAdd一下， O(n^2)
当列数太大，超过64，就用int数组吧。我想4G的bitmap都能实现，这种连续的内存区
间应该也不是太难吧。

【在 d*****c 的大作中提到】

: 这个序列是binary的吗？还是直接加呢？我觉得不一定是跟下一行加吧，要loop下面所
: 有的？
: 请大牛指点

b*e2013-06-25 07:06

13 楼

遍历所有的矩形是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*72013-06-25 07:06

14 楼

暴力的话是O(n^4) 可以用一个一唯数组保存上一次的结果这样可以做到O(n^3)time O
(n)space
但我觉得这道题一定有O(n^2)的DP解法

【在 b***e 的大作中提到】

: 遍历所有的矩形是O(n^4)时间。
:
: ~

T*u2013-06-25 07:06

15 楼

牛逼！第二题只是要求找有没有，并没有求最大最小。可以假定如果没有，那么1是很
少的。那就把所有的元素是1的点都存成序列，然后历遍所有的1的点，运算量应该不大。

【在 z***m 的大作中提到】

b*e2013-06-25 07:06

16 楼

什么叫保存上一次的结果？上一次是哪一次？直接暴力的话是O(n^6). 每一个矩形要求
和。这里n是边长，不是面积。你是不是搞混了？

O

【在 a******7 的大作中提到】

: 暴力的话是O(n^4) 可以用一个一唯数组保存上一次的结果这样可以做到O(n^3)time O
: (n)space
: 但我觉得这道题一定有O(n^2)的DP解法

b*g2013-06-25 07:06

17 楼

第一题：
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*g2013-06-25 07:06

18 楼

第二题：
建立一个 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*n2013-06-25 07:06

19 楼

你说AND instead of ADD 吧？
即使这样，你的and. cost 和检查 “两个1“的 cost 还是 o（n），

【在 z***m 的大作中提到】

m*k2013-06-25 07:06

20 楼

原矩阵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*n2013-06-25 07:06

21 楼

上面讨论大概方向没错，就要从一维max sum sub array 拓展。
两步走，从 sum 到 limit budget max array length, 简单。第二步，从一维变
二维，这比较难

【在 b***e 的大作中提到】

: 什么叫保存上一次的结果？上一次是哪一次？直接暴力的话是O(n^6). 每一个矩形要求
: 和。这里n是边长，不是面积。你是不是搞混了？
:
: O

c*n2013-06-25 07:06

22 楼

不要朝bitmap 想，没用。 bit map 仅仅把你的复杂度降一个 constant, 没变。就
当你所有的字长都是1好了

【在 z***m 的大作中提到】

c*n2013-06-25 07:06

23 楼

第一题我找到办法了
先做一维上的。跟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*l2013-06-25 07:06

24 楼

第二题
我觉得不用转换把~ 已经是0 和 1了
然后 && 就可以了把~
如果col = n ; row = m
那么就是 O(m^2 * n)
有没有O(m * n) 解法啊？
就算用转换成bit 也不用^ 应该用&把~

【在 o**********5 的大作中提到】

b*e2013-06-25 07:06

25 楼

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*e2013-06-25 07:06

26 楼

------------- 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*32013-06-25 07:06

27 楼

你的这个有问题吧，这是三层循环，看了你的回复，不理解为什么内层循环是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*w2013-06-25 07:06

28 楼

如果大于NxN 鸽巢原理就一定有四角为1

【在 i***e 的大作中提到】

:
: ------------- O(N)
: end）
: ----------------------------------------- O(N*N)
: O(N*N*N) overall.