一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1308|回复: 19
收起左侧

[其他] Google 电面 9 月 21 号

[复制链接] |试试Instant~ |关注本帖
JimLuo 发表于 2015-9-23 00:25:09 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 JimLuo 于 2015-9-23 08:08 编辑

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

评分

3

查看全部评分

本帖被以下淘专辑推荐:

whcnbin 发表于 2015-9-23 08:47:34 | 显示全部楼层
印度阿三私心很重,如果你也是一位阿三,那结果可能是问你:请预测下昨天的天气
回复 支持 1 反对 0

使用道具 举报

josealin 发表于 2015-9-23 01:17:20 | 显示全部楼层
应该不用quick sort吧  quick select就可以了把 quick select O(n)复杂度
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-9-23 01:22:51 | 显示全部楼层
楼主的回答还是不错的
回复 支持 反对

使用道具 举报

lchen77 发表于 2015-9-23 02:32:35 | 显示全部楼层
这道题比较经典的做法是不是应该是  quick select,平均 时间复杂度 O(n), 空间复杂 O(1)
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-23 02:40:43 | 显示全部楼层
其实C++有个函数叫nth_element, 时间 复杂度是O(N)
回复 支持 反对

使用道具 举报

superbinhugo 发表于 2015-9-23 05:19:46 | 显示全部楼层
Linzertorte 发表于 2015-9-23 02:40
其实C++有个函数叫nth_element, 时间 复杂度是O(N)

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

使用道具 举报

 楼主| JimLuo 发表于 2015-9-23 05:36:56 | 显示全部楼层
josealin 发表于 2015-9-23 01:17
应该不用quick sort吧  quick select就可以了把 quick select O(n)复杂度

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

使用道具 举报

Linzertorte 发表于 2015-9-23 06:41:08 | 显示全部楼层
superbinhugo 发表于 2015-9-23 05:19
这....C++各种奇技淫巧OTZ,复杂度是O(N)的话,linear search一遍,然后要怎么留住最大的前K个呢?用heap ...

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

使用道具 举报

xnature 发表于 2015-9-23 08:33:25 | 显示全部楼层
kith largest number不是用quick sort中的partition么?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-23 09:58:26 | 显示全部楼层
JimLuo 发表于 2015-9-23 05:36
quick select是可以的,但是三哥面试官貌似要引导我写出桶排序,随后把题改成返回前K个最大的,还给出了 ...

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

使用道具 举报

kelvinzhong 发表于 2015-9-23 10:16:04 | 显示全部楼层
其实就是个pocket gems常规题目 Top K frequent elements.
回复 支持 反对

使用道具 举报

lchen77 发表于 2015-9-23 21:31:10 | 显示全部楼层
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 >= 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);
    }
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-23 22:38:50 | 显示全部楼层
前k个可能quick select比较好 k会无穷大是干嘛用的
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-23 23:31:54 | 显示全部楼层
flexwang 发表于 2015-9-23 22:38
前k个可能quick select比较好 k会无穷大是干嘛用的

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

使用道具 举报

lizlingng 发表于 2015-9-24 01:45:16 | 显示全部楼层
JimLuo 发表于 2015-9-23 05:36
quick select是可以的,但是三哥面试官貌似要引导我写出桶排序,随后把题改成返回前K个最大的,还给出了 ...

罗总罗总,把三哥问的题目再稍微说详细一点?
他怎么从kth largest给你带到bucket sort这条沟里的……
回复 支持 反对

使用道具 举报

lll_2013 发表于 2015-9-26 23:12:03 | 显示全部楼层
楼主,能问问你是面new grad职位还是experienced职位嘛?我都担心自己连面试机会也没有。。。
回复 支持 反对

使用道具 举报

 楼主| JimLuo 发表于 2015-9-27 03:29:10 | 显示全部楼层
lll_2013 发表于 2015-9-26 23:12
楼主,能问问你是面new grad职位还是experienced职位嘛?我都担心自己连面试机会也没有。。。

New grad的职位,一般google投了就会有面试
回复 支持 反对

使用道具 举报

hkc593 发表于 2015-10-11 13:09:38 | 显示全部楼层
感觉面试官就是想引导LZ想一个O(n)时间复杂度和O(1)空间复杂度的算法。
回复 支持 反对

使用道具 举报

plutoman 发表于 2015-10-17 14:48:18 | 显示全部楼层
hkc593 发表于 2015-10-11 13:09
感觉面试官就是想引导LZ想一个O(n)时间复杂度和O(1)空间复杂度的算法。

感觉这阿三bucket sort 有点误导啊。或者他给了其他约束条件。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 17:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表