没有合适的资源?快使用搜索试试~ 我知道了~
首页微软面试100题全解:C++工程师必备
微软面试100题全解:C++工程师必备
需积分: 10 4 下载量 76 浏览量
更新于2024-07-21
收藏 359KB PDF 举报
微软面试100题是一份由July和阿财两位作者共同整理的面试题库,旨在帮助求职者准备微软等公司的数据结构和算法面试。这份题库包含100个面试题目,涵盖了面试中常见的核心概念和技术挑战。发布于2011年10月,初衷是作为博主周年庆的回馈,让读者在学习和交流中提升自己的技能。 七月最初仅整理了前60题,提供了下载链接,但由于个人原因,如时间冲突和个人对答案质量的追求,导致后40题的答案延迟发布。他认为答案仅供参考,不应过度依赖,同时也在不断更新和完善,通过撰写文章分享更深入的解题思路和技巧,将这些题目提升到程序员编程艺术的层面。 阿财在美国加州的朋友主动提供了完整的100题答案,使得这份宝贵的资源得以完整呈现。尽管七月之前上传的前60题可能存在问题和不足,但现在有了阿财的补充,求职者可以得到更加全面的复习材料。这份题库对于准备微软面试的人来说是一个宝贵的参考资料,许多关注者也积极参与讨论,分享各自的理解和解题方法。 阅读这份100题集锦,不仅有助于掌握数据结构和算法的基础知识,还能锻炼面试技巧和问题解决能力。同时,它也体现了互联网开放共享的精神,让知识得以快速传播和提升。如果你对微软面试有任何疑问,鼓励大家积极提问和反馈,共同提升IT行业的技术实力。
资源详情
资源推荐
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 !=
‘
\0
’
) {
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 ==
‘
\0
’
&& *p2 ==
‘
\0
’
) 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,
I
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 ,由于这一整数序列是如下树的后序遍历结果:
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 题
翻转句子中单词的顺序。
题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。
句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。
例如输入
“
I
am a student.
”
,则输出
“
student. a am
I
”
。
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:
1+..+n=n*(n+1)/2=(n^2+n)/2
it is easy to get x/2, so the problem is to get n^2
though no if/else is allowed, we can easilly go around using short-pass.
using macro to make it fancier:
#define T(X, Y, i) (Y & (1<<i)) && X+=(Y<<i)
int foo(int n){
int r=n;
T(r, n, 0); T(r, n,1); T(r, n, 2); … T(r, n, 31);
return r >> 1;
}
第 13 题:
题目:输入一个单向链表,输出该链表中倒数第 k 个结点。链表的倒数第 0 个结点为链表的尾指针。
链表结点定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
Answer:
Two ways. 1: record the length of the linked list, then go n-k steps. 2: use two cursors.
Time complexities are exactly the same.
Node * lastK(Node * head, int k) {
if (k<0) error( “ k < 0 ” );
Node *p=head, *pk=head;
for (;k>0;k--) {
if (pk->next!=NULL) pk = pk->next;
else return NULL;
}
while (pk->next!=NULL) {
p=p->next, pk=pk->next;
}
return p;
}
第 14 题:
题目:输入一个已经按升序排序过的数组和一个数字,
在数组中查找两个数,使得它们的和正好是输入的那个数字。
要求时间复杂度是 O(n) 。如果有多对数字的和等于输入的数字,输出任意一对即可。
例如输入数组 1 、 2 、 4 、 7 、 11 、 15 和数字 15 。由于 4+11=15 ,因此输出 4 和 11 。
ANSWER:
Use two cursors. One at front and the other at the end. Keep track of the sum by moving the cursors.
void find2Number(int a[], int n, int dest) {
int *f = a, *e=a+n-1;
int sum = *f + *e;
while (sum != dest && f < e) {
if (sum < dest) sum = *(++f);
else sum = *(--e);
}
if (sum == dest) printf( “ %d, %d\n ” , *f, *e);
}
第 15 题:
题目:输入一颗二元查找树,将该树转换为它的镜像,
即在转换后的二元查找树中,左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入:
8
/ \
6 10
剩余45页未读,继续阅读
yyzeagle
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- IPQ4019 QSDK开源代码资源包发布
- 高频组电赛必备:掌握数字频率合成模块要点
- ThinkPHP开发的仿微博系统功能解析
- 掌握Objective-C并发编程:NSOperation与NSOperationQueue精讲
- Navicat160 Premium 安装教程与说明
- SpringBoot+Vue开发的休闲娱乐票务代理平台
- 数据库课程设计:实现与优化方法探讨
- 电赛高频模块攻略:掌握移相网络的关键技术
- PHP简易简历系统教程与源码分享
- Java聊天室程序设计:实现用户互动与服务器监控
- Bootstrap后台管理页面模板(纯前端实现)
- 校园订餐系统项目源码解析:深入Spring框架核心原理
- 探索Spring核心原理的JavaWeb校园管理系统源码
- ios苹果APP从开发到上架的完整流程指南
- 深入理解Spring核心原理与源码解析
- 掌握Python函数与模块使用技巧
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功