热乎乎的 Uber 电面 fulltime

刚刚的Uber店面，太挫了。。

题目
You are given a collection of contestants and their scores, return the medalists and their scores

大意就是有一堆参赛者还有他们的分数，输出得奖牌的，就是前三名

我用PriorityQueue写的，自己写了个class Pla

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

Stackoverflow上介绍了蠢办法  O(n)

int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
int max3 = Integer.MIN_VALUE; // assuming integer elements in the array

for (int i = 0; i < theArray.length; i++) {
    if (theArray[i] > max1) {
        max3 = max2;
        max2 = max1;
        max1 = theArray[i];
    } else if (theArray[i] > max2) {
        if (max1 == theArray[i]) {
            // Neglect as already present in max1
        } else {
            max3 = max2;
            max2 = theArray[i];
        }
    } else if (theArray[i] > max3) {
        if (max1 == theArray[i] || max2 == theArray[i]) {
            // Neglect as already present in max1 OR max2
        } else {
            max3 = theArray[i];
        }
    }
}      

lcl3356897 发表于 2015-10-29 07:16
见补充，面试官应该是让找前k大的，O(n)时间

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

average O(n)找前K个就是quickselect呀，只不过找出来的这k个不是按顺序出来的就是了

这里有详细说法
http://stackoverflow.com/questio ... heap-vs-quickselect

average O(n) 应该是想让你用 quick selection

sqszsqsz 发表于 2015-10-29 06:17
Stackoverflow上介绍了蠢办法  O(n)

int max1 = Integer.MIN_VALUE;

你这个说白了是O(n*K)，只不过对于这个例子K是3所以看上去是O(n)

snowwolf 发表于 2015-10-29 06:43
你这个说白了是O(n*K)，只不过对于这个例子K是3所以看上去是O(n)

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

喜欢天王老子这个词

snowwolf 发表于 2015-10-29 06:43
你这个说白了是O(n*K)，只不过对于这个例子K是3所以看上去是O(n)

见补充，面试官应该是让找前k大的，O(n)时间

sqszsqsz 发表于 2015-10-29 06:46
毕竟题目要求是找前三名，K是定死的就是O(n). 除非问找前n名的score的方法，天王老子也没法O(n)给sort出 ...

见补充，面试官应该是让找前k大的，O(n)时间

我当时都傻了。后来想了想，如果范围不大的话，可以试试桶排序，不过已经没机会了。。

求大神讲解o(n)解法啊