一面

项目介绍，项目中遇到的困难

1.说一下STL中的vector的扩容机制

扩容方式：
1、倍数开辟二倍的内存
2、旧的数据开辟到新内存
3、释放旧的内存
4、指向新内存

2. 了解哪些STL容器？

• vector-数组，list-链表，deque-分配中央控制器map(并非map容器)，map记录着一系列的固定长度的数组的地址.
• map-红黑树，unordered_map-哈希表。

3. 你刚才说了map和unordered_map，说一下他们查找的时间复杂度？

• map->采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:插入: O(logN);查找:O(logN);删除:O(logN)
• unordered_map->采用哈希表实现，不同操作的时间复杂度为:插入:O(1)查找看:O(1);删除:O(1)。

4. 刚才有说了deque，那deque在头尾插入、删除和访问的时间复杂度呢？

deque的push_back, push_front, pop_back, pop_front操作时间复杂度为O(1);访问O(1).

5. 数组和链表区别.

• 数组的存储区间是连续的，查询简单，增加和删除困难.
• 链表是一种物理存储单元上非连续、非顺序的存储结构,查询相对于数组困难，增加和删除容易。

6.平时写算法题多不？

7. STL项目中用哪个比较多？

刷题的时候vector和stack用的多......

8.那就用stack实现一个队列吧

相关题目(用栈实现队列)，这里只讲了思路就好。

9. 手撕代码：区间合并， [3,5],[4,6],[7,9]-> [3,6],[7,9]

广告一波->算法基础课第一讲（PS：Y总太强了） 区间合并。
先说思路：
1.左端点排序。
2.然后比较是否有相交的区间，然后再进行合并。具体可以去看基础课讲的。

然后分析了一下时间复杂度，因为用到了排序，时间复杂度为O(NlogN).然后面试官说有没有时间复杂度更小的方法，说用可以用空间来换时间，这个我就不太懂了。zzz