头条二面

介绍自己

说一说项目

重点介绍一下难点

手撕代码

• [432123] ,[4321],[1234] 输入这样一个阶梯式的数组，如何找到最小值？

  因为普通遍历算法是暴力解法，对于这样一个部分有序，阶梯式的数组肯定不是最高效的。 二分查找，插值查找，斐波那契查找都是需要数组有序，因此可以尝试这三种算法。 分块查找适用于较大数据量，哈希查找和桶查找差不多， 其实对于数据量较小比较复杂，空间开销比较大 最后用二分查找实现了，即mid值需要小于前者和小于后者， 如果mid-1>mid>mid+1 则往右半区找， 如果mid-1<mid<mid+1则往左半区找， 同时注意边界值，即mid-1<0 和mid+1>=arr.length的情况 这道题完全做出来了，并且通过了所有测试用例

• 1->2->3->4->5->6这样一个链表，如何排序成1->6->2->5->3->4这种结构，注意是分别有序的，说一说思路

  这道题没让编程就是说思路，注意观察也是部分有序。 1.两个队列实现，快慢指针找到中点然后，然后对后半部分进行反转 2.反转链表，然后类似于二路归并的感觉，只不过不需要互相比较，逐个结点接起来。 3.一个队列一个栈实现，进行反转。