Microsoft面试

来源：百度文库 编辑：神马文学网 时间：2024/07/03 12:36:11
在微软一共见了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．    第三个人问了一下基本的问题：如果要在一个pda上面设计一个游戏算法，怎么
做？我给的答案是用博弈树，but limit the number of levels explored;第二个问题
是很简单的双链表的实现问题。
4．    第四个人问了一个比较难的问题：有一个integer数组， 怎么样找出一个sub-
array, so that the sum of the elements in the sub-array is maximized. 这个问
题我打得不太好，给了一个recursive的算法，但是应该不是最优解，想听听大家的意
见。
5．    第五个人是大boss,他问了一个问题：一个二维空间的第一象限有很多点，问怎
么能够找出最外围的那些点。答案：
a)    connect (0,0) with a point, this line and the x axis forms an angle,
find out the point with the minimal angle. Suppose this point is x1.
b)    Connect x1 with any other point, this line and the horizontal line
crossing x1 forms an angle, find out the point with the minimal angle.
Suppose it is x2
c)    Connect x2 with any other point (than x1 and x2), this line and the
line crossing x1 and x2 forms an angle, find out the point with the minimal
angle. Suppose it is x3.
d)    Repeat c) until we find x1.
6．    感想：总的来说题目应该不是太难，也没有变态的brain teaser, 只要大家不
要慌张，应该可以拿到offer. 祝大家都心想事成！
Microsoft面试 Microsoft的面试说明 Microsoft OneNote Microsoft Corporation Microsoft Excel Microsoft Office Microsoft Update Microsoft Office Microsoft Live全景图 Microsoft Goes Bonkers Microsoft 全文搜索技术 Microsoft群集解决方案 Microsoft Live全景图 Microsoft 关联算法 Microsoft Interview IQ questions Microsoft 关联算法 Microsoft Windows 错误报告 Microsoft Interview IQ questions Microsoft Live全景图 Microsoft COFEE泄漏 Microsoft Office 2007 注册码 Microsoft Visual FoxPro Microsoft Office 2007 Microsoft程序员测试题