戴尔开发工程师 面试经历

先是英文自我介绍，然后让我介绍一个做过的印象最深的项目，然后就问我这个项目是怎么设计的，遇到了什么困难怎么解决的，最后是两道算法题：（1）有0，1，2到99这100个正整数，中间丢失了一个，剩余的99个数打乱顺序放在一个数组里，问怎样找到丢失的那个数。他没有要求复杂度，结果我就没往深处想，直接说了一个时间空间复杂度都为O(n)的算法（瞬秒），他说ok，然后第二题（事后想想当时脑残了，能把空间复杂度优化到O(1)的，不过对方当时没问）（2）有一个有序的环形数列，从小到大排好了，比如：4，5，6，1，2，3，从第四个位置开始当成环形看，就是一个有序数列1，2，3，4，5，6。问题是在这个数列中找到给定的关键字。我想到了用二分找到这个环形的开头位置i，那么[0，i]，[i+1，n-1]就是有序的，再次做二分即可。对方说能想到lgn的复杂度很好，但是希望能够只要一次二分就完成。我又纠结了一会才想到，正要跟他细说，但是他说“我相信你已经知道怎么做了，等会把代码发给我”。