面经（谷家） - 未名空间MITBBS历史存档

t*32012-07-18 07:07

1 楼

我也来尝试一下全中文描述
第一个
题目比较通俗，给你一个二岔树的顺序遍历结果，还有前续遍历结果，把树还原出来
第二个
告诉我一个游戏，叫做“生／或者／死”，在一个棋盘上，规则如下：
每格有两种状态：生，或者死
每一轮，如果有少于两个邻居是活着的，这格就死掉
如果刚好有两个邻居活着，这格保持原有状态
如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了
如果有三个以上邻居，这格就被挤死了
要在白板上写每轮如何更新整个棋盘的状态
第三个
给一个矩阵，顺时针翻转九十度
第四个吃饭
第五个
问了给了一些数轴上的范围，要求把重合的部分合并掉
最后一个
原来打算问生或者死的那题，结果发现被人抢了，很无语，于是改问零散的数学问题
估计一下谷歌地球总共要多大的硬盘来存全球的地貌照片。
一个很大的文件（一个比连），有很多行，每行长短不一，如何随机抽取一百行。假设
你有一个六十四位的比特的随机数生成器。
各位内部人士走过路过就装做没看到吧

q*y2012-07-18 07:07

2 楼

生或者死的那题不太懂
判断生死时有优先级么？

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

: 我也来尝试一下全中文描述
: 第一个
: 题目比较通俗，给你一个二岔树的顺序遍历结果，还有前续遍历结果，把树还原出来
: 第二个
: 告诉我一个游戏，叫做“生／或者／死”，在一个棋盘上，规则如下：
: 每格有两种状态：生，或者死
: 每一轮，如果有少于两个邻居是活着的，这格就死掉
: 如果刚好有两个邻居活着，这格保持原有状态
: 如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了
: 如果有三个以上邻居，这格就被挤死了

t*32012-07-18 07:07

3 楼

所有格子同步更新，比如
活活死。。。
活死死。。。
死活死
第二行第一个死在这一轮会重生
第三行的死这一轮不会重生，因为是所有事情是同时发生的

【在 q***y 的大作中提到】

: 生或者死的那题不太懂
: 判断生死时有优先级么？

i*e2012-07-18 07:07

4 楼

第二题是 game of life，后续应该还有一问：
如果扩展到第ｋ步的时候，万一棋盘装不下怎么办？

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

: 我也来尝试一下全中文描述
: 第一个
: 题目比较通俗，给你一个二岔树的顺序遍历结果，还有前续遍历结果，把树还原出来
: 第二个
: 告诉我一个游戏，叫做“生／或者／死”，在一个棋盘上，规则如下：
: 每格有两种状态：生，或者死
: 每一轮，如果有少于两个邻居是活着的，这格就死掉
: 如果刚好有两个邻居活着，这格保持原有状态
: 如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了
: 如果有三个以上邻居，这格就被挤死了

H*r2012-07-18 07:07

5 楼

最后一题有人能说说思路么？晕了

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

: 我也来尝试一下全中文描述
: 第一个
: 题目比较通俗，给你一个二岔树的顺序遍历结果，还有前续遍历结果，把树还原出来
: 第二个
: 告诉我一个游戏，叫做“生／或者／死”，在一个棋盘上，规则如下：
: 每格有两种状态：生，或者死
: 每一轮，如果有少于两个邻居是活着的，这格就死掉
: 如果刚好有两个邻居活着，这格保持原有状态
: 如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了
: 如果有三个以上邻居，这格就被挤死了

q*y2012-07-18 07:07

6 楼

Knuth shuffle，执行前一百次

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

: 最后一题有人能说说思路么？晕了

w*x2012-07-18 07:07

7 楼

冰天雪地裸体跪谢楼主发题，楼主简直就是我的再生父母啊~~

H*r2012-07-18 07:07

8 楼

谷歌地球总共要多大的硬盘来存全球的地貌照片？
Knuth shuffle 得知道总行数和每行的位置吧？还得记住哪些行已经选过了？

【在 q***y 的大作中提到】

: Knuth shuffle，执行前一百次

Z*Z2012-07-18 07:07

9 楼

那题是reservoir sampling吧
另外bless lz

【在 q***y 的大作中提到】

: Knuth shuffle，执行前一百次

r*e2012-07-18 07:07

10 楼

bless!

c*p2012-07-18 07:07

11 楼

http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

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

: 第二题是 game of life，后续应该还有一问：
: 如果扩展到第ｋ步的时候，万一棋盘装不下怎么办？

w*x2012-07-18 07:07

12 楼

生或死那题能用一个二维数组吗，不知道有什么tricky的地方？

l*a2012-07-18 07:07

13 楼

我不能装作没看见

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

: 我也来尝试一下全中文描述
: 第一个
: 题目比较通俗，给你一个二岔树的顺序遍历结果，还有前续遍历结果，把树还原出来
: 第二个
: 告诉我一个游戏，叫做“生／或者／死”，在一个棋盘上，规则如下：
: 每格有两种状态：生，或者死
: 每一轮，如果有少于两个邻居是活着的，这格就死掉
: 如果刚好有两个邻居活着，这格保持原有状态
: 如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了
: 如果有三个以上邻居，这格就被挤死了

w*x2012-07-18 07:07

14 楼

鄙视~~

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

: 我不能装作没看见

l*a2012-07-18 07:07

15 楼

why ne?

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

:
: 鄙视~~

z*a2012-07-18 07:07

16 楼

地表照片分辨率我猜大概在20cm的样子. 地球表面积大约5.1E14平方米. 假设每个像素
占四个byte, 那大约要50PB的空间.

h*e2012-07-18 07:07

17 楼

这么些数学题？什么职位

H*r2012-07-18 07:07

18 楼

地球照片不是三维的么？

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 地表照片分辨率我猜大概在20cm的样子. 地球表面积大约5.1E14平方米. 假设每个像素
: 占四个byte, 那大约要50PB的空间.

a*i2012-07-18 07:07

19 楼

哎哟，我本来很认真的看题，看到这里喷了。。。
那只是“看起来像”三维，其实都是一张张的图，googlemap可以看做是个特殊的web
browser来hold那一张张的图。。。

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

: 地球照片不是三维的么？
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

H*r2012-07-18 07:07

20 楼

其实你可以说谷歌地球现在是用的伪3d，不过看看以下网站的描述：
http://www.google.com/earth/explore/products/
http://en.wikipedia.org/wiki/Google_Earth
“Google Earth is simply based on 3D maps, it has the capability to show 3D
buildings and structures (such as bridges), which consist of users'
submissions using SketchUp, a 3D modeling program software.”

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

: 哎哟，我本来很认真的看题，看到这里喷了。。。
: 那只是“看起来像”三维，其实都是一张张的图，googlemap可以看做是个特殊的web
: browser来hold那一张张的图。。。

w*x2012-07-18 07:07

21 楼

讨论一下生或者死那题吧, 有啥tricky的??

H*r2012-07-18 07:07

22 楼

wiki 上提到了几个tricky的地方，比如边界处理，数据结构（2个2d数组不是最好的结
构），更新时如何加速（有些area从来不动的),如何发现，识别pattern, 如果pattern
是逐渐扩大的怎么办，等等...

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

: 讨论一下生或者死那题吧, 有啥tricky的??

a*o2012-07-18 07:07

23 楼

我觉得可以就地更新，就是标俩特殊符号
比如0->1时候可以先标2,
1->0时候先标个3，最后一遍把2改成1
3改成0,当然如果实在要省空间的话。。。

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

: 所有格子同步更新，比如
: 活活死。。。
: 活死死。。。
: 死活死
: 第二行第一个死在这一轮会重生
: 第三行的死这一轮不会重生，因为是所有事情是同时发生的

t*32012-07-18 07:07

24 楼

我也来尝试一下全中文描述
第一个
题目比较通俗，给你一个二岔树的顺序遍历结果，还有前续遍历结果，把树还原出来
第二个
告诉我一个游戏，叫做“生／或者／死”，在一个棋盘上，规则如下：
每格有两种状态：生，或者死
每一轮，如果有少于两个邻居是活着的，这格就死掉
如果刚好有两个邻居活着，这格保持原有状态
如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了
如果有三个以上邻居，这格就被挤死了
要在白板上写每轮如何更新整个棋盘的状态
第三个
给一个矩阵，顺时针翻转九十度
第四个吃饭
第五个
问了给了一些数轴上的范围，要求把重合的部分合并掉
最后一个
原来打算问生或者死的那题，结果发现被人抢了，很无语，于是改问零散的数学问题
估计一下谷歌地球总共要多大的硬盘来存全球的地貌照片。
一个很大的文件（一个比连），有很多行，每行长短不一，如何随机抽取一百行。假设
你有一个六十四位的比特的随机数生成器。
各位内部人士走过路过就装做没看到吧

b*z2012-07-18 07:07

25 楼

支持感谢！

d*e2012-07-18 07:07

26 楼

棋盘邻居的定义是上下左右四个邻居么？
请教啥思路

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

: 我也来尝试一下全中文描述
: 第一个
: 题目比较通俗，给你一个二岔树的顺序遍历结果，还有前续遍历结果，把树还原出来
: 第二个
: 告诉我一个游戏，叫做“生／或者／死”，在一个棋盘上，规则如下：
: 每格有两种状态：生，或者死
: 每一轮，如果有少于两个邻居是活着的，这格就死掉
: 如果刚好有两个邻居活着，这格保持原有状态
: 如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了
: 如果有三个以上邻居，这格就被挤死了

A*a2012-07-18 07:07

27 楼

感谢！祝大offer

d*n2012-07-18 07:07

28 楼

求第二题的思路，反复的扫描棋盘，直到没有状态改变吗？

m*g2012-07-18 07:07

29 楼

Create a separate matrix and record new state of each cell, then start from
there for next round ??

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

: 求第二题的思路，反复的扫描棋盘，直到没有状态改变吗？

i*t2012-07-18 07:07

30 楼

每个cell的变化在后续cell变化时考虑吗?

u*12012-07-18 07:07

31 楼

Conway's Game of Life.

c*p2012-07-18 07:07

32 楼

mark

x*12012-07-18 07:07

33 楼

请问最后一题有什么号放大？

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

: 我也来尝试一下全中文描述
: 第一个
: 题目比较通俗，给你一个二岔树的顺序遍历结果，还有前续遍历结果，把树还原出来
: 第二个
: 告诉我一个游戏，叫做“生／或者／死”，在一个棋盘上，规则如下：
: 每格有两种状态：生，或者死
: 每一轮，如果有少于两个邻居是活着的，这格就死掉
: 如果刚好有两个邻居活着，这格保持原有状态
: 如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了
: 如果有三个以上邻居，这格就被挤死了