一亩三分地论坛

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

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

热乎乎的 Uber 电面 fulltime

[复制链接] |试试Instant~ |关注本帖
lcl3356897 发表于 2015-10-29 05:58:25 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚的Uber店面,太挫了。。
. from: 1point3acres.com/bbs
题目
You are given a collection of contestants and their scores, return the medalists and their scores

大意就是有一堆参赛者还有他们的分数,输出得奖牌的,就是前三名. more info on 1point3acres.com

我用PriorityQueue写的,自己写了个class Plaeyer来表示参赛者和分数, 然后写Comparator排序
. more info on 1point3acres.com
一开始是大顶堆,把所有的参赛者都放入堆里边,然后输出前3个, Time 是 O(nlgn), Space 是 O(n)

然后建立了大小为3的小顶堆, 保存最好的3个  Time是O(nlg3), Space是O(3).鐣欏璁哄潧-涓浜-涓夊垎鍦

然后Interviewer问有没有个方法的average case是O(n) 我就懵了。。。就没答出来。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
大概就这样.鏈枃鍘熷垱鑷1point3acres璁哄潧

跪求RP
. more info on 1point3acres.com


补充内容 (2015-10-29 07:14):
对了忘说了。。
在建立了大小为3的小顶堆之后,面试官问我如果要前k个怎么办,我说那就弄个大小为k的小顶堆。. from: 1point3acres.com/bbs
然后面试官问,有没有 O(n)的解法

评分

2

查看全部评分

sqszsqsz 发表于 2015-10-29 06:17:10 | 显示全部楼层
Stackoverflow上介绍了蠢办法  O(n)

int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
int max3 = Integer.MIN_VALUE; // assuming integer elements in the array
. more info on 1point3acres.com
for (int i = 0; i < theArray.length; i++) {
    if (theArray[i] > max1) {
        max3 = max2;. visit 1point3acres.com for more.
        max2 = max1;
        max1 = theArray[i];
    } else if (theArray[i] > max2) {. more info on 1point3acres.com
        if (max1 == theArray[i]) {. from: 1point3acres.com/bbs
            // Neglect as already present in max1
        } else {. 鍥磋鎴戜滑@1point 3 acres
            max3 = max2;
            max2 = theArray[i];
        }
    } else if (theArray[i] > max3) {
        if (max1 == theArray[i] || max2 == theArray[i]) {-google 1point3acres
            // Neglect as already present in max1 OR max2
        } else {
            max3 = theArray[i];
        }
    }
}      
回复 支持 2 反对 0

使用道具 举报

snowwolf 发表于 2015-10-29 07:46:08 | 显示全部楼层
lcl3356897 发表于 2015-10-29 07:16
见补充,面试官应该是让找前k大的,O(n)时间

我当时都傻了。后来想了想,如果范围不大的话,可以试试 ...

average O(n)找前K个就是quickselect呀,只不过找出来的这k个不是按顺序出来的就是了. 1point 3acres 璁哄潧
-google 1point3acres
这里有详细说法
http://stackoverflow.com/questio ... heap-vs-quickselect
回复 支持 1 反对 0

使用道具 举报

snowwolf 发表于 2015-10-29 06:39:33 | 显示全部楼层
average O(n) 应该是想让你用 quick selection
回复 支持 反对

使用道具 举报

snowwolf 发表于 2015-10-29 06:43:18 | 显示全部楼层
sqszsqsz 发表于 2015-10-29 06:17
Stackoverflow上介绍了蠢办法  O(n).1point3acres缃

int max1 = Integer.MIN_VALUE;
.鏈枃鍘熷垱鑷1point3acres璁哄潧
你这个说白了是O(n*K),只不过对于这个例子K是3所以看上去是O(n)
回复 支持 反对

使用道具 举报

sqszsqsz 发表于 2015-10-29 06:46:15 | 显示全部楼层
snowwolf 发表于 2015-10-29 06:43
你这个说白了是O(n*K),只不过对于这个例子K是3所以看上去是O(n)

毕竟题目要求是找前三名,K是定死的就是O(n). 除非问找前n名的score的方法,天王老子也没法O(n)给sort出来
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-10-29 06:56:50 来自手机 | 显示全部楼层
喜欢天王老子这个词
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-10-29 07:15:40 | 显示全部楼层
snowwolf 发表于 2015-10-29 06:43. 1point3acres.com/bbs
你这个说白了是O(n*K),只不过对于这个例子K是3所以看上去是O(n)

见补充,面试官应该是让找前k大的,O(n)时间
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-10-29 07:16:20 | 显示全部楼层
sqszsqsz 发表于 2015-10-29 06:46. 鍥磋鎴戜滑@1point 3 acres
毕竟题目要求是找前三名,K是定死的就是O(n). 除非问找前n名的score的方法,天王老子也没法O(n)给sort出 ...

见补充,面试官应该是让找前k大的,O(n)时间. Waral 鍗氬鏈夋洿澶氭枃绔,

我当时都傻了。后来想了想,如果范围不大的话,可以试试桶排序,不过已经没机会了。。
回复 支持 反对

使用道具 举报

bill701 发表于 2015-10-29 07:34:39 | 显示全部楼层
求大神讲解o(n)解法啊
回复 支持 反对

使用道具 举报

woaibai 发表于 2015-10-29 07:46:39 | 显示全部楼层
如果知道分数范围的话,比如0-100, 可以用counting sort. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
lz这是哪个组的?
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-10-29 07:51:09 | 显示全部楼层
snowwolf 发表于 2015-10-29 07:46
average O(n)找前K个就是quickselect呀,只不过找出来的这k个不是按顺序出来的就是了

这里有详细说法.1point3acres缃
...

再补充下。。
要求按序输出
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-10-29 07:52:22 | 显示全部楼层
woaibai 发表于 2015-10-29 07:46
如果知道分数范围的话,比如0-100, 可以用counting sort
lz这是哪个组的?

嗯,但是面试官没说分数范围,所以犹豫了好久没说

面试官是Real-Time的
我投的是BackEnd 和 Growth
回复 支持 反对

使用道具 举报

doudoujiejie 发表于 2015-10-29 18:54:26 | 显示全部楼层
可以先用quick selection找到k-th largest 再扫一遍数组找到比它大的吗。。。这样是o(n)?
回复 支持 反对

使用道具 举报

stormy1991 发表于 2015-10-30 04:28:51 | 显示全部楼层
话说lz是啥时候投的呀,之前同学帮忙内推了一直没有消息
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-10-30 11:40:50 | 显示全部楼层
doudoujiejie 发表于 2015-10-29 18:54
可以先用quick selection找到k-th largest 再扫一遍数组找到比它大的吗。。。这样是o(n)?

QuickSelection就直接能返回前K大的吧
不过他要求有序输出。。。
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-10-30 11:42:50 | 显示全部楼层
stormy1991 发表于 2015-10-30 04:28
话说lz是啥时候投的呀,之前同学帮忙内推了一直没有消息
. visit 1point3acres.com for more.
我14号推的,16号让我约时间

再催催?
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-10-31 08:23:46 | 显示全部楼层
刚收到邮件,已跪
回复 支持 反对

使用道具 举报

whuyt 发表于 2015-10-31 18:53:11 | 显示全部楼层
lcl3356897 发表于 2015-10-30 11:40
QuickSelection就直接能返回前K大的吧
不过他要求有序输出。。。

quickselect后再排序吧,因为k是定值,排序是O(1)。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-10 09:04:36 | 显示全部楼层
应该就是quick select啊
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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