没有合适的资源?快使用搜索试试~ 我知道了~
首页微软面试精华:100道算法与数据结构题
微软面试100题是一份备受关注的面试准备资料,针对的是应聘微软职位的求职者,特别是程序员。这份资源包含了100个精选的编程面试题,主要涵盖算法、数据结构等内容,旨在帮助求职者提升技能,为简历筛选、电话面试、笔试和面对面面试做好充分准备。面试题目的设计既考察基础理论知识,又注重实际问题解决能力,例如将二元查找树转换成排序的双向链表。 题目"把二元查找树转变成排序的双向链表"是其中一道经典题目,它要求在不增加新节点的前提下,仅通过调整指针来完成树到链表的转换。解决这个问题有两种递归思路: 1. 第一种方法是采用自顶向下的方式,从根节点开始,先递归地处理左子树,将其转换为有序的左链表,然后处理右子树,将两者连接起来。关键在于找到左子链表的最右节点与右子树的最左节点进行连接,确保链表保持有序。 2. 另一种方法则是中序遍历整个二叉查找树,每次访问的结点都小于或等于当前结点,这样自然形成了递增顺序。在遍历过程中,每访问一个结点,将其插入到已排序链表的末尾,最终得到有序的双向链表。 在提供代码实现时,首先定义了一个二元查找树结点的数据结构,包括值(m_nValue)和指向左右子节点的指针。具体的代码实现展示了如何利用这些数据结构和逻辑来完成转换。 这份微软面试100题资源对于求职者来说是一个宝贵的资源,它不仅能检验和提升编程技能,还能熟悉面试流程和常见问题类型,提高求职成功率。但作者也提醒读者,由于个人水平有限,部分答案可能存在不足,鼓励读者积极参与讨论,分享更多高质量的面试题和解法。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/4445208/bgb.jpg)
std::cout<<*iter<<'\t';
std::cout<<std::endl;
}
// if the node is not a leaf, goto its children
if(pTreeNode->m_pLeft)
FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
if(pTreeNode->m_pRight)
FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);
// when we finish visiting a node and return to its parent node,
// we should delete this node from the path and
// minus the node's value from the current sum
currentSum -= pTreeNode->m_nValue; //!!I think here is no use
path.pop_back();
}
(05)查找最小的 k 个元素
题目:输入 n 个整数,输出其中最小的 k 个。
例如输入 1,2,3,4,5,6,7 和 8 这 8 个数字,则最小的 4 个数字为 1,2,3 和 4。
分析:这道题最简单的思路莫过于把输入的 n 个整数排序,这样排在最前面的 k 个数就是
最小的 k 个数。只是这种思路的时间复杂度为 O(nlogn)。我们试着寻找更快的解决思路。
我们可以开辟一个长度为 k 的数组。每次从输入的 n 个整数中读入一个数。如果数组中已
经插入的元素少于 k 个,则将读入的整数直接放到数组中。否则长度为 k 的数组已经满了,
不能再往数组里插入元素,只能替换了。如果读入的这个整数比数组中已有 k 个整数的最
大值要小,则用读入的这个整数替换这个最大值;如果读入的整数比数组中已有 k 个整数
的最大值还要大,则读入的这个整数不可能是最小的 k 个整数之一,抛弃这个整数。这种
思路相当于只要排序 k 个整数,因此时间复杂可以降到 O(n+nlogk)。通常情况下 k 要远小
于 n,所以这种办法要优于前面的思路。
这是我能够想出来的最快的解决方案。不过从给面试官留下更好印象的角度出发,我们可
以进一步把代码写得更漂亮一些。从上面的分析,当长度为 k 的数组已经满了之后,如果
需要替换,每次替换的都是数组中的最大值。在常用的数据结构中,能够在 O(1)时间里得
到最大值的数据结构为最大堆。因此我们可以用堆(heap)来代替数组。
另外,自己重头开始写一个最大堆需要一定量的代码。我们现在不需要重新去发明车轮,
因为前人早就发明出来了。同样,STL 中的 set 和 multiset 为我们做了很好的堆的实现,
我们可以拿过来用。既偷了懒,又给面试官留下熟悉 STL 的好印象,何乐而不为之?
参考代码:
#include <set>
#include <vector>
#include <iostream>
![](https://csdnimg.cn/release/download_crawler_static/4445208/bgc.jpg)
using namespace std;
typedef multiset<int, greater<int> > IntHeap;
/////////////////////////////////////////////////////////////////////
//
// find k least numbers in a vector
/////////////////////////////////////////////////////////////////////
//
void FindKLeastNumbers
(
const vector<int>& data, // a vector of data
IntHeap& leastNumbers, // k least numbers, output
unsigned int k
)
{
leastNumbers.clear();
if(k == 0 || data.size() < k)
return;
vector<int>::const_iterator iter = data.begin();
for(; iter != data.end(); ++ iter)
{
// if less than k numbers was inserted into leastNumbers
if((leastNumbers.size()) < k)
leastNumbers.insert(*iter);
// leastNumbers contains k numbers and it's full now
else
{
// first number in leastNumbers is the greatest one
IntHeap::iterator iterFirst = leastNumbers.begin();
// if is less than the previous greatest number
if(*iter < *(leastNumbers.begin()))
{
// replace the previous greatest number
leastNumbers.erase(iterFirst);
leastNumbers.insert(*iter);
}
}
}
![](https://csdnimg.cn/release/download_crawler_static/4445208/bgd.jpg)
}
(06)判断整数序列是不是二元查找树的后序遍历结果
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返
回 true,否则返回 false。
例如输入 5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回 true。
如果输入 7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回 false。
分析:这是一道 trilogy 的笔试题,主要考查对二元查找树的理解。
在后续遍历得到的序列中,最后一个元素为树的根结点。从头开始扫描这个序列,比根结
点小的元素都应该位于序列的左半部分;从第一个大于跟结点开始到跟结点前面的一个元
素为止,所有元素都应该大于跟结点,因为这部分元素对应的是树的右子树。根据这样的
划分,把序列划分为左右两部分,我们递归地确认序列的左、右两部分是不是都是二元查
找树。
参考代码:
using namespace std;
/////////////////////////////////////////////////////////////////////
//
// Verify whether a squence of integers are the post order traversal
// of a binary search tree (BST)
// Input: squence - the squence of integers
// length - the length of squence
// Return: return ture if the squence is traversal result of a BST,
// otherwise, return false
/////////////////////////////////////////////////////////////////////
//
bool verifySquenceOfBST(int squence[], int length)
{
if(squence == NULL || length <= 0)
return false;
// root of a BST is at the end of post order traversal squence
int root = squence[length - 1];
剩余63页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
sunkai1209111
- 粉丝: 0
- 资源: 5
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 解决Eclipse配置与导入Java工程常见问题
- 真空发生器:工作原理与抽吸性能分析
- 爱立信RBS6201开站流程详解
- 电脑开机声音解析:故障诊断指南
- JAVA实现贪吃蛇游戏
- 模糊神经网络实现与自学习能力探索
- PID型模糊神经网络控制器设计与学习算法
- 模糊神经网络在自适应PID控制器中的应用
- C++实现的学生成绩管理系统设计
- 802.1D STP 实现与优化:二层交换机中的生成树协议
- 解决Windows无法完成SD卡格式化的九种方法
- 软件测试方法:Beta与Alpha测试详解
- 软件测试周期详解:从需求分析到维护测试
- CMMI模型详解:软件企业能力提升的关键
- 移动Web开发框架选择:jQueryMobile、jQTouch、SenchaTouch对比
- Java程序设计试题与复习指南
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)