常见：百度微软等算法面试题及答案1

preview
试读
106页
microsoft
需积分: 0 0 下载量 105 浏览量 更新于2022-08-08 收藏 177KB DOCX 举报
常见：百度微软等算法面试题及答案1
程序员面试题精选 100 题 [折叠]
前言
　　随着高校的持续扩张，每年应届毕业生的数目都在不断增长，伴随而来的是应届毕业生的就业压力也
越来越大。
　　在这样的背景下，就业变成一个买方市场的趋势越来越明显。为了找到一个称心的工作，绝大多数应
届毕业生都必须反复经历简历筛选、电话面试、笔试、面试等环节。在这些环节中，面试无疑起到最为重
要的作用，因为通过面试公司能够最直观的了解学生的能力。
　　为了有效地准备面试，面经这个新兴概念应运而生。笔者在当初找工作阶段也从面经中获益匪浅并最
终找到满意的工作。为了方便后来者，笔者花费大量时间收集并整理散落在茫茫网络中的面经。不同行业
的面经全然不同，笔者从自身专业出发，着重关注程序员面试的面经，并从精选出若干具有代表性的技术
类的面试题展开讨论，希望能给读者带来一些启发。
　　由于笔者水平有限，给各面试题提供的思路和代码难免会有错误，还请读者批评指正。另外，热忱欢
迎读者能够提供更多、更好的面试题，本人将感激不尽。
--------------------------------------------------------------------------------------------
-------------------------------------------------
(01)把二元查找树转变成排序的双向链表
　　题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结
点，只调整指针的指向。
　　比如将二元查找树
10
/ \
6 14
/ \ /　 \
4 8 12 　 16
转换成双向链表
4=6=8=10=12=14=16。
　　分析：本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也不例外。下面我
们用两种不同的递归思路来分析。
　　思路一：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树转换成
一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的最右结点（左子树的最大结
点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调整所有结点。
　　思路二：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一
个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到
链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。
参考代码：
首先我们定义二元查找树结点的数据结构如下：
struct BSTreeNode // a node in the binary search tree
{
int m_nValue; // value of node：当前节点的值
BSTreeNode *m_pLeft; // left child of node：指向左子节点的指针
BSTreeNode *m_pRight; // right child of node：指向右子节点的指针
};
思路一对应的代码：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树
转换成一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的最右结点（左子树的
最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调整所有结
点。
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
// asRight - whether pNode is the right child of its parent
// Output: if asRight is true, return the least node in the sub-tree 如果 asRight 为 true，则返回子树中的最小节点
// else return the greatest node in the sub-tree 否则，返回子树中最大的节点
///////////////////////////////////////////////////////////////////////
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
{
if(!pNode)
return NULL;
//定义左子树和右子树的指针
BSTreeNode *pLeft = NULL;
BSTreeNode *pRight = NULL;
// Convert the left sub-tree，如果当前节点 pNode 的左节点 m_pLeft 不为空，则递归左子树，并 false 返回
左子树中最小值
if(pNode->m_pLeft)
pLeft = ConvertNode(pNode->m_pLeft, false);
// Connect the greatest node in the left sub-tree to the current node 将左子树当中的最大节点赋值给当前节点
进行调整
if(pLeft)
{
pLeft->m_pRight = pNode;
pNode->m_pLeft = pLeft;
}
// Convert the right sub-tree，如果当前节点 pNode 的右节点 m_pRight 不为空，则递归右子树，并 true 返
回右子树中的最小值
if(pNode->m_pRight)
pRight = ConvertNode(pNode->m_pRight, true);
// Connect the least node in the right sub-tree to the current node 将右子树当中的最小节点赋值给当前节点进
行调整
if(pRight)
{
pNode->m_pRight = pRight;
pRight->m_pLeft = pNode;
}
BSTreeNode *pTemp = pNode;
// If the current node is the right child of its parent, 如果当前节点的右孩子是它的父亲节点
// return the least node in the tree whose root is the current node。则返回当前节点树中的最小节点
if(asRight)
{
while(pTemp->m_pLeft)
pTemp = pTemp->m_pLeft;
}
// If the current node is the left child of its parent, 如果当前节点的左孩子是它的父亲节点
// return the greatest node in the tree whose root is the current node。则返回当前节点的最大节点
else
{
while(pTemp->m_pRight)
pTemp = pTemp->m_pRight;
}
return pTemp;
}
///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
// As we want to return the head of the sorted double-linked list,
// we set the second parameter to be true。初始调用点
return ConvertNode(pHeadOfTree, true);
}
思路二对应的代码：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每
访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其
链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
// pLastNodeInList - the tail of the double-linked list
///////////////////////////////////////////////////////////////////////
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
if(pNode == NULL)
return;
BSTreeNode *pCurrent = pNode;
// Convert the left sub-tree，如果当前节点的左子树不为空，则递归调用左子树
if (pCurrent->m_pLeft != NULL)
ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
// Put the current node into the double-linked list，将当前节点赋值给 pLastNodeInList 链表
pCurrent->m_pLeft = pLastNodeInList;
if(pLastNodeInList != NULL)
pLastNodeInList->m_pRight = pCurrent;
pLastNodeInList = pCurrent;
// Convert the right sub-tree，如果右子树不为空，则递归调用右子树
if (pCurrent->m_pRight != NULL)
ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}
///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list，按中序遍历方式的调用情况
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
{
BSTreeNode *pLastNodeInList = NULL;
ConvertNode(pHeadOfTree, pLastNodeInList);
// Get the head of the double-linked list
BSTreeNode *pHeadOfList = pLastNodeInList;
while(pHeadOfList && pHeadOfList->m_pLeft)
pHeadOfList = pHeadOfList->m_pLeft;
return pHeadOfList;
}
----------------------------------------------------------------------------------------------------------
-
(02)设计包含 min 函数的栈
题目：定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。要求函数 min、push 以及 pop
的时间复杂度都是 O(1)。
分析：这是去年 google 的一道面试题。
我看到这道题目时，第一反应就是每次 push 一个新元素时，将栈里所有逆序元素排序。这样栈顶元素将是
最小元素。但由于不能保证最后 push 进栈的元素最先出栈，这种思路设计的数据结构已经不是一个栈了。
在栈里添加一个成员变量存放最小元素（或最小元素的位置）。每次 push 一个新元素进栈的时候，如果该
元素比当前的最小元素还要小，则更新最小元素。
乍一看这样思路挺好的。但仔细一想，该思路存在一个重要的问题：如果当前最小元素被 pop 出去，如何
才能得到下一个最小元素？
因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。我们需要一个辅助栈。每次
push 一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结
构，用最小元素的位置将能减少空间消耗）push 到辅助栈中；每次 pop 一个元素出栈的时候，同时 pop
辅助栈。
参考代码：
#include <deque>
#include <assert.h>
template <typename T> class CStackWithMin
{
public:
CStackWithMin(void) {}
virtual ~CStackWithMin(void) {}
T& top(void);
const T& top(void) const;
void push(const T& value);
void pop(void);
const T& min(void) const;
private:
T>m_data;// theelements of stack
size_t>m_minIndex;// the indicesof minimum elements
};
// get the last element of mutable stack

剩余105页未读，继续阅读

资源推荐
资源评论
yxldr
  • 粉丝: 23
  • 资源: 326
上传资源 快速赚钱
voice
center-task 前往需求广场，查看用户热搜

最新资源