头条3面面经

1. 介绍你的项目

2. 你知道stl的vector是怎么实现的吗，分析一下它扩容时的复杂度，证明均摊到每个操作是O1

3. 树的中序遍历不用递归，我先说了一个标准动作stack+visit（记录出栈次数），面试官说不要用其他数据结构，我又想了一个双栈，面试官说只用一个栈也可以，就没想出来

4. 给定一个数组，求两数和最大，要求两个数至少隔k个元素，dp了一下最大值

5. 你有什么问题

感觉比1、2面要简单是怎么回事tat 第3个问题没想出来也没有进一步提示了，不做到最优就是凉凉么orz 求求字节收了我