顶风作案，Google面经 - 未名空间MITBBS历史存档

T*82011-03-24 07:03

1 楼

看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
Google
1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
find all the paths inside the cube to the (n, n,...n)
3. Given a matrix with values of 0 and 1, for any point, if there are three
1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
recall exactly anymore). how to do it. Given a very big such matrix and n
computer, how to do it efficiently. Assume each computer has very limited
memory, how to do it.
4. Network related questions since I was a network guy
5. Design question...

H*M2011-03-24 07:03

2 楼

哥们好样的

..
three
cannot

【在 T*****8 的大作中提到】

: 看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
: Google
: 1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
: 2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
: n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
: find all the paths inside the cube to the (n, n,...n)
: 3. Given a matrix with values of 0 and 1, for any point, if there are three
: 1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
: recall exactly anymore). how to do it. Given a very big such matrix and n
: computer, how to do it efficiently. Assume each computer has very limited

f*w2011-03-24 07:03

3 楼

..
cube,
three
(cannot
n
limited
3 有什么好方法吗？

【在 T*****8 的大作中提到】

: 看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
: Google
: 1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
: 2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
: n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
: find all the paths inside the cube to the (n, n,...n)
: 3. Given a matrix with values of 0 and 1, for any point, if there are three
: 1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
: recall exactly anymore). how to do it. Given a very big such matrix and n
: computer, how to do it efficiently. Assume each computer has very limited

f*42011-03-24 07:03

4 楼

顶一个～

T*W2011-03-24 07:03

5 楼

顶，就一个字。

m*q2011-03-24 07:03

6 楼

把数组按行分给各个机器，比如一共有8000行，8个机器，
则每个机器处理1000行。每个机器处理的时候只要把
前三行的前三列装到内存就行，每次处理一列后把前一列
删除，后面一列加入，直到所有列处理完毕。然后删除
前一行，加入新一行，继续处理
注意分数组的时候需要，两个机器直接有两行是共用的。

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

:
: ..
: cube,
: three
: (cannot
: n
: limited
: 3 有什么好方法吗？

r*g2011-03-24 07:03

7 楼

Hi
第一题题目详细是什么，能说说吗

..
three
cannot

【在 T*****8 的大作中提到】

: 看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
: Google
: 1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
: 2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
: n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
: find all the paths inside the cube to the (n, n,...n)
: 3. Given a matrix with values of 0 and 1, for any point, if there are three
: 1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
: recall exactly anymore). how to do it. Given a very big such matrix and n
: computer, how to do it efficiently. Assume each computer has very limited

n*s2011-03-24 07:03

8 楼

这道题：
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram
答案：
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.htm

【在 r*******g 的大作中提到】

: Hi
: 第一题题目详细是什么，能说说吗
:
: ..
: three
: cannot

w*r2011-03-24 07:03

9 楼

多谢，how's the result?

..
three
cannot

【在 T*****8 的大作中提到】

: 看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
: Google
: 1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
: 2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
: n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
: find all the paths inside the cube to the (n, n,...n)
: 3. Given a matrix with values of 0 and 1, for any point, if there are three
: 1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
: recall exactly anymore). how to do it. Given a very big such matrix and n
: computer, how to do it efficiently. Assume each computer has very limited

h*n2011-03-24 07:03

10 楼

MARK

T*82011-03-24 07:03

11 楼

看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
Google
1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
find all the paths inside the cube to the (n, n,...n)
3. Given a matrix with values of 0 and 1, for any point, if there are three
1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
recall exactly anymore). how to do it. Given a very big such matrix and n
computer, how to do it efficiently. Assume each computer has very limited
memory, how to do it.
4. Network related questions since I was a network guy
5. Design question...

H*M2011-03-24 07:03

12 楼

哥们好样的

..
three
cannot

【在 T*****8 的大作中提到】

: 看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
: Google
: 1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
: 2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
: n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
: find all the paths inside the cube to the (n, n,...n)
: 3. Given a matrix with values of 0 and 1, for any point, if there are three
: 1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
: recall exactly anymore). how to do it. Given a very big such matrix and n
: computer, how to do it efficiently. Assume each computer has very limited

f*w2011-03-24 07:03

13 楼

..
cube,
three
(cannot
n
limited
3 有什么好方法吗？

【在 T*****8 的大作中提到】

: 看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
: Google
: 1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
: 2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
: n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
: find all the paths inside the cube to the (n, n,...n)
: 3. Given a matrix with values of 0 and 1, for any point, if there are three
: 1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
: recall exactly anymore). how to do it. Given a very big such matrix and n
: computer, how to do it efficiently. Assume each computer has very limited

f*42011-03-24 07:03

14 楼

顶一个～

T*W2011-03-24 07:03

15 楼

顶，就一个字。

m*q2011-03-24 07:03

16 楼

把数组按行分给各个机器，比如一共有8000行，8个机器，
则每个机器处理1000行。每个机器处理的时候只要把
前三行的前三列装到内存就行，每次处理一列后把前一列
删除，后面一列加入，直到所有列处理完毕。然后删除
前一行，加入新一行，继续处理
注意分数组的时候需要，两个机器直接有两行是共用的。

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

:
: ..
: cube,
: three
: (cannot
: n
: limited
: 3 有什么好方法吗？

r*g2011-03-24 07:03

17 楼

Hi
第一题题目详细是什么，能说说吗

..
three
cannot

【在 T*****8 的大作中提到】

: 看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
: Google
: 1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
: 2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
: n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
: find all the paths inside the cube to the (n, n,...n)
: 3. Given a matrix with values of 0 and 1, for any point, if there are three
: 1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
: recall exactly anymore). how to do it. Given a very big such matrix and n
: computer, how to do it efficiently. Assume each computer has very limited

n*s2011-03-24 07:03

18 楼

这道题：
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram
答案：
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.htm

【在 r*******g 的大作中提到】

: Hi
: 第一题题目详细是什么，能说说吗
:
: ..
: three
: cannot

w*r2011-03-24 07:03

19 楼

多谢，how's the result?

..
three
cannot

【在 T*****8 的大作中提到】

: 看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
: Google
: 1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
: 2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
: n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
: find all the paths inside the cube to the (n, n,...n)
: 3. Given a matrix with values of 0 and 1, for any point, if there are three
: 1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
: recall exactly anymore). how to do it. Given a very big such matrix and n
: computer, how to do it efficiently. Assume each computer has very limited

h*n2011-03-24 07:03

20 楼

MARK

Y*B2011-03-24 07:03

21 楼

第三题啥想法阿？
怎么觉得根据题目的要求，这个变幻过程会一直进行下去，因为当考察第二个点的时候又把第
一个已经做好的点周围的值给变了？
谁能说说？

e*92011-03-24 07:03

22 楼

大家应该关注一下第三题,最近又被问到过.

s*n2011-03-24 07:03

23 楼

能把第三题说的更清除一些么？
是按顺序做，先做第一行，再做第二行， .... ,对么？
前面的结果影响后面的，怎么实现多个机器并行呢？

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

: 大家应该关注一下第三题,最近又被问到过.

a*82011-03-24 07:03

24 楼

google 这么变态，面试网络工程师考算法？

d*i2011-03-24 07:03

25 楼

有关第二题，
当n=2
step = 1
n >2
step = 从n个空间中任选一个空间，然后就是step(n-1)
所以是n*step(n-1)
用递归，
这样可以么。。。

Y*B2011-03-24 07:03

26 楼

第三题啥想法阿？
怎么觉得根据题目的要求，这个变幻过程会一直进行下去，因为当考察第二个点的时候又把第
一个已经做好的点周围的值给变了？
谁能说说？

e*92011-03-24 07:03

27 楼

大家应该关注一下第三题,最近又被问到过.

s*n2011-03-24 07:03

28 楼

能把第三题说的更清除一些么？
是按顺序做，先做第一行，再做第二行， .... ,对么？
前面的结果影响后面的，怎么实现多个机器并行呢？

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

: 大家应该关注一下第三题,最近又被问到过.

a*82011-03-24 07:03

29 楼

google 这么变态，面试网络工程师考算法？

d*i2011-03-24 07:03

30 楼

有关第二题，
当n=2
step = 1
n >2
step = 从n个空间中任选一个空间，然后就是step(n-1)
所以是n*step(n-1)
用递归，
这样可以么。。。

s*n2011-03-24 07:03

31 楼

第三题，最后所有的1会扩展成矩形样子吧，丁字形的1会被补上缺口变成矩形。从这个角度分析，是不是有比较好的办法？算法如下：
搜索纵或横相连的1，将其扩展为矩形（相连1的minx, miny, maxx, maxy)。然后如果两个矩形距离只间隔一列/行，则很可能合并两个矩形。重复上述步骤直到没法再扩展。