6.8阿里云二面

声明：无保密协议

    这次面试的gg比较直接，上来就问了我做过的digO系统,问了下这个系统使用，想法，语义Web的一些问题，这个忽悠能力我还是有的。然后如何聚类的问题，之前我负责调查聚类算法的特点，因此还是了解点。聚类是我师兄实现的，我只是知道如何去做，基于什么想法，所以就简单的说了下想法，现在想起来忘了和他说不是我实现的了。。。不会说我不忽悠他吧，下次遇到类似情况记得说明。期间着重问了时间复杂度，这个我还是知道的。期间过程比较长，不赘述。
    完了就开始问如何找到第k个大小的数，貌似以前看过，但是感觉今天没有热身，面试没有感觉，一时没有太好解决办法，说最基本的是O(kn)，然后说了个k=2的时候的解决办法，貌似也不是很好，然后他又问了最好情况的复杂度，要具体数字。后来在老曹drizzlecrj的第 (前)k大数问题看到比较了这个题目的解法：

     所谓“第（前）k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第（前）k个数的问题。
解法1： 我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。
解法2： 利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)
解法3： 利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分S_a和S_b。S_a中 的元素大于等于X，S_b中元素小于X。这时有两种情况：
1. S_a中元素的个数小于k，则S_b中 的第k-|S_a|个元素即为第k大数；
2. S_a中元素的个数大于等于k，则返回S_a中 的第k大数。时间复杂度近似为O(n)
解法4： 二分[S_min,S_max]查找结果X，统计X在 数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)
解法5：用O(4*n)的方法对原数组 建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn)
解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆 顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)
解法7：利用hash保存数组中元素S_i出 现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

详细内容参考老曹blog。
    然后就是问我有什么问题，我就问了他们做的东西面向的用户，阿里云的氛围和文化，然后是对实习生的要求以及是否安排师傅等等。