微软面世经过# JobHunting - 待字闺中
f*5
1 楼
一直在班上潜水，现在也把我的面世经历和大家分享，希望对各位有所帮助！
在微软一共见了5个人。
1． 第一个人问了一些关于XQUERY的问题，这个和我的背景有关，不会每个人都问
的。
2． 第二个人先问了一个单链表的实现问题，然后文了一个有关图形的算法体：有
一个M*N的integer矩阵，现在要做的是扫描这个矩阵，如果（i,j）是0，那么把地i行
和第j列都变成0。答案如下：
a) 最简单的算法是扫描两边，第一遍时用另一个m*n矩阵记录下应该变成0的位置，
然后第二遍的时候复制那些0；
b) 然后要求减少空间需求，我给的算法是用一个m+n的数组记录下第i行/列是否需
要变成0，然后第二遍时复制0；
c) 最后的算法是reuse原来的矩阵的第一行和第一列as the m+n array, but we
need one additional integer since the first row and the first column
overlaps in the position (0,0).这个算法是空间复杂度是O(1)
3． 第三个人问了一下
在微软一共见了5个人。
1． 第一个人问了一些关于XQUERY的问题，这个和我的背景有关，不会每个人都问
的。
2． 第二个人先问了一个单链表的实现问题，然后文了一个有关图形的算法体：有
一个M*N的integer矩阵，现在要做的是扫描这个矩阵，如果（i,j）是0，那么把地i行
和第j列都变成0。答案如下：
a) 最简单的算法是扫描两边，第一遍时用另一个m*n矩阵记录下应该变成0的位置，
然后第二遍的时候复制那些0；
b) 然后要求减少空间需求，我给的算法是用一个m+n的数组记录下第i行/列是否需
要变成0，然后第二遍时复制0；
c) 最后的算法是reuse原来的矩阵的第一行和第一列as the m+n array, but we
need one additional integer since the first row and the first column
overlaps in the position (0,0).这个算法是空间复杂度是O(1)
3． 第三个人问了一下