笔试面试总结

13 September 2014

##美团笔试题

美团这次笔试有8道基本题，都是算法，给的时间是90分钟，有的题目需要想的点还是很多的。90分钟想思路和写代码是很紧张的。先记录部分题目如下：

在平面坐标上有n个点，求两两间的斜率最大值(假设任意两点斜率都是存在的)。

解：这题的思路是先将n个点按x坐标排序，然后计算两两间斜率，斜率的最大值肯定在其中出现过。为什么是两两之间呢。见下图，1、3两点连成的线斜率不可能是最大的。
有一个先递增后递减的数组，查找里面的最大值。如[1,2,3,4,5,4,2,1]。

解：二分变种。逻辑过程要清楚，如果找到一个点比两边都大，那说明已经找到了，结束。否则，往大的那边搜。不可能比两边都小。
求数组中绝对值最接近0的连续子数组。如[-1,0,1,2,-2]中，[-1,0,-1],[2,-2],[-1,0,1,2,-2]都是满足条件的子数组。

解：之前经常遇到的题是求和值最大的连续子数组，被思维定式了。

这题先求出前缀和数组sum[i]表示0-i项的和。然后附上下标信息对sum进行排序，两两计算，最接近0的子数组肯定在其中出现。(因为sum[i]-sum[j] 即是 j-i项连续子数组的和)。
包含特定的字符集的最短子串。如字符集是abc，text ="cacdbe",那么text中包含abc的最短子串是acdb。

解:这次暂时只想到一个麻烦的标记方法，时间复杂度是O(n)。待定，看能不能找到优雅的方法。 16日补：原来这题我之前是做过的，在LeetCode上，看了源码，实在麻烦的，方法还是两个指针走。

##搜狗面试

搜狗我是现场投了一个简历，然后就被内推免笔试去面了。没问什么刁难的算法。问的都是些具体的技术场景，让你想解决方案。面试围绕着一个Hash表的各类问题开始展开，具体过程太过惨烈，不再复述。

##阿里面试

大数据

笔试面试总结 记录经历的笔试面试题