输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入前序遍历序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6}，则重建二叉树并输出它的头节点。二叉树节点的定义如下：

1
2
3
4
5
6

struct BinaryTreeNode 
{
    int m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
}

• 由于树的操作会涉及大量的指针，因此与树有关的面试题都不太容易。
• 3 种遍历都有递归和循环两种不同的实现方法，递归实现都比循环实现要简洁很多。
• 我们可以平均在 O(logn) 的时间内，根据数值在二叉搜索树中找到一个节点。
• 需要快速找到最大值或最小值的问题都可以用堆来解决。
• 红黑树：把树中的节点定义为红、黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。STL 中，set、multiset、map、mutimap 等数据结构都是基于红黑树实现的。
• 考查应聘者分析复杂问题的能力。把构建二叉树的大问题分解成构建左、右子树的两个小问题。确定左、右子树节点的数量，用递归的方法去完成。
  Read more »

输入一个链表的头节点，从尾到头反过来打印出每个节点的值。链表节点定义如下：

1
2
3
4
5

struct ListNode 
{
    int m_mKey;
    ListNode *m_pNext;
}

• 内存分配不是在创建链表时一次性完成的，由于没有闲置的内存，链表的空间效率比数组高。
• 如果我们打算修改输入的数据，最好先问面试官是不是允许修改。
• 典型的后进先出，可以用栈实现这种顺序。递归本质上就是一个栈结构，但有可能导致函数调用栈溢出，显然用栈基于循环实现的代码的鲁棒性要好一些。
• 考查对循环、递归、栈 3 个相互关联的概念的理解。

Source Code

请实现一个函数，把字符串中的每个空格替换成“20%”。例如，输入“We are happy.”，则输出“We%20are%20happy.”。

• URL参数中含有特殊字符，如空格、”#”等。会导致服务器端无法获得正确的参数值，转换规则：”%”后面跟上 ASCII 码的两位十六进制的表示。
• 从前往后复制每个字符则需要重复移动数字多次（O(n^2)），从后往前复制，这样就能减少移动的次数，从而提高效率（O(n)）。能清晰地分析出两种不同方法的时间效率各是多少。
• 画一两个示意图解释自己的思路（两个指针），既能帮助我们厘清思路，也能使我们和面试官的交流变得更加高效。
  Read more »

在一个长度为 n+1 的数组里的所有数字都在 1～n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 8 的数组 [2, 3, 5, 4, 3, 2, 6, 7]，那么对应的输出是重复的数字 2 或者 3。

• 可以创建一个长度为 n+1 的辅助数组，该方案需要 O(n) 的辅助空间。
• 某范围里数字的个数对解决这个问题很重要。
• 函数 countRange 将被调用 O(logn) 次，每次需要 O(n) 的时间，总时间复杂度是 O(nlogn)，相当于以时间换空间。
• 交流的重要性：面试官提出不同的功能要求或者性能要求，我们最终选取的算法也将不同。
• 能快速、正确地实现二分查找算法的代码。

Source Code

在一个长度为 n 的数组里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为 7 的数组 [2, 3, 1, 0, 2, 5, 3]，那么对应的输出是重复的数字 2 或者 3。

• 排序一个长度为 n 的数组需要 O(nlogn) 的时间。
• 利用哈希表可以实现时间复杂度为 O(n) 的算法，但代价是一个空间复杂度为 O(n) 的哈希表。
• 重复数字通过指针，传递给函数的调用者。
• 尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，故时间复杂度是 O(n)。
• 一维数组在内存中占据连续的空间，可以根据下标定位对应的元素。
• 问题比较复杂时，关键是能否通过具体的例子找出其中的规律。

Source Code