微软intern面经 - 未名空间MITBBS历史存档

p*w2011-01-19 08:01

1 楼

上周五面的，刚刚收到拒信。
我本来说想面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。

i*92011-01-19 08:01

2 楼

intern 面试怎么这么变态啊

M72011-01-19 08:01

3 楼

面了
换。
不很理解这道题，通过交换subtree来使两个不等的binary tree相等?
dynamic programming from upper left to lower right?
no idea... 你怎么回答的？
会怎
反复震荡？这不是物理题吗？
数。
是棋
会右
如果是N个士兵。最多N/2秒就稳定下来了？
这是OO design的题目？
。

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

: 上周五面的，刚刚收到拒信。
: 我本来说想面bing或者azure，不过hr临时给安排了office的一个做排版的组。总共面了
: 四轮。
: 第一轮：一个俄罗斯人，三道白板coding。
: 1. atoi
: 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
: 时间复杂度，如何优化。
: 3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
: 子数字和最大。只能向右和下移动。时间复杂度，如何优化。
: 第二轮：lunch interview，俄罗斯人，几道智力题。

s*82011-01-19 08:01

4 楼

intern居然这么难。

g*s2011-01-19 08:01

5 楼

2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
时间复杂度，如何优化。
recursion?
is_equal(root1, root1) ::= root1->dat == root2->dat &&
(is_equal(root1->left, root2.left) && is_equal(root1->right, root1-
>right || ... //swap case).
each node can at most trigger 2 swap ops. so worst case 2n? not sure if
a swap on one parent and a swap on its kid would cancel each other.
complexity exponential?
optimization: traverse the tree to calculate the size of each sub-tree.
check the sub-tree size before recursive call.
3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
子数字和最大。只能向右和下移动。时间复杂度，如何优化。
recursion: f(n, m) = max{ f(n-1, m), f(n, m-1) } + x[n][m].
so it seems dp would work.
第二轮：lunch interview，俄罗斯人，几道智力题。
1. 什么东西是小的，绿色的，住在地面三英尺以下？
no idea.
2. 从地面挖一个洞下去，打通地球另一面出来。然后这面扔一个石头下去，问石头会怎
么样。
no idea.
3. 16个硬币排成4x4的方阵，怎么样拿掉6个，使得剩下的硬币每一行每一列都是偶数。
description unclear.
4. 一个方形的表面，一堆小的方形棋子，a和b轮流把棋子放到表面上。唯一的条件是棋
子不能重叠。如果一方找不到空间放棋子就算输了，问有无必胜策略。
the 1st player always takes the exact center, then no matter how the 2nd
play, the 1st always have space and must win.
5. 一列士兵横排站开，军官第一秒喊口令"about face"，然后士兵有的会左转有的会右
转，这样转完后一些士兵会面对面，然后下一秒这些面对面的士兵会向后转。再下一秒
仍是如此。问最后会不会结束。证明。如果能结束的话所花时间的上界。
yes, it will always terminate. mathematical induction. always remove the
two soldiers at the ends. O(N).
第三轮：白人manager。
设计军舰游戏，两方是NxN的矩阵，上面布局PxQ大小的军舰，两方轮流猜测对方军舰位
置，发射炮弹，一次只能打击一个格。被攻击的一方返回hit,miss,sunk,lost四种信号
。
第四轮：白人principle manager。
基本上就是有向无环图的遍历。

面了
换。

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

: 上周五面的，刚刚收到拒信。
: 我本来说想面bing或者azure，不过hr临时给安排了office的一个做排版的组。总共面了
: 四轮。
: 第一轮：一个俄罗斯人，三道白板coding。
: 1. atoi
: 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
: 时间复杂度，如何优化。
: 3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
: 子数字和最大。只能向右和下移动。时间复杂度，如何优化。
: 第二轮：lunch interview，俄罗斯人，几道智力题。

p*w2011-01-19 08:01

6 楼

本来想一起把我的答案发了的，结果被老婆拽去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. 要和面试官随时沟通，我的面试官就经常被我晾在那儿不知道干吗，只好默默的查信
箱。。。尤其是第三轮面试。我虽然记着要和面试官沟通，但是临场觉得有些沟通更影
响思路，就不理面试官自己默默想。其实沟通了即时答案没给出来，很多时候可能也比
把面试官晾着好几分钟，给个一般的答案要强。

面了
换。

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

: 上周五面的，刚刚收到拒信。
: 我本来说想面bing或者azure，不过hr临时给安排了office的一个做排版的组。总共面了
: 四轮。
: 第一轮：一个俄罗斯人，三道白板coding。
: 1. atoi
: 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
: 时间复杂度，如何优化。
: 3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
: 子数字和最大。只能向右和下移动。时间复杂度，如何优化。
: 第二轮：lunch interview，俄罗斯人，几道智力题。

g*s2011-01-19 08:01

7 楼

本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
2. 用递归
因为一个函数调用四次自己，树有log(n)层，所以复杂度是4^(log(n)) = n^2。我复杂
度这块比较弱，在他的提示下写出来的。
how u know tree has lgN level? the worse case could be N.
然后假如左右子树需要交换的情况下，用变量保存总共要交换几次。我用一个引用来保
存，把代码最后一行加几个if语句，在需要交换左右子树的情况下变量自增。但他似乎
不满意，给我写了两个引用，我没懂他什么意思。
why u need a variable to keep the swap? confused here.
it seems this problem has an easy version and a complicated version.
easy version not considering left/right sub-tree swapping. in this case,
you can traverse each tree twice (in-order and pre-order) and then
compares the traversal results. it takes only O(N).
3. 给了个递归方案，就是MaxSum(x,y) = Max(MaxSum(x-1,y)+matrix(x,y), MaxSum(x
,y-1)+matrix(x,y))。写了代码。时间复杂度2^2n。然后优化，我说用一个matrix来存
每个位置的最大值，就不用重复算了。他好像表示同意，但又说什么当前行当前列之类
的，我也没听太懂。
i think he's talking about the dp solution using O(M+N) time and
O(min(M, N) space.
第二轮俄罗斯人的智力题：
第五题给出了不太严格的证明，然后他让我换个思路想一下，即两个面对面的士兵各自
向后转等价于两个士兵各向前一步。然后我又大概说了一下。他问我这个问题和哪个排
序像，我说冒泡。然后就结束了午饭。回公司的路上大概聊了会未来技术的发展趋势，
感觉他没什么兴趣。
confused. how could face-to-face equal to move forward and how to relate
this one to bubble sort?
第四个我先写了个BFS，然后他问我有什么问题，我说会有节点被重复遍历。然后他让我
给时间复杂度，磨蹭半天在他的提示下给了个n!。然后优化，我给了个方案，mark遍历
过的点。他基本表示同意。然后又让我给递归算法，写完后让我比较两种迭代和递归哪
种好，胡扯了一阵就到时间了。
how could bfs on directed acyclic graph has n! complexity? u can just do
topological sort and achieve O(N).

换。
if
tree.

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

: 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
: 时间复杂度，如何优化。
: recursion?
: is_equal(root1, root1) ::= root1->dat == root2->dat &&
: (is_equal(root1->left, root2.left) && is_equal(root1->right, root1-
: >right || ... //swap case).
: each node can at most trigger 2 swap ops. so worst case 2n? not sure if
: a swap on one parent and a swap on its kid would cancel each other.
: complexity exponential?
: optimization: traverse the tree to calculate the size of each sub-tree.

p*w2011-01-19 08:01

8 楼

是，这块我考虑的不细。。。看来细节真的很重要
两棵树全等是指形状全等(isomorphism)。
(x
应该是。
两个士兵面对面，然后各自向后转，变成背对背，不就等价于两个面对面的士兵交换
位置么？我觉得像bubble sort，两个元素比较，然后可能交换位置
让我
因为无环，根节点可能有n-1个子节点，每个子节点可能有n-2个子节点。。。如果对
遍历过的节点mark的话可以O(n)，topological sort不懂。

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

: 本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
: 2. 用递归
: 因为一个函数调用四次自己，树有log(n)层，所以复杂度是4^(log(n)) = n^2。我复杂
: 度这块比较弱，在他的提示下写出来的。
: how u know tree has lgN level? the worse case could be N.
: 然后假如左右子树需要交换的情况下，用变量保存总共要交换几次。我用一个引用来保
: 存，把代码最后一行加几个if语句，在需要交换左右子树的情况下变量自增。但他似乎
: 不满意，给我写了两个引用，我没懂他什么意思。
: why u need a variable to keep the swap? confused here.
: it seems this problem has an easy version and a complicated version.

c*z2011-01-19 08:01

9 楼

石头的那个，明显间歇振动是正解，鄙视老毛子

M72011-01-19 08:01

10 楼

感觉更像是午餐时的一个玩笑。

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

: 石头的那个，明显间歇振动是正解，鄙视老毛子

l*t2011-01-19 08:01

11 楼

简单的说LZ基本没啥hands-on。atoi都能写成那样？

h*e2011-01-19 08:01

12 楼

啥topological sort都不懂。。。？！！。

d*j2011-01-19 08:01

13 楼

ha，第五题士兵转向问题我明白了
lz说的对，士兵面对面时向后转等效于二者交换各自在原来方向上向前走一步。。。
这是什么？想起来了么?
MS编程之美中的蚂蚁走路问题！
是有终结状态的，所耗费的时间就是第一次左转或者右转时面向最远端且与面前人面
对面的那个人，worst case也是O(N)
看来像我这样不聪明的人，是得熟读兵书才能弥补不足！

z*s2011-01-19 08:01

14 楼

感谢楼主分享。

O(min(M, N) space.
请教这个O(M+N) time，O(min(M,N)) space的算法。

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

: 本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
: 2. 用递归
: 因为一个函数调用四次自己，树有log(n)层，所以复杂度是4^(log(n)) = n^2。我复杂
: 度这块比较弱，在他的提示下写出来的。
: how u know tree has lgN level? the worse case could be N.
: 然后假如左右子树需要交换的情况下，用变量保存总共要交换几次。我用一个引用来保
: 存，把代码最后一行加几个if语句，在需要交换左右子树的情况下变量自增。但他似乎
: 不满意，给我写了两个引用，我没懂他什么意思。
: why u need a variable to keep the swap? confused here.
: it seems this problem has an easy version and a complicated version.

A*l2011-01-19 08:01

15 楼

同感。。。

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

: intern 面试怎么这么变态啊

l*42011-01-19 08:01

16 楼

标记一下

f*r2011-01-19 08:01

17 楼

thanks for sharing

面了
换。

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

: 上周五面的，刚刚收到拒信。
: 我本来说想面bing或者azure，不过hr临时给安排了office的一个做排版的组。总共面了
: 四轮。
: 第一轮：一个俄罗斯人，三道白板coding。
: 1. atoi
: 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
: 时间复杂度，如何优化。
: 3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
: 子数字和最大。只能向右和下移动。时间复杂度，如何优化。
: 第二轮：lunch interview，俄罗斯人，几道智力题。

c*b2011-01-19 08:01

18 楼

atoi 其实挺复杂的,如果输入123rst,那么输出是123;如果输入abc123,那么输出是0.如
果字符串的第一个非空字符不存在，或者不是数字和正负号的话，返回零；否则开始做
类型转换，之后检测到非数字或结束符 \0 时停止转换，返回整型数。
int Atoi(char* string)
{
assert(string != NULL);

int temp = 0;
bool blnMinus = false;

for(int i = 0; i < strlen(string); i ++)
{
if(string[i] >= 48 && string[i] <= 57)
temp = temp * 10 + (string[i] - 48);
else if(string[0] = '-')
blnMinus = true;
else
break;
}

return blnMinus ? -temp : temp;
}

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

: 本来想一起把我的答案发了的，结果被老婆拽去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;

s*82011-01-19 08:01

19 楼

智力题好有趣儿，哈哈，石头会怎么样。要是我我会说，石头会喊"Help!"

面了

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

: 上周五面的，刚刚收到拒信。
: 我本来说想面bing或者azure，不过hr临时给安排了office的一个做排版的组。总共面了
: 四轮。
: 第一轮：一个俄罗斯人，三道白板coding。
: 1. atoi
: 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
: 时间复杂度，如何优化。
: 3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
: 子数字和最大。只能向右和下移动。时间复杂度，如何优化。
: 第二轮：lunch interview，俄罗斯人，几道智力题。

M*u2011-01-19 08:01

20 楼

cft
碰到毛子挺惨。。。

面了
换。
会怎
数。
是棋
会右

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

: 上周五面的，刚刚收到拒信。
: 我本来说想面bing或者azure，不过hr临时给安排了office的一个做排版的组。总共面了
: 四轮。
: 第一轮：一个俄罗斯人，三道白板coding。
: 1. atoi
: 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
: 时间复杂度，如何优化。
: 3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
: 子数字和最大。只能向右和下移动。时间复杂度，如何优化。
: 第二轮：lunch interview，俄罗斯人，几道智力题。

m*92011-01-19 08:01

21 楼

intern也要好好准备呀，不可掉以轻心。我们组的一个intern前段时间在intern结束
时就直接拿到offer了，连面试都省了，半年以后来直接来上班。他在intern面试时也
是正经的5轮。intern要是表现的好直接拿到offer的可能性很大的。

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

: intern居然这么难。

S*I2011-01-19 08:01

22 楼

intern还面5轮，有点BT了吧？

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

: intern也要好好准备呀，不可掉以轻心。我们组的一个intern前段时间在intern结束
: 时就直接拿到offer了，连面试都省了，半年以后来直接来上班。他在intern面试时也
: 是正经的5轮。intern要是表现的好直接拿到offer的可能性很大的。

D*a2011-01-19 08:01

23 楼

住在地底下那个绿色的东西是不是忍者神龟？

面了
换。

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

: 上周五面的，刚刚收到拒信。
: 我本来说想面bing或者azure，不过hr临时给安排了office的一个做排版的组。总共面了
: 四轮。
: 第一轮：一个俄罗斯人，三道白板coding。
: 1. atoi
: 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
: 时间复杂度，如何优化。
: 3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
: 子数字和最大。只能向右和下移动。时间复杂度，如何优化。
: 第二轮：lunch interview，俄罗斯人，几道智力题。

s*i2011-01-19 08:01

24 楼

lol! 这个太搞了！估计就是！！忍者神龟就是made in usa!

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

: 住在地底下那个绿色的东西是不是忍者神龟？
:
: 面了
: 换。

p*w2011-01-19 08:01

25 楼

上周五面的，刚刚收到拒信。
我本来说想面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。

s*f2011-01-19 08:01

26 楼

//2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交
换。
//时间复杂度，如何优化。
bool TotalEqual(Node *t1, Node *t2){
if (!t1 && !t2)
return true;
else if (!t1 || !t2)
return false;
else
return TotalEqual(t1->left, t2->left) && TotalEqual(t1->right, t2->
right) || \
TotalEqual(t1->right, t2->left) && TotalEqual(t1->left, t2->
right);
}
//exchange time: II(node num of each level)

e*s2011-01-19 08:01

27 楼

1. 什么东西是小的，绿色的，住在地面三英尺以下？

s*f2011-01-19 08:01

28 楼

//3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
//子数字和最大。只能向右和下移动。时间复杂度，如何优化。
//well, no good way to express matrix parameter in c.
//i may always transfer to array next time
int MaxSum(int m[][3], int n){
if (!m || !*m || n < 1)
return 0;
int *tmp = new int[n * n];
tmp[0] = m[0][0];
for (int i = 1; i < n; ++i){
tmp[i] = m[0][i] + tmp[i - 1];
tmp[i * n] = m[i][0] + tmp[i * n - n];
}
for (int i = 1; i < n; ++i){
for (int j = 1; j < n; ++j){
tmp[i * n + j] = max(tmp[(i - 1)*n + j], tmp[i * n + j - 1]) + m
[i][j];
}
}
return tmp[n * n - 1];
}

s*f2011-01-19 08:01

29 楼

//3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
//子数字和最大。只能向右和下移动。时间复杂度，如何优化。
//well, no good way to express matrix parameter in c.
//i may always transfer to array next time
int MaxSum(int m[][3], int n){
if (!m || !*m || n < 1)
return 0;
int *tmp = new int[n * n];
tmp[0] = m[0][0];
for (int i = 1; i < n; ++i){
tmp[i] = m[0][i] + tmp[i - 1];
tmp[i * n] = m[i][0] + tmp[i * n - n];
}
for (int i = 1; i < n; ++i){
for (int j = 1; j < n; ++j){
tmp[i * n + j] = max(tmp[(i - 1)*n + j], tmp[i * n + j - 1]) + m
[i][j];
}
}
return tmp[n * n - 1];
}

l*a2011-01-19 08:01

30 楼

what is your time complexity?

的格

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

: //3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
: //子数字和最大。只能向右和下移动。时间复杂度，如何优化。
: //well, no good way to express matrix parameter in c.
: //i may always transfer to array next time
: int MaxSum(int m[][3], int n){
: if (!m || !*m || n < 1)
: return 0;
: int *tmp = new int[n * n];
: tmp[0] = m[0][0];
: for (int i = 1; i < n; ++i){

e*s2011-01-19 08:01

31 楼

时间复杂度，如何优化?

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

: //2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交
: 换。
: //时间复杂度，如何优化。
: bool TotalEqual(Node *t1, Node *t2){
: if (!t1 && !t2)
: return true;
: else if (!t1 || !t2)
: return false;
: else
: return TotalEqual(t1->left, t2->left) && TotalEqual(t1->right, t2->

e*s2011-01-19 08:01

32 楼

Got your point. DP, O(n^2)

的格

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

: //3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
: //子数字和最大。只能向右和下移动。时间复杂度，如何优化。
: //well, no good way to express matrix parameter in c.
: //i may always transfer to array next time
: int MaxSum(int m[][3], int n){
: if (!m || !*m || n < 1)
: return 0;
: int *tmp = new int[n * n];
: tmp[0] = m[0][0];
: for (int i = 1; i < n; ++i){

e*s2011-01-19 08:01

33 楼

public static int maxpathto(int[,] m, int x, int y)
{
if (m == null)
return 0;
if (x < 0 || y < 0)
return 0;
if (x == 0 && y == 0)
return m[x, y];
else
return Math.Max(maxpathto(m, x-1, y), maxpathto(m, x, y-1))
+ m[x,y];
}

g*i2011-01-19 08:01

34 楼

这个lunch interview挺讨厌的啊,竟然还出了5题,楼主给的答案在这里有
http://krics.appspot.com/thread/LeisureTime/213249/2/

m*r2011-01-19 08:01

35 楼

Microsoft用一样的intern题目again?

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

: 这个lunch interview挺讨厌的啊,竟然还出了5题,楼主给的答案在这里有
: http://krics.appspot.com/thread/LeisureTime/213249/2/

l*s2011-01-19 08:01

36 楼

ms jobs:
http://jobguiding.com/it-jobs/it-companies/microsoft.html

面了
换。

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

: 上周五面的，刚刚收到拒信。
: 我本来说想面bing或者azure，不过hr临时给安排了office的一个做排版的组。总共面了
: 四轮。
: 第一轮：一个俄罗斯人，三道白板coding。
: 1. atoi
: 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
: 时间复杂度，如何优化。
: 3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
: 子数字和最大。只能向右和下移动。时间复杂度，如何优化。
: 第二轮：lunch interview，俄罗斯人，几道智力题。