问一个面试经常问的ood，维护前k名的list的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一个面试经常问的ood，维护前k名的list的问题

问一个面试经常问的ood，维护前k名的list的问题# JobHunting - 待字闺中

g*12015-02-12 08:02

1 楼

很多家公司都会问，ex: 有一堆股票，经常更新，要设计数据结构能输出前10名股票。
大概的解法是hashmap + heap，想请大神讲一下具体设计方法

c*b2015-02-12 08:02

2 楼

public static List topK(int[] test,int k){
List l = new ArrayList();
if(k>test.length) return l;
//用hash存放股票名称，和出现次数
HashMap hash = new HashMap();
for(int i=0;iif(hash.containsKey(test[i])){
hash.put(test[i], hash.get(test[i])+1);
} else {
hash.put(test[i], 1);
}
}
//用一个priorityqueue，可以对出现次数进行排序
PriorityQueue> pq = new PriorityQueueInteger,Integer>>(k, new Comparator>(){
@Override
public int compare(Entry o1,EntryInteger> o2) {
if(o1.getValue()>o2.getValue()){
return -1;
} else if(o1.getValue()return 1;
} else {
return 0;
}
}
});
//然后无脑把hash插入到priorityqueue里
pq.addAll(hash.entrySet());
//取出所需要的个数
for(int i=0;iSystem.out.println(pq.peek());
l.add((Integer)pq.poll().getKey());
}
return l;
}

s*n2015-02-12 08:02

3 楼

大牛

【在 c******b 的大作中提到】

: public static List topK(int[] test,int k){
: List l = new ArrayList();
: if(k>test.length) return l;
: //用hash存放股票名称，和出现次数
: HashMap hash = new HashMap();
: for(int i=0;i: if(hash.containsKey(test[i])){
: hash.put(test[i], hash.get(test[i])+1);
: } else {
: hash.put(test[i], 1);

y*g2015-02-12 08:02

4 楼

感觉不用做一个新的Comparator， hashmap.value(), 然后加到heap里就好了。。这
题的follow up，如果进来的是一个stream，要怎么实时更新heap？

w*m2015-02-12 08:02

5 楼

加个fixed size的queue，随时间滑动。

【在 y*********g 的大作中提到】

: 感觉不用做一个新的Comparator， hashmap.value(), 然后加到heap里就好了。。这
: 题的follow up，如果进来的是一个stream，要怎么实时更新heap？

s*m2015-02-12 08:02

6 楼

能具体讲讲吗

【在 w********m 的大作中提到】

: 加个fixed size的queue，随时间滑动。

p*t2015-02-12 08:02

7 楼

不太明白为什么是记录出现频率，可能是因为我不太懂股票，股票是按出现频率排名的
么？我还以为是数字。。。

【在 c******b 的大作中提到】

p*t2015-02-12 08:02

8 楼

如果是那种只会一直增加不会减少的（比如出现频率），heap还是比较容易更新的，如
果是数字可以增加也可以减少的那种，要怎么更新heap我就不知道了，有人能说说么

【在 y*********g 的大作中提到】

: 感觉不用做一个新的Comparator， hashmap.value(), 然后加到heap里就好了。。这
: 题的follow up，如果进来的是一个stream，要怎么实时更新heap？

z*y2015-02-12 08:02

9 楼

两个问题：
1.经常更新是什么概念？
价格经常更新？成交量经常更新？还是有别的意思？
2.前10名股票是啥概念？
价格最高的前10？成交量最大的前10？价格涨幅最大的前10？

g*12015-02-12 08:02

10 楼

我有一个问题，在有stream过来需要更新数据时，如果存在在pq里地股票更新了数据要
怎么处理呢？是不是通过hashmap track到这个股票然后delete掉再添加到pq里？

【在 c******b 的大作中提到】

c*m2015-02-12 08:02

11 楼

不太明白经常更新是啥意思。输出前10的股票用小顶堆是不是就可以？

s*n2015-02-12 08:02

12 楼

前天BB onsite就遇到这道题了，交易会不断的进来，然后getTop10(或者topN)也会频
繁的调用，让设计。刚开始说priority_queue，对面国人大哥问什么是pq, 改口说
heap，也不让，最后我用双map, 一个map存ticker->{volume, iter_of_rankmap}, 另
一个multimap rankermap, size约束成10，存volumn->ticker, 自圆其说算是解决了
，面试的说cool cool，也不知道是真酷还是忽悠我，至今没想到其他方法。

h*c2015-02-12 08:02

13 楼

how about it
the source code of top or htop.

【在 s*********n 的大作中提到】

: 前天BB onsite就遇到这道题了，交易会不断的进来，然后getTop10(或者topN)也会频
: 繁的调用，让设计。刚开始说priority_queue，对面国人大哥问什么是pq, 改口说
: heap，也不让，最后我用双map, 一个map存ticker->{volume, iter_of_rankmap}, 另
: 一个multimap rankermap, size约束成10，存volumn->ticker, 自圆其说算是解决了
: ，面试的说cool cool，也不知道是真酷还是忽悠我，至今没想到其他方法。

s*n2015-02-12 08:02

14 楼

rankermap就是topN

【在 h**********c 的大作中提到】

: how about it
: the source code of top or htop.

h*c2015-02-12 08:02

15 楼

没太看明白top (built in) in linux 是怎么实现的

【在 s*********n 的大作中提到】

: rankermap就是topN

s*n2015-02-12 08:02

16 楼

哥们儿你捣乱呢么我在说这道题和linux里的top没关系

【在 h**********c 的大作中提到】

: 没太看明白top (built in) in linux 是怎么实现的