b***e
发帖数: 15201 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: philofellow (大智若愚), 信区: JobHunting
标 题: 微软intern面经
发信站: BBS 未名空间站 (Wed Jan 19 19:56:26 2011, 美东)
上周五面的，刚刚收到拒信。
我本来说想面bing或者azure，不过hr临时给安排了office的一个做排版的组。总共面了
四轮。
第一轮：一个俄罗斯人，三道白板coding。
1. atoi
2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
时间复杂度，如何优化。
3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
子数字和最大。只能向右和下移动。时间复杂度，如何优化。
第二轮：lunch interview，俄罗斯人，几道智力题。
1. 什么东西是小的，绿色的，住在地面三英尺以下？
2. 从地面挖一个洞下去，打通地球另一面出来。然后这面扔一个石头下去，问石头会怎
么样。
3. 16个硬币排成4x4的方阵，怎么样拿掉6个，使得剩下的硬币每一行每一列都是偶数。
4. 一个方形的表面，一堆小的方形棋子，a和b轮流把棋子放到表面上。唯一的条件是棋
子不能重叠。如果一方找不到空间放棋子就算输了，问有无必胜策略。
5. 一列士兵横排站开，军官第一秒喊口令"about face"，然后士兵有的会左转有的会右
转，这样转完后一些士兵会面对面，然后下一秒这些面对面的士兵会向后转。再下一秒
仍是如此。问最后会不会结束。证明。如果能结束的话所花时间的上界。
第三轮：白人manager。
设计军舰游戏，两方是NxN的矩阵，上面布局PxQ大小的军舰，两方轮流猜测对方军舰位
置，发射炮弹，一次只能打击一个格。被攻击的一方返回hit,miss,sunk,lost四种信号
。
第四轮：白人principle manager。
基本上就是有向无环图的遍历。
祝大家早日拿到心仪的offer。 |
b***e
发帖数: 15201 | |
l*r
发帖数: 79569 | |
w***s
发帖数: 7132 | 4 挖洞那个？我记得答案是石头会不停地摆动直到停在地心？ |
a****5
发帖数: 10854 | 5 这要忽视地球以外的引力才行
【在 w***s 的大作中提到】
: 挖洞那个？我记得答案是石头会不停地摆动直到停在地心？
|
L**********r
发帖数: 594 | 6 2.2 应该留在地心吧。
2.1 不知道英文有特别问生物么？
【在 b***e 的大作中提到】
: 请关注第2轮前2题.....
|
L**********r
发帖数: 594 | 7 地球上的物理规律不都是已经包含了地球以外的引力作用之下了么？
【在 a****5 的大作中提到】
: 这要忽视地球以外的引力才行
|
a****5
发帖数: 10854 | 8 ofcz not
否则钱塘江怎么涨潮?
【在 L**********r 的大作中提到】
: 地球上的物理规律不都是已经包含了地球以外的引力作用之下了么？
|
c***c
发帖数: 6234 | 9 我觉得是。
方块那个应该是在中心放第一个，以后就和对方以第一个为轴对称放。只要他能放你就
能放
【在 L**********r 的大作中提到】
: 地球上的物理规律不都是已经包含了地球以外的引力作用之下了么？
|
L**********r
发帖数: 594 | 10 涨潮不也落下去了么，月夕力量还是会消失。
我是想说，自然现象里既然没有能反重力始终上飞的，那小石头最后的命运就是归结到
重力的结果，飞
来飞去最后停在地心？
【在 a****5 的大作中提到】
: ofcz not
: 否则钱塘江怎么涨潮?
|
|
|
L**********r
发帖数: 594 | 11 方块儿那个，我觉得胜算应该是“后放”，想想2x2的四个表，这个算是最简化的model。先出手的人肯
定先没地方放啊
【在 c***c 的大作中提到】
: 我觉得是。
: 方块那个应该是在中心放第一个，以后就和对方以第一个为轴对称放。只要他能放你就
: 能放
|
l*r
发帖数: 79569 | 12 你放在中心，他不就没地方放了，呵呵
model。先出手的人肯
【在 L**********r 的大作中提到】
: 方块儿那个，我觉得胜算应该是“后放”，想想2x2的四个表，这个算是最简化的model。先出手的人肯
: 定先没地方放啊
|
L**********r
发帖数: 594 | 13 我觉得放中心这种方法，前提是你的方块不是最小的，我可以在四角放上更小的方块，
所以极限下去，两个人都有“最小”的方块儿时，那最简单基本的博弈场地就是2x2四
格表吧。所以先放先死，呵呵。
不知道俺理解它题意对不
【在 l*r 的大作中提到】
: 你放在中心，他不就没地方放了，呵呵
:
: model。先出手的人肯
|
a****5
发帖数: 10854 | 14 问得不是"石头会怎么样"嘛
这不仅包含最终结果,还包括过程
另,既然有月夕,自然最终石头不会相对地球静止,而会在某小范围游动
【在 L**********r 的大作中提到】
: 涨潮不也落下去了么，月夕力量还是会消失。
: 我是想说，自然现象里既然没有能反重力始终上飞的，那小石头最后的命运就是归结到
: 重力的结果，飞
: 来飞去最后停在地心？
|
a****5
发帖数: 10854 | 15 你理解错了
他说的中心先手是对的
仔细想想,不一定非要按照你脑袋里想想的格子来放
你说的2x2方盘子,先手只需要把1x1小方块在最中心一放,后手直接死了
【在 L**********r 的大作中提到】
: 我觉得放中心这种方法，前提是你的方块不是最小的，我可以在四角放上更小的方块，
: 所以极限下去，两个人都有“最小”的方块儿时，那最简单基本的博弈场地就是2x2四
: 格表吧。所以先放先死，呵呵。
: 不知道俺理解它题意对不
|
L**********r
发帖数: 594 | 16 哦，明白你的意思了，嗯，同意小范围游动
【在 a****5 的大作中提到】
: 问得不是"石头会怎么样"嘛
: 这不仅包含最终结果,还包括过程
: 另,既然有月夕,自然最终石头不会相对地球静止,而会在某小范围游动
|
l**i
发帖数: 8245 | 17 没有中心...
【在 c***c 的大作中提到】
: 我觉得是。
: 方块那个应该是在中心放第一个，以后就和对方以第一个为轴对称放。只要他能放你就
: 能放
|
L**********r
发帖数: 594 | 18 所以我的方法对撒？
【在 l**i 的大作中提到】
: 没有中心...
|
c***c
发帖数: 6234 | 19 如果是2x2的大方块，小方块是1x1的。我放中间，我的小方块各占2x2de1/4，你的小方
块怎么放？
我不是必须放在格子里，任意放。
大方块肯定大于小方块（否则不用下，第一个人就输了），我把第一个小方块的中心和
大方块的中心重合的放。以后就和你放的方块相对中心对称着放。
乐子在逗你，中心就是对角线的交点。
【在 L**********r 的大作中提到】
: 所以我的方法对撒？
|
L**********r
发帖数: 594 | 20 哦，理解，相当于如果平面只有最小的小方块大小，第一个人放那（相当于放中间），
第二个人就输
了。
我假设每个人至少能放一个了。
【在 c***c 的大作中提到】
: 如果是2x2的大方块，小方块是1x1的。我放中间，我的小方块各占2x2de1/4，你的小方
: 块怎么放？
: 我不是必须放在格子里，任意放。
: 大方块肯定大于小方块（否则不用下，第一个人就输了），我把第一个小方块的中心和
: 大方块的中心重合的放。以后就和你放的方块相对中心对称着放。
: 乐子在逗你，中心就是对角线的交点。
|
|
|
b***e
发帖数: 15201 | 21 哈哈 答案很欢乐
第二轮俄罗斯人的智力题：
第一题的答案是一个小的绿色的吃石头的小动物。我没明白什么意思，直到第二题的时
候才明白。第二题我先说石头会在这个通道中做简谐震动，他说不对。我然后说石头会
在地心被融化，他说不对，然后我突然恍然大悟第一题是个引子，于是说石头会被小的
绿色的吃石头的小动物吃掉。。。 |
c***c
发帖数: 6234 | 22 我觉得这个答案很无聊。因为如果会被融化的话，融浆早就喷出来了。而且题目是有个洞，有融浆的话会有洞吗？
我来答下
1、不知道。植物的话不会是绿的（没有阳光是不会有绿色植物的），没有绿色动物在地下3尺生活。
2、4x4的格子，因为完全对称（横竖也是对称），所以只考虑行。16-6=10。10个子排四行，每行还得是偶数，就只有4，4，2，0和4，2，2，2组合。4，4，2，0不可能。因为都两行满了，剩下俩放哪里都会有奇数出现。因为是完全对称，所以拿掉2，4，8，16才能保证每行和列偶数，所以一定有重合。所以最下一行排满，最有一列排满（定点重合了），剩下3个，正好把就一个子的对角线排满。bingo。现在想了下，其实把剩下的那个顶点放上子。剩下俩子再把任意的对角线填满
3、象我说的如同围棋里的模仿棋，天元放一个，剩下就对称着放
4、如果考虑空气阻力，最终停在地心。否则两个洞口永无休止地来回跑。我其实开始就考虑到第三种情况，地心是融浆。但都说有洞了，就是放个钢管之类的保持有洞。融浆解释纯粹知识不够。要是考虑融浆的话，就得知道融浆怎么形成的，压力造成的。不放钢管的话，你的洞马上就被地壳自身压力压扁了，永远挖不成洞的。
5、真没思路。
我比较满意的是2，我一步一步地有思路。最后三个子，是画图才出来的。脑子真不行了。但应该能得部分分吧。我考试就这样，不会就拼命推理，能的一份是一分。
【在 b***e 的大作中提到】
: 哈哈 答案很欢乐
: 第二轮俄罗斯人的智力题：
: 第一题的答案是一个小的绿色的吃石头的小动物。我没明白什么意思，直到第二题的时
: 候才明白。第二题我先说石头会在这个通道中做简谐震动，他说不对。我然后说石头会
: 在地心被融化，他说不对，然后我突然恍然大悟第一题是个引子，于是说石头会被小的
: 绿色的吃石头的小动物吃掉。。。
|
f*****n
发帖数: 12752 | 23 围棋里的模仿棋
说到这个，《棋魂》里的小高手不是把下模仿棋的家伙打败了吗？ |
l****i
发帖数: 20439 | 24 这帮猪头纯粹是吃饱了撑的
【在 b***e 的大作中提到】
: 哈哈 答案很欢乐
: 第二轮俄罗斯人的智力题：
: 第一题的答案是一个小的绿色的吃石头的小动物。我没明白什么意思，直到第二题的时
: 候才明白。第二题我先说石头会在这个通道中做简谐震动，他说不对。我然后说石头会
: 在地心被融化，他说不对，然后我突然恍然大悟第一题是个引子，于是说石头会被小的
: 绿色的吃石头的小动物吃掉。。。
|
c***c
发帖数: 6234 | 25 靠。我看错答案了。这真是吃饱了撑的。家乡话说：臭显呗。跟那个把大象放冰箱里的
笑话一样无聊。
楼主，转身的答案是什么？是不是2N(偶数）人一个隔一个那样左右转是the worst
case? N+1次转身？
【在 l****i 的大作中提到】
: 这帮猪头纯粹是吃饱了撑的
|
b***e
发帖数: 15201 | 26 恩 我转发答案吧 不一定对阿
发信人: philofellow (大智若愚), 信区: JobHunting
标 题: Re: 微软intern面经（一些解答）
发信站: BBS 未名空间站 (Wed Jan 19 22:22:13 2011, 美东)
本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
1. atoi
当时写的程序很不细致，没有判断正负，字符串中字符不为数字，字符串过长越界等情
况。写完后想起来了，然后口头补充了一下，面试官说知道我的意思就直接到下一道题
了。
2. 用递归
bool Equal(Node* a, Node* b){
if(a == NULL && b != NULL) || (a != NULL && b == NULL)
return false;
if(a == NULL && b == NULL) return true;
return (Equal(a->left, b->left) && Equal(a->right, b->right)) || (Equal(a-
>left, b->right) && Equal(a->right == b->left))
}
因为一个函数调用四次自己，树有log(n)层，所以复杂度是4^(log(n)) = n^2。我复杂
度这块比较弱，在他的提示下写出来的。
然后假如左右子树需要交换的情况下，用变量保存总共要交换几次。我用一个引用来保
存，把代码最后一行加几个if语句，在需要交换左右子树的情况下变量自增。但他似乎
不满意，给我写了两个引用，我没懂他什么意思。
3. 给了个递归方案，就是MaxSum(x,y) = Max(MaxSum(x-1,y)+matrix(x,y), MaxSum(x
,y-1)+matrix(x,y))。写了代码。时间复杂度2^2n。然后优化，我说用一个matrix来存
每个位置的最大值，就不用重复算了。他好像表示同意，但又说什么当前行当前列之类
的，我也没听太懂。
第二轮俄罗斯人的智力题：
第一题的答案是一个小的绿色的吃石头的小动物。我没明白什么意思，直到第二题的时
候才明白。第二题我先说石头会在这个通道中做简谐震动，他说不对。我然后说石头会
在地心被融化，他说不对，然后我突然恍然大悟第一题是个引子，于是说石头会被小的
绿色的吃石头的小动物吃掉。。。
第三题4x4枚硬币去掉6枚，剩10枚，分成四个偶数，摆摆就出来了，行列都是2,2,2,4。
第四题先下的下在中间，然后不管对手下哪里，都在对称位置下，这样只要对手有地方
落子，自己就有地方。给出这个答案后我说启发我想到这个答案的是围棋中也有类似的
命题，并且大概给他讲了一下，因为之前和这个俄罗斯人聊了会围棋聊的比较欢。
第五题给出了不太严格的证明，然后他让我换个思路想一下，即两个面对面的士兵各自
向后转等价于两个士兵各向前一步。然后我又大概说了一下。他问我这个问题和哪个排
序像，我说冒泡。然后就结束了午饭。回公司的路上大概聊了会未来技术的发展趋势，
感觉他没什么兴趣。
第三个面试官design的题答得比较差。一开始脑子里没什么思路，胡乱划了一阵然后在
那儿僵了5分钟，也没和面试官沟通。后来给出了一个比较笨的方案。就是战舰类有一
个数组，保存战舰所占格子的坐标。player类有一个数组，保存一系列战舰对象。每次
对方调用shoot函数的时候，更新自己的战舰数组中每个战舰的坐标，如果有战舰的坐
标数组长度为0，意味着被击沉。如果战舰数组为空，意味游戏结束。然后写了一些核
心代码
。
面试官不太满意，然后就到下一个了。
第四个我先写了个BFS，然后他问我有什么问题，我说会有节点被重复遍历。然后他让
我给时间复杂度，磨蹭半天在他的提示下给了个n!。然后优化，我给了个方案，mark遍
历过的点。他基本表示同意。然后又让我给递归算法，写完后让我比较两种迭代和递归
哪种好，胡扯了一阵就到时间了。
总结：
1. 写程序之前一定要先想清楚，要注意细节，我基本上每个coding题都是一开始给的
算法虽然思路差不多但是毫无优化，细节也有很多问题，在面试官一步步追问下才改善
的。应该一开始就尽量把细节的东西写完善，可能会给面试官比较好的印象。
2. 要和面试官随时沟通，我的面试官就经常被我晾在那儿不知道干吗，只好默默的查
信箱。。。尤其是第三轮面试。我虽然记着要和面试官沟通，但是临场觉得有些沟通更
影响思路，就不理面试官自己默默想。其实沟通了即时答案没给出来，很多时候可能也
比把面试官晾着好几分钟，给个一般的答案要强。
面了
换。 |
j******c
发帖数: 712 | 27 2. 从地面挖一个洞下去，打通地球另一面出来。然后这面扔一个石头下去，问石头会怎
么样。
这个题请参见大刘的小说《地球大炮》。要是我遇到这个问题非得问死那个
interviewer不可。 |
G********g
发帖数: 745 | 28 这个题你要是玩过围棋就知道了
【在 c***c 的大作中提到】
: 我觉得是。
: 方块那个应该是在中心放第一个，以后就和对方以第一个为轴对称放。只要他能放你就
: 能放
|
G********g
发帖数: 745 | 29 这个题你要是玩过围棋就知道了
【在 c***c 的大作中提到】
: 我觉得是。
: 方块那个应该是在中心放第一个，以后就和对方以第一个为轴对称放。只要他能放你就
: 能放
|
G********g
发帖数: 745 | 30 这个题你要是玩过围棋就知道了
【在 c***c 的大作中提到】
: 我觉得是。
: 方块那个应该是在中心放第一个，以后就和对方以第一个为轴对称放。只要他能放你就
: 能放
|
|
|
z**n
发帖数: 22303 | 31 并且液态岩浆都凝固了.
【在 a****5 的大作中提到】
: 这要忽视地球以外的引力才行
|
