把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转，该数组的最小值为 1。

• 查找较为简单，不外乎顺序查找、二分查找、哈希表查找、二叉排序树查找。
• 遇到排序的数组（或者部分排序的数组），可以尝试用二分查找算法。
• 哈希表和二叉排序树查找的重点在于考查对应的数据结构，而不是算法：
  • 哈希表最主要的优点是能够在 O(1) 时间内查找某一元素（效率最高），缺点是需要额外的空间；
  • 二叉排序树对应的数据结构是二叉搜索树。
• 排序复杂一些，要求比较插入排序、冒泡排序、归并排序、快速排序等不同算法的优劣。
• 要求应聘者写出快速排序的代码：Partition 函数 + 递归。
  Read more »

题目一：求斐波那契数列的第 n 项。
写一个函数，输入 n，求 Fibonacci 数列的第 n 项，斐波那契数列的定义如下：

• 递归是在一个函数的内部调用这个函数自身；循环则是通过设置计算的初始值及终止条件，在一个范围内重复计算。
• 如果没有特别的要求，应聘者可以尽量多采用递归的方法编程，可能引起：调用栈溢出。
• 每一次函数调用，都需要在内存中分配空间以保存参数、返回地址、临时变量，而且往栈里压入数据和弹出数据都需要时间。

引子：小萝卜的例子

希望小萝卜具有自主运动能力。
定位和建图可以看成感知的内外之分：

• 一方面，要明白自身的状态（即位置）；
• 另一方面，也要了解外在的环境（即地图）。

一类传感器是携带于机器人本体上的，测到的通常都是一些间接的物理量而不是直接的位置数据，这种定位方案可适用于未知环境；
另一类是安装于环境中的，限制了机器人的使用范围。
当谈论视觉 SLAM时，主要是指如何用相机解决定位和建图问题。
相机：以一定速率拍摄周围的环境，形成一个连续的视频流。
按照工作方式的不同，可分为：单目相机（Monocular）、双目相机（Stereo）、深度相机（RGB-D）。

本书讲什么

SLAM 是 Simultaneous Localization And Mapping 的缩写，中文译作：同时定位与地图构建。
SLAM 的目的是解决定位与地图构建，希望实时地、在没有先验知识的情况下进行 SLAM。
我们眼中的花草树木、虫鱼鸟兽，在计算机中只是一个个由数字排列而成的矩阵。
与人工智能和机器学习所用的方式——概率学建模是不同的。
与 SLAM 相关的应用点：在许多地方，我们都希望知道自身的位置。
虽然 SLAM 的理论框架基本趋于稳定，但其编程实现仍然较为复杂。
我们会详细地介绍 SLAM 的理论背景、系统架构，以及各个模块的主流做法。
经典书籍：《概率机器人》（Probabilistic robotics）、《计算机视觉中的多视图几何》（Multiple View Geometry in Computer Vision）、《机器人学中的状态估计》（State Estimation for Robotics: A Matrix-Lie-Group Approach）

• 目的在于介绍基础理论，SLAM 只是其应用之一；
• 内容偏重于数学理论，基本不涉及编程实现。

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead，分别完成在队列尾部插入节点和在队列头部删除节点的功能。

1
2
3
4
5
6
7
8
9
10
11

template<typename T> class CQueue 
{
    public:
        CQueue(void);
        ~CQueue(void);
        void appendTail(const T& node);
        T deleteHead();
    private:
        stack<T> stack1;
        stack<T> stack2;
};

• 操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址、临时变量等。
• 需要 O(n) 时间，才能找到栈中最大或者最小的元素。
• 考查应聘者写与模板相关的代码的能力。