Google 电面 9 月 21 号

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

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

其实就是个pocket gems常规题目 Top K frequent elements.

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);
    }

前k个可能quick select比较好 k会无穷大是干嘛用的

gp89757 发表于 2015-9-23 22:38
前k个可能quick select比较好 k会无穷大是干嘛用的

我估计“K无穷大”的意思是：“不能使用O(f(K))的额外空间”，也就是只能使用O(1)空间。可能是为了断掉楼主想的“用比较排序法”的念头。

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

罗总罗总，把三哥问的题目再稍微说详细一点？
他怎么从kth largest给你带到bucket sort这条沟里的……

lll_2013 发表于 2015-9-26 23:12
楼主，能问问你是面new grad职位还是experienced职位嘛？我都担心自己连面试机会也没有。。。

New grad的职位，一般google投了就会有面试

感觉面试官就是想引导LZ想一个O(n)时间复杂度和O(1)空间复杂度的算法。

hkc593 发表于 2015-10-11 13:09
感觉面试官就是想引导LZ想一个O(n)时间复杂度和O(1)空间复杂度的算法。

感觉这阿三bucket sort 有点误导啊。或者他给了其他约束条件。。。