题目一：求斐波那契数列的第 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) 时间，才能找到栈中最大或者最小的元素。
• 考查应聘者写与模板相关的代码的能力。

给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点出了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。

考虑不同位置的节点的下一个节点：

1. 节点有右子树：从右子节点出发一直沿着左指针向下遍历，就能找到下一个节点；
2. 节点没有右子树：
   • 节点是它父节点的左子节点：下一个节点就是它的父节点；
   • 节点是它父节点的右子节点：沿着父指针一直向上遍历，直到找到一个是它父节点的左子节点的节点，这个节点的父节点就是我们要找的下一个节点。反之，则没有下一个节点；

Source Code