1、

1.1 10万份数据，分成10份，每份1万个

1.2 替换字符串中的空格

1.3 查找邮件地址

 

2、

2.1 数组中和最大的子序列

2.2 数组中个数超过一半的数字

2.3 全排列

2.4 1000瓶水，1个有毒

 

3、

3.1 计算1+2+3+……+N

3.2 删除链表中倒数第K个点

3.3 判断两个链表是否相交

3.4 求数组中最大最小值

3.5 用COPY-ON-WRITE写STRING类

 

---------------------------------------------------------------------------------------

 

1、C++ 基础知识

类的内存布局，vtable的原理，虚继承的时候类内存布局，多继承的时候类的布局。另外一个重点在内存部分，只要跟内存相关的都喜欢考，对指针的理解，allocator的实现，vector内存分配的策略，各种智能指针实现原理及其使用注意事项, rule of three， RAII，内存泄漏的原油时候如何调试等等。较多涉及指针、多态（虚函数表、内存 layout等）、作用域、内存的管理等。

vector增长模式、虚函数表、函数指针复杂形式的识别、HASH的设计

从最基础的c++基础语法知识以及stl原理，到初级的多态的实现，再到高级的内存模型，c++11的新特性，最后到模板编程，

算法、多线程、SOCKET、内存管理

以C++的虚函数为例。了解多态么？它是怎么实现的？什么时候应该使用它？在语言层面，虚函数是怎样实现的？为什么还要区分虚函数和普通函数，都成虚函数不好么？虚表里存储的是什么？如果基类定义先声明了f函数后声明了g函数，子类定义会反过来（真正面试的时候会有样例代码给出），那么虚表里第一项是什么？如果有多继承，虚表内会怎样？等等。。。这只是个大体思路，关键是看求职者的现场反应能力和链接能力，比如：第一题，如果提到静态多态，并且简单询问后确认懂得什么是静态多态，则有额外加分。第二题，提到和其他语言的对比（如java oc python 等），有额外加分。第四题，关键不在于答案，而在于回答的思路。如果在回答出大体原理之后加以说明这东西是undefined，不应该依赖于这个结果，有额外加分。第五题，如果一开始求职者不太了解这个事情，但是通过我简单的提示，能够沿着这个思路走下去，无论对错，均有额外加分。如果在面试中会询问到了求职者之前没有思考过的问题，我会给出适当的提示，逼迫其现场思考。如果中间被求职者带跑了，比如问第一题的时候扯到模板元编程了，我的态度就是随着他跑，在他自己最擅长的领域才能看出他的思路究竟是怎样的。总之，尽量通过方方面面探知求职人员对技术核心思想的把握能力，如果在面试之前他就考虑的很透彻，这是上上之选（原因是其会自己沿着正确的方向独立思考），如果在面试中可以现场考虑出大概，这是上之选（原因是其逻辑思维还不错）。思维方式很重要，某种程度上，这东西决定一个人的命运。

2、算法和数据结构

算法数据结构是必然要考察的重点。都说这是程序员安身立命之根本，一般面试第一关遇到的都是面试官说“我们来写个算法吧”，我遇到的算法基本上要么是位运算的，要么是DP和贪心，有一些查找和排序（包括topK）算法，很多leetcode和剑指offer上面的原题或者变种题，难度中等吧。数据结构的话比较简单，最难的也就考过字典树，好像大家都遵循着够用就行的原则，反正就是队列，树，图，这几种，主要考察的是各种操作的时间复杂度，应用场景怎么选择等等。数据结构主要关注哈希、优先级队列等，算法则是字符串处理、简单的 DFS、BFS、动态规划。

 

3、操作系统知识

进程、线程、协程、锁的使用、消息队列、共享内存、网络协议、epoll、select等。顺便会考察一些处理问题的基本思路，比如通过哈希来划分、通过队列来序列化操作等等。

其次要考察的是语言无关的基础知识，包括操作系统概念相关知识，多线程编程，网络编程，TCP相关网络知识，编译原理相关基础知识，最后要考察的是存储

 

4、和应聘者背景经历有关的知识

5、开放式问题 

讲讲一个程序从源代码编写一直到程序执行整个生命周期的过程

6、实践

用C++写一个有理数类，class Rational，实现基本的加减乘除和输入输出操作。别看这么小小的一个问题，居然可以考察到非常之多的地方，犹如闯关游戏一般，直到把这个面试者推向极限。完全不知所云的，甚至有说忘了有理数是啥的，两个整数之比定义为有理数，第一个叫做分子，第二个叫做分母。如果搞不清楚的怎么做的，我会给一个main函数的示例（见下面的代码），告诉他“面向接口编程，不要面向实现编程”。我发现有经验的人，会问我接口或者对象的行为是什么样的。能搞清楚问题，首先让他写出类的声明，然后就可以问，哪些是public，哪些是private的，什么是运算符重载。为何传递参数要写 const Rational&。继续问，构造函数，析构函数，拷贝构造函数，operator= 是怎么回事，相关知识云云，构造函数是不是前面要加 explicit 修饰。继续问 istream和ostream的重载怎么写，friend 函数是怎么回事。让面试者写代码，尽可能完整地实现这个类的成员函数，中间观察编程习惯，代码风格等等有理数分母不能为0，看看面试者是不是够仔细，还有对C++的异常控制是否有了解。包括数字过大的时候，整数溢出了是否有考虑。1/3+1/3+1/3输出应该是1，所以分子分母要约分，求最大公约数这个点想到。如果有负数，最大公约数怎么求？istream输入的情况可能会很多，涉及到字符串的解析，"3.5","1/3", "-1/5", "-0.3"，看看面试者能正确处理多少种情况？顺便问一下测试方面的问题。有理数的分子分母可能会很大，是不是可以考虑模板化，写成Rational<T>，然后可以有个Bigint的类来实现 typedef Rational<Bigint> HighPrecisionRational;//我期望看到的解答

 

 

1 #include 
             
               2  3 class Rational 4 { 5 public: 6     Rational(); 7     Rational(int x); 8     Rational(int x, int y); 9     Rational(const Rational& r);10     const Rational& operator=(int x);11     const Rational& operator=(const Rational& r);12     virtual ~Rational();13 14     bool operator== (const Rational& other) const;15 16     friend const Rational operator+ (const Rational& r1, const Rational& r2);17     friend const Rational operator- (const Rational& r1, const Rational& r2);18     friend const Rational operator* (const Rational& r1, const Rational& r2);19     friend const Rational operator/ (const Rational& r1, const Rational& r2);20     friend std::ostream& operator<< (std::ostream&, const Rational& r);21     friend std::istream& operator >> (std::istream&, Rational& r);22 23 private:24     static int gcd(int p, int q);25     int num; //numerator26     int div; //divisor27 };28 29 30 int main(int argc, char* argv[])31 {32     Rational a(1, 3);33     Rational b = 3;34     b = a;35     Rational c(a + b + Rational(1, 3));36     std::cout << "a=" << a << std::endl;37     std::cout << "b=" << b << std::endl;38     std::cout << "c=" << c << std::endl;39 40     std::cout << "Please input a Rational number like 13/15" << std::endl;41     Rational d;42     std::cin >> d;43     std::cout << "value d+1=" << d + 1 << std::endl;44     45     return 0;46 }
             

 

 

 

面试者能闯到最后一关的，我已经比较满意了。整个面试的过程中围绕着一个功能的实现反复交流和改进，我们的谈话已经涉及到了C++、字符串、算法、数学、代码风格、软件工程、测试的很多方面的知识了；同时对面试者的表达能力，沟通能力，性格方面也有所了解了。

 

finally. 我会给一个杀手级问题，这里分子分母约分用到了gcd，请问时间复杂度是多少？啊哈，这里要请出Knuth爷爷的《计算机程序设计艺术》啦！

 

我补充说明一下

1. 确实如他所说的，先给出operator+=，然后再去实现非友元的operator+，这样是能减少代码冗余的；如果只是要求实现加减乘除操作，用友元operator也没有问题。

2. 如果只是考虑在控制台输入输出，iostream就能满足需求了; 如果更往深了讨论，比如涉及到字符串解析(sstream)，文件的读写(fstream)，这个时候就需要重载参数为basic_streamTemplate<typename charT>

basic_stream<charT>& operator<< (basic_stream<charT>& os, const Rational& r);

Template<typename charT>

basic_stream<charT>& operator>> (basic_stream<charT>& os, const Rational& r);

3. std::complex是复数，而Rational是有理数，实现细节上还是多有不同的。如果是要求面试者实现一个complex的话，我曾要求他实现出复数的乘方和开方运算。

4. operator= 应该返回 const Rational&，已改正;

5. 为何不直接用系统默认合成的构造析构函数。Rational x; 的值是多少呢？我的习惯是初始化为0，而且不希望分母为0

6. 构造函数Rational::Rational(int x)，我认为是不应该声明为explicit的，因为我希望重载了operator+运算符之后，r+1, 1+r都能work。我们这里并不是要求应聘者是一名C++语法专家，更多的是希望在相互讨论的过程中，观察面试者思考问题的深度和全面性，以及应变能力。