2024年程序员面试题100题.doc

程序员面试题精选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
// 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
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
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* ConvertBSTreeNode* 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-searchtree 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
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)。
分析：这是去年谷歌的一道面试题。
我看到这道题目时，第一反应就是每次push一个新元素时，将栈里所有逆序元素排序。这么栈顶元素将是最小元素。但因为不能确保最后push进栈的元素最先出栈，这种思绪设计的数据结构已经不是一个栈了。
在栈里添加一个组员变量存储最小元素（或最小元素的位置）。每次push一个新元素进栈的时候，假如该元素比目前的最小元素还要小，则更新最小元素。
乍一看这么思绪挺好的。但仔细一想，该思绪存在一个重要的问题：假如目前最小元素被pop出去，怎样才能得到下一个最小元素？
因此仅仅只添加一个组员变量存储最小元素（或最小元素的位置）是不够的。我们需要一个辅助栈。每次push一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元素的类型也许是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；每次pop一个元素出栈的时候，同时pop辅助栈。
参考代码：
#include
#include

template 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
template ename T> T& CStackWithMin::top()
{
return m_data.back();
}

// get the last element of non-mutable stack
template const T& CStackWithMin::top() const
{
return m_data.back();
}

// insert an elment at the end of stack
template void CStackWithMin::push(const T& value)
{
// append the data into the end of m_data
m_data.push_back(value);

// set the index of minimum elment in m_data at the end of m_minIndex
if(m_minIndex.size() == 0)
m_minIndex.push_back(0);
else
{
if(value < m_data[m_minIndex.back()])
m_minIndex.push_back(m_data.size() - 1);
else
m_minIndex.push_back(m_minIndex.back());
}
}

// erease the element at the end of stack
template void CStackWithMin::pop()
{
// pop m_data
m_data.pop_back();

// pop m_minIndex
m_minIndex.pop_back();
}

// get the minimum element of stack
template const T& CStackWithMin::min() const
{
assert(m_data.size() > 0);
assert(m_minIndex.size() > 0);

return m_data[m_minIndex.back()];
}
举个例子演示上述代码的运行过程：
  步骤              数据栈            辅助栈                最小值
1.push 3    3          0             3
2.push 4    3,4        0,0           3
3.push 2    3,4,2      0,0,2         2
4.push 1    3,4,2,1    0,0,2,3       1
5.pop       3,4,2      0,0,2         2
6.pop       3,4        0,0           3
7.push 0    3,4,0      0,0,2         0
讨论：假如思绪正确，编写上述代码不是一件极难的事情。但假如能注意某些细节无疑能在面试中加分。例如我在上面的代码中做了如下的工作：
·         用模板类实现。假如他人的元素类型只是int类型，模板将能给面试官带来好印象；
·         两个版本的top函数。在诸多类中，都需要提供const和非const版本的组员访问函数；
·         min函数中assert。把代码写的尽也许安全是每个软件企业对程序员的要求；
·         添加某些注释。注释既能提升代码的可读性，又能增加代码量，何乐而不为？
总之，在面试时假如时间允许，尽也许把代码写的漂亮某些。说不定代码中的几个小亮点就能让自己轻松拿到心仪的Offer。
(03)－求子数组的最大和
   [折叠]

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。
分析：本题最初为浙江大学计算机系的考研题的最后一道程序设计题，在里包括谷歌在内的诸多知名企业都把本题当作面试题。因为本题在网络中广为流传，本题也顺利成为程序员面试题中经典中的经典。
假如不考虑时间复杂度，我们能够枚举出所有子数组并求出他们的和。不过非常遗憾的是，因为长度为n的数组有O(n2)个子数组；并且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思绪的时间是O(n3)。
很轻易了解，当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。假如目前得到的和是个负数，那么这个和在接下来的累加中应当抛弃并重新清零，否则的话这个负数将会减少接下来的和。基于这么的思绪，我们能够写出如下代码。
参考代码：
/////////////////////////////////////////////////////////////////////////////
// Find the greatest sum of all sub-arrays
// Return value: if the input is valid, return true, otherwise return false
/////////////////////////////////////////////////////////////////////////////
bool FindGreatestSumOfSubArray
(
int *pData, // an array
unsigned int nLength, // the length of array
int &nGreatestSum // the greatest sum of all sub-arrays
)
{
// if the input is invalid, return false
if((pData == NULL) || (nLength == 0))
return false;

int nCurSum = nGreatestSum = 0;
for(unsigned int i = 0; i < nLength; ++i)
{
nCurSum += pData[i];

// if the current sum is negative, discard it
if(nCurSum < 0)
nCurSum = 0;

// if a greater sum is found, update the greatest sum
if(nCurSum > nGreatestSum)
nGreatestSum = nCurSum;
}

// if all data are negative, find the greatest element in the array
if(nGreatestSum == 0)
{
nGreatestSum = pData[0];
for(unsigned int i = 1; i < nLength; ++i)
{
if(pData[i] > nGreatestSum)
nGreatestSum = pData[i];
}
}

return true;
} 
讨论：上述代码中有两点值得和大家讨论一下：
·         函数的返回值不是子数组和的最大值，而是一个判断输入是否有效的标志。假如函数返回值的是子数组和的最大值，那么当输入一个空指针是应当返回什么呢？返回0？那这个函数的用户怎么辨别输入无效和子数组和的最大值刚好是0这两中情况呢？基于这个考虑，本人以为把子数组和的最大值以引用的方式放到参数列表中，同时让函数返回一个函数是否正常执行的标志。
·         输入有一类特殊情况需要特殊处理。当输入数组中所有整数都是负数时，子数组和的最大值就是数组中的最大元素。
(04)－在二元树中找出和为某一值的所有途径   [折叠]
题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所通过的所有结点形成一条途径。打印出和与输入整数相等的所有途径。
例如输入整数22和如下二元树
                                            10
                                          /   \
                                          5     12
                                        /   \   
                                     　4     7 
则打印出两条途径：10, 12和10, 5, 7。
二元树结点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
分析：这是百度的一道笔试题，考查对树这种基本数据结构以及递归函数的了解。
当访问到某一结点时，把该结点添加到途径上，并累加目前结点的值。假如目前结点为叶结点并且目前途径的和刚好等于输入的整数，则目前的途径符合要求，我们把它打印出来。假如目前结点不是叶结点，则继续访问它的子结点。目前结点访问结束后，递归函数将自动回到父结点。因此我们在函数退出之前要在途径上删除目前结点并减去目前结点的值，以确保返回父结点时途径刚好是根结点到父结点的途径。我们不难看出保存途径的数据结构实际上是一个栈结构，因为途径要与递归调用状态一致，而递归调用本质就是一个压栈和出栈的过程。
参考代码：
///////////////////////////////////////////////////////////////////////
// Find paths whose sum equal to expected sum
///////////////////////////////////////////////////////////////////////
void FindPath
(
BinaryTreeNode* pTreeNode, // a node of binary tree
int expectedSum, // the expected sum
std::vector&path, // a pathfrom root to current node
int& currentSum // the sum of path
)
{
if(!pTreeNode)
return;

currentSum += pTreeNode->m_nValue;
path.push_back(pTreeNode->m_nValue);

// if the node is a leaf, and the sum is same as pre-defined, 
// the path is what we want. print the path
bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
if(currentSum == expectedSum && isLeaf)
{
std::vector::iterator iter =path.begin();
for(; iter != path.end(); ++ iter)
std::cout<<*iter<<'\t';
std::cout<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
#include
#include

using namespace std;

typedef multiset > IntHeap;

///////////////////////////////////////////////////////////////////////
// find k least numbers in a vector
///////////////////////////////////////////////////////////////////////
void FindKLeastNumbers
(
const vector& data, // a vector of data
IntHeap& leastNumbers, // k least numbers, output
unsigned int k
)
{
leastNumbers.clear();

if(k == 0 || data.size() < k)
return;

vector::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);
}
}
}
}
(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