美团

一面

1. 主要问实习和硕士期间的项目。（40min）

   • 项目实现

   • 项目挑战

   • 对于故障的处理

2. 八股：(10min)

   • 对于C++11是否熟悉。

   • 智能指针，auto_ptr的问题。

   • 哈希表，如何解决哈希冲突：只说了一致性哈希和链表做法。

3. 做题：(15min)

   •     合并K个有序链表，

     • 一开始用堆做的，问了下priority_queue用的什么排序（堆排序），对于这样用堆排序的复杂度。

     • 让用别的方法去做，想到用归并排序去做。

知识整理：

1. auto_ptr的问题。:

   auto_ptr在构造时获取对某个对象的所有权，在析构时释放该对象。

   • 若是两个auto_ptr都指向同一个对象，那么在析构的时候肯定会都试图删除该对象，两次删除同一对象在C++标准中是未定义的。（会导致对同一块内存析构多次）

   • auto_ptr无论被拷贝还是被复制，源对象都将失去对其资源的所有权，复制一个auto_ptr时，它所指向的对象的所有权被移交到复制的对象，而他本身被置为NULL。（因此不要创建包含auto_ptr的容器）

1. 如何解决哈希冲突

一个问题（自己想的）：对于哈希冲突，大家都在考虑如何解决存储时的哈希冲突，那么在查找的时候，如何判断计算出来的key就是最终的key呢？（这部分有没有大佬能帮忙答个疑）

答：网上对于这部分的解释基本没有，都是讨论存储问题，个人感觉其实哈希算法算出来的key其实就是最终key，只是在产生key的过程中已经考虑到了哈希冲突，也就是说可能按照最初哈希算出来的key对应的存储区并没有数据，但是考虑到哈希冲突，依然会进行下一步的计算得到最终的key。就比如假设哈希算法为取十进制数的最后一位座位key，那么22和32的key都为2，那么对于2这个存储区，即便先进行存储的数据为32，但是算法也会考虑到22和2的存在，因此，即便该存储区为空，依旧不会存在里面。（很好的解释了开放地址法和链地址法的初始问题，但是对于再散列选取的伪随机数序列还是有点问题）

1. 开放地址法：

这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

 Hi=（H（key）+di）% m   i=1，2，…，n

再散列（di）选取主要有三种：

1.线性探测再散列 2.二次探测再散列 3.伪随机数序列

1. 链地址法

   拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数 组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。

2. 再哈希法：

同时构造多个不同的哈希函数，在产生冲突的时候选择其他哈希。

1. 建立一个公共溢出区

将哈希表分为基础表和溢出表两部分，凡是和基础表发生冲突的元素，一律填入溢出表。