微软数据结构算法面试100题全解

需积分: 50 10 浏览量更新于2024-07-27 1 收藏 370KB PDF 举报

"微软等数据结构算法面试100题答案集锦" 这篇资源是一份由July和阿财共同整理的微软公司数据结构和算法面试题的综合答案集锦，主要面向那些希望进入大型IT公司，尤其是微软，从事软件开发工作的应届毕业生。这份资料的发布日期为2011年10月13日，正值July创建博客一周年之际。July的博客"结构之法算法之道"因其深入讨论编程面试和算法研究而广受欢迎，影响力不仅限于国内，还延伸到了国际互联网。在July的博客中，他最初分享了微软面试的前60道题目的答案，但由于各种原因，剩余的40题答案没有及时整理发布。然而，近期阿财，一位在美国加州的朋友，主动提供了他完成的全部100题的答案，使得这份资料得以完整。July认为，答案只是参考，不应过分依赖，而且他一直在对这些问题进行深入分析和优化，以形成"程序员编程艺术"系列文章。此资源的价值在于它提供的多样化的解题思路，对于准备面试的人来说，可以对比不同解答，学习不同的解决问题的方法。尽管July已上传了前60题的答案，但他还是决定将阿财提供的完整答案集锦公开，以便大家有更多的参考和学习机会。July鼓励读者如果发现任何问题，积极提出，以促进共同学习和进步。这份100题的答案集锦在社区中引起了广泛关注，许多人在微软100题的讨论中贡献了自己的见解和解决方案，这充分体现了开源和分享的精神，促进了技术知识的传播和提升。对于准备面试的人来说，这是一个宝贵的资源，可以帮助他们更好地理解和应用数据结构和算法，从而在面试中脱颖而出。

char * p = sub;

int len = 0;

int TO_REDUCE = 1;

while (*p!= ’ \0 ’ ) {

dest = HBASE * dest + (int)(*p);

TO_REDUCE *= HBASE;

len ++;

}

int hash = 0;

p = str;

int i=0;

while (*p !=

‘

’

) {

if (i++<len) hash = HBASE * dest + (int)(*p);

else hash = (hash - (TO_REDUCE * (int)(*(p-len))))*HBASE + (int)(*p);

if (hash == dest && i>=len && strncmp(sub, p-len+1, len) == 0) return i-len;

p++;

}

return -1;

}

★ 比较两个字符串，用 O(n) 时间和恒量空间。

ANSWER:

What is “ comparing two strings ” ? Just normal string comparison? The natural way use O(n) time and O(1)

space.

int strcmp(char * p1, char * p2) {

while (*p1 != ‘ \0 ’ && *p2 != ‘ \0 ’ && *p1 == *p2) {

p1++, p2++;

}

if (*p1 ==

‘

’

&& *p2 ==

‘

’

) return 0;

if (*p1 == ‘ \0 ’ ) return -1;

if (*p2 == ‘ \0 ’ ) return 1;

return (*p1 - *p2); // it can be negotiated whether the above 3 if ’ s are necessary,

don ’ t like to omit them.

}

★ 假设你有一个用 1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在 1 到

1000( 包括 1000) 之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做

一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种

方式的算法吗 ?

ANSWER:

Sum up all the numbers, then subtract the sum from 1001*1002/2.

Another way, use A XOR A XOR B = B:

int findX(int a[]) {

int k = a[0];

for (int i=1; i<=1000;i++)

k ~= a[i]~i;

}

return k;

}

★ 不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。

ANSWER:

n<<3;

(n<<3)-n;

第 9 题

判断整数序列是不是二元查找树的后序遍历结果

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。

如果是返回 true ，否则返回 false 。

例如输入 5 、 7 、 6 、 9 、 11 、 10 、 8 ，由于这一整数序列是如下树的后序遍历结果：

/ \

6 10

/ \ / \

5 7 9 11

因此返回 true 。

如果输入 7 、 4 、 6 、 5 ，没有哪棵树的后序遍历的结果是这个序列，因此返回 false 。

ANSWER:

This is an interesting one. There is a traditional question that requires the binary tree to be re-constructed

from mid/post/pre order results. This seems similar. For the problems related to (binary) trees, recursion is

the first choice.

In this problem, we know in post-order results, the last number should be the root. So we have known the

root of the BST is 8 in the example. So we can split the array by the root.

int isPostorderResult(int a[], int n) {

return helper(a, 0, n-1);

}

int helper(int a[], int s, int e) {

if (e==s) return 1;

int i=e-1;

while (a[e]>a[i] && i>=s) i--;

if (!helper(a, i+1, e-1))

return 0;

int k = l;

while (a[e]<a[i] && i>=s) i--;

return helper(a, s, l);

}

第 10 题

翻转句子中单词的顺序。

题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。

句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。

例如输入

“

am a student.

”

，则输出

“

student. a am

”

。

Answer:

Already done this. Skipped.

第 11 题

求二叉树中节点的最大距离 ...

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，

我们姑且定义 " 距离 " 为两节点之间边的个数。

写一个程序，

求一棵二叉树中相距最远的两个节点之间的距离。

ANSWER:

This is interesting... Also recursively, the longest distance between two nodes must be either from root to

one leaf, or between two leafs. For the former case, it ’ s the tree height. For the latter case, it should be the

sum of the heights of left and right subtrees of the two leaves ’ most least ancestor.

The first case is also the sum the heights of subtrees, just the height + 0.

int maxDistance(Node * root) {

int depth;

return helper(root, depth);

}

int helper(Node * root, int &depth) {

if (root == NULL) {

depth = 0; return 0;

}

int ld, rd;

int maxleft = helper(root->left, ld);

int maxright = helper(root->right, rd);

depth = max(ld, rd)+1;

return max(maxleft, max(maxright, ld+rd));

}

第 12 题

题目：求 1+2+ … +n ，

要求不能使用乘除法、 for 、 while 、 if 、 else 、 switch 、 case 等关键字以及条件判断语句

（ A?B:C ）。

ANSWER:

剩余45页未读，继续阅读

天行健01

粉丝: 9
资源: 3

微软数据结构算法面试100题全解

java面试题及答案-非常全面（包括基础、网络、数据结构、算法及IT大厂面经）

【July整理】微软等数据结构+算法面试100题[附完整答案]

数据结构和算法面试100题及答案.rar v

微软等数据结构 算法面试100题全部答案集锦

微软等数据结构算法面试100题全部答案集锦

微软数据结构算法面试100题答案集锦

微软等数据结构算法面试100题全部答案集锦.pdf

微软等数据结构 算法面试100题全部答案集锦.doc

微软等数据结构算法面试100题全部答案

微软等数据结构 算法面试100题

最新资源

微软等数据结构算法面试100题全部答案集锦

微软等数据结构算法面试100题全部答案集锦.doc

微软等数据结构算法面试100题