百度垂直搜索部门实习面经

之前面了一次百度的实习，并且拿到offer，下面是实习过程中出现的题目，希望给同样投百度的同学一个参考。

百度垂直搜索部门实习面经

一面

1.      背景问题：自我介绍，问有关项目经历，描述以前做的东西

语言：

1.      C++ 关于vtable，是类对应vtable还是对象对应vtable（类）

2.      构造函数能否是虚函数(我说的比较含糊：个人认为从语言设计角度来讲不需要）

3.      malloc和new的差别

4.      析构函数不是虚函数的情况给个例子，问会发生神马

5.      在一个函数new了一个以后，没有delete，用什么技术来解决此处发生的内存泄露

6.      cpp编译成二进制文件的过程

7.      delete数组有什么不同，如果用deletep来delete数组，会有什么问题

OS：

new分配内存的过程，应该回答出一种内存管理方式

如果有多个程序同时申请内存，这个时候操作系统如何做到互斥访问

海量数据查询问题：

用户的输入常常会有错误，错误主要分三种情况，多一个，少一个，写错一个。

假如我们在数据库中存储了所有正确的输入，利用什么技术，例如输入一个错误query，来得到所有正确的query。

这个题目是hr提示我的，其实我也没有什么思路
想到的是hash表
对正确的数据存储的时候做如下处理：
例如我们要存储abcdef，首先存储abcdef状态为1，说明是争取的字符串。
把这个字符串的每个位置去掉一个分别存储，用来以后做用户少输入一个的检测。
则里面有bcdef acdef....

在检索的时候，假如目标串是A, 检索A，如果检索到的标记是1，说明输入的是正确的。 如果检索到的字符串标记为0，则说明用户把争取的少输入了一个。现在把A的每个位置去掉一个字符。如果检索到的标记为1，说明用户多输入一个，如果检索到的标记为0，说明用户输入错一个。

二面：

1.      讲项目经历，大概一共聊了15分钟吧

2.      一个寺庙有N个台阶，一个人站在下面，他要去到第M个台阶，假设他只有2个方案可以选择 1. 向上走3台阶 2. 向下走2个台阶。请问他到达第M个台阶最少要走多少步。给出核心算法并分析复杂度

(dp可以解决）

（后来顺便扯到如果台阶个数特别多，应该如何分配dp[N], 然后又扯到局部变量，全局静态变量，和堆变量的差别，包括生命周期，分配上的大小限制，读写速度，什么情况使用哪种变量）

3.      简化题目为：有两个数组，A[N], B[M]，代表两个集合。

3.1现在求出集合的交集，给出算法的复杂度 

3.2 如果两个集合都已经排好序，如何求出交集