程序员面试题精选100题详解：微软Google技术挑战

5星 · 超过95%的资源需积分: 13 120 浏览量更新于2024-07-28 1 收藏 906KB PDF 举报

《程序员面试题精选100题-何海涛》是一本针对求职程序员编写的实用指南，由何海涛整理并分享，旨在帮助应届毕业生更好地应对面试挑战。这本书主要关注于技术类面试题，内容涵盖了微软、Google等知名公司的面试常见问题。在当前就业市场中，面试的重要性不言而喻，它能帮助雇主直接评估应聘者的实际能力。作者分享了面试题目的整理过程，指出许多与树相关的问题常常采用递归的方法解决。例如，书中提供了一个具体题目——如何将一棵二元查找树转换成一个排序的双向链表，要求仅通过调整指针方向完成，而不能创建新的节点。这道题展示了递归策略的应用，其中可能涉及深度优先搜索（DFS）或先序遍历的思路。作者强调，由于个人水平有限，书中的解答可能存在不足，鼓励读者提供反馈和补充，以不断完善内容。此外，作者保留了对博客文章的版权，并提醒在转发或出版时务必注明原出处。这本书不仅提供了实战经验，还包含了面试技巧和策略，对于准备进入职场的程序员来说，是一份宝贵的参考资料。

http://zhedahht.blog.163.com/blog/static/25411174200725319627/

程序员面试题精选 100 题 (06) －判断整数序列是不是二元查找树的后序遍历结果

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

回 false 。

例如输入 5 、 7 、 6 、 9 、 11 、 10 、 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];

// the nodes in left sub-tree are less than the root

int i = 0;

for (; i < length - 1; ++ i)

http://zhedahht.blog.163.com/blog/static/2541117420072915131422/

程序员面试题精选 100 题 (08) －求 1+2+...+n

题目：求 1+2+ … +n ，要求不能使用乘除法、 for 、 while 、 if 、 else 、 switch 、 case 等关键字以及条件判断语

句（ A?B:C ）。

分析：这道题没有多少实际意义，因为在软件开发中不会有这么变态的限制。但这道题却能有效地考查发

散思维能力，而发散思维能力能反映出对编程相关技术理解的深刻程度。

通常求 1+2+ … +n 除了用公式 n(n+1)/2 之外，无外乎循环和递归两种思路。由于已经明确限制 for 和 whil e

的使用，循环已经不能再用了。同样，递归函数也需要用 if 语句或者条件判断语句来判断是继续递归下去

还是终止递归，但现在题目已经不允许使用这两种语句了。

我们仍然围绕循环做文章。循环只是让相同的代码执行 n 遍而已，我们完全可以不用 for 和 while 达到这个

效果。比如定义一个类，我们 new 一含有 n 个这种类型元素的数组，那么该类的构造函数将确定会被调用

n 次。我们可以将需要执行的代码放到构造函数里。如下代码正是基于这个思路：

class Temp

{

public :

Temp() { ++ N; Sum += N; }

static void Reset() { N = 0; Sum = 0; }

static int GetSum() { return Sum; }

private :

static int N;

static int Sum;

};

int Temp::N = 0;

int Temp::Sum = 0;

int solution1_Sum( int n)

{

Temp::Reset();

Temp *a = new Temp[n];

delete []a;

a = 0;

return Temp::GetSum();

}

我们同样也可以围绕递归做文章。既然不能判断是不是应该终止递归，我们不妨定义两个函数。一个函数

充当递归函数的角色，另一个函数处理终止递归的情况，我们需要做的就是在两个函数里二选一。从二选

一我们很自然的想到布尔变量，比如 ture （ 1 ）的时候调用第一个函数， false （ 0 ）的时候调用第二个函数

。

那现在的问题是如和把数值变量 n 转换成布尔值。如果对 n 连续做两次反运算，即 !!n ，那么非零的 n 转换

剩余185页未读，继续阅读

goO___Oog

粉丝: 0
资源: 11

程序员面试题精选100题详解：微软Google技术挑战

程序员面试题精选100题完整版.pdf，这是一份不错的文件

程序员面试题精选100题完整版

程序员面试题精选100题-何海涛

各大公司程序员面试题集锦（何海涛版pdf）

程序员面试100题（何海涛）

程序员面试题精选100题：微软、Google等公司面试题大全

程序员面试题精选100题详解：数据结构与算法实战

程序员面试题精选：100道技术难题解析

程序员面试题精选：技巧揭秘与实战解析

程序员面试必备：何海涛版100道经典面试题

最新资源