查看: 3295| 回复: 19
跳转到指定楼层
上一主题 下一主题
收起左侧

[其他] Google 电面 9 月 21 号

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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大米 +9 收起 理由
西风吹草 + 5 谢谢你的介绍!
lizlingng + 1 感谢分享!
lchen77 + 3 感谢分享!

查看全部评分


上一篇:LEETCODE一天刷几题正常啊?
下一篇:Salesforce Certification

本帖被以下淘专辑推荐:

推荐
whcnbin 2015-9-23 08:47:34 | 只看该作者
全局:
印度阿三私心很重,如果你也是一位阿三,那结果可能是问你:请预测下昨天的天气
回复

使用道具 举报

推荐
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[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);
    }
回复

使用道具 举报

推荐
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个数就行了。
回复

使用道具 举报

🔗
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么?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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