Google 电面 9 月 21 号

一个印度哥哥面试的，总共45分钟，上来聊了15分钟的简历上的项目。然后开始考算法，打开google doc，面试官给了一道 leetcode 原题，Find the Kth largest number. 然后我说先sort 一遍，输出第k个最大的。面试官问你要怎么sort，我说用quick sort，面试官想要提升时间复杂度，我说可以用merge sort，面试官还说要提升，并且K 会无穷大，然后让求前k个最大的数，问hint，面试官说写个桶排序，然而这个我并不太会实现，硬着头皮写代码，刚有了完整思路还没写完时间已到，最后说了下思路，然后结束。整个过程三哥态度明显很不好，感觉已挂。

印度阿三私心很重，如果你也是一位阿三，那结果可能是问你：请预测下昨天的天气

superbinhugo 发表于 2015-9-23 05:19
这....C++各种奇技淫巧OTZ，复杂度是O(N)的话，linear search一遍，然后要怎么留住最大的前K个呢？用heap ...

C++库用的应该就是quick select， O（N）是只平均复杂度，算法导论上有证明，下面是我leetcode上的实现， 供参考：
int findKthLargest(vector<int>& nums, int k) {
        const int size_n = nums.size();
        int left = 0, right = size_n - 1;
        while (left <= right) {
            int i = left, j = right;
            int pivot = nums[left];
            while (i <= j) {
                while (i <= j && nums[i] >= pivot) i++;
                while (i <= j && nums[j] < pivot) j--;
                if (i < j) swap(nums[i++], nums[j--]);
            }
            swap(nums[left], nums[j]);
            if (j == k - 1) return nums[j];
            if (j > k - 1)  right = j - 1;
            else left = j + 1;
        }
        assert(false);
    }

JimLuo 发表于 2015-9-23 05:36
quick select是可以的，但是三哥面试官貌似要引导我写出桶排序，随后把题改成返回前K个最大的，还给出了 ...

如果数组里的数的范围只有0~100的话，counting sort就可以么。开一个长为101的数组M，扫第一遍时在M中记录下每个数字出现的次数。扫完以后倒着从M中数出K个数就行了。

应该不用quick sort吧  quick select就可以了把 quick select O(n)复杂度

楼主的回答还是不错的

这道题比较经典的做法是不是应该是  quick select，平均 时间复杂度 O(n), 空间复杂 O（1）

其实C++有个函数叫nth_element, 时间 复杂度是O(N)

Linzertorte 发表于 2015-9-23 02:40
其实C++有个函数叫nth_element, 时间 复杂度是O(N)

这....C++各种奇技淫巧OTZ，复杂度是O(N)的话，linear search一遍，然后要怎么留住最大的前K个呢？用heap想了想似乎不行的样子@@

josealin 发表于 2015-9-23 01:17
应该不用quick sort吧  quick select就可以了把 quick select O(n)复杂度

quick select是可以的，但是三哥面试官貌似要引导我写出桶排序，随后把题改成返回前K个最大的，还给出了数组数组在0~100范围内

superbinhugo 发表于 2015-9-23 05:19
这....C++各种奇技淫巧OTZ，复杂度是O(N)的话，linear search一遍，然后要怎么留住最大的前K个呢？用heap ...

然后你并不知道 。。。前面k就是是最小的k个。。后面就是最大的n-k-1个。。
你想想quick sort的 按pivot，小的在pivot左边，大一点的在pivot 右边

kith largest number不是用quick sort中的partition么？