g*****1 发帖数: 93 | 1 很多家公司都会问,ex: 有一堆股票,经常更新,要设计数据结构能输出前10名股票。
大概的解法是hashmap + heap,想请大神讲一下具体设计方法 |
c******b 发帖数: 13 | 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;i
if(hash.containsKey(test[i])){
hash.put(test[i], hash.get(test[i])+1);
} else {
hash.put(test[i], 1);
}
}
//用一个priorityqueue,可以对出现次数进行排序
PriorityQueue> pq = new PriorityQueue
Integer,Integer>>(k, new Comparator>(){
@Override
public int compare(Entry o1,Entry
Integer> 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;i
System.out.println(pq.peek());
l.add((Integer)pq.poll().getKey());
}
return l;
} |
s*******n 发帖数: 344 | 3 大牛
【在 c******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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*********g 发帖数: 8 | 4 感觉不用做一个新的Comparator, hashmap.value(), 然后加到heap里就好了。。 这
题的follow up, 如果进来的是一个stream, 要怎么实时更新heap? |
w********m 发帖数: 1137 | 5 加个fixed size的queue,随时间滑动。
【在 y*********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉不用做一个新的Comparator, hashmap.value(), 然后加到heap里就好了。。 这 : 题的follow up, 如果进来的是一个stream, 要怎么实时更新heap?
|
s*******m 发帖数: 228 | 6 能具体讲讲吗
【在 w********m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 加个fixed size的queue,随时间滑动。
|
p**********t 发帖数: 75 | 7 不太明白为什么是记录出现频率,可能是因为我不太懂股票,股票是按出现频率排名的
么?我还以为是数字。。。
【在 c******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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);
|
p**********t 发帖数: 75 | 8 如果是那种只会一直增加不会减少的(比如出现频率),heap还是比较容易更新的,如
果是数字可以增加也可以减少的那种,要怎么更新heap我就不知道了,有人能说说么
【在 y*********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉不用做一个新的Comparator, hashmap.value(), 然后加到heap里就好了。。 这 : 题的follow up, 如果进来的是一个stream, 要怎么实时更新heap?
|
z***y 发帖数: 73 | 9 两个问题:
1.经常更新是什么概念?
价格经常更新?成交量经常更新?还是有别的意思?
2.前10名股票是啥概念?
价格最高的前10?成交量最大的前10?价格涨幅最大的前10? |
g*****1 发帖数: 93 | 10 我有一个问题,在有stream过来需要更新数据时,如果存在在pq里地股票更新了数据要
怎么处理呢? 是不是通过hashmap track到这个股票然后delete掉再添加到pq里?
【在 c******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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);
|
|
|
c*****m 发帖数: 271 | 11 不太明白经常更新是啥意思。输出前10的股票用小顶堆是不是就可以? |
s*********n 发帖数: 35 | 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**********c 发帖数: 4120 | 13 how about it
the source code of top or htop.
【在 s*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 前天BB onsite就遇到这道题了,交易会不断的进来,然后getTop10(或者topN)也会频 : 繁的调用,让设计。 刚开始说priority_queue,对面国人大哥问什么是pq, 改口说 : heap,也不让,最后我用双map, 一个map存ticker->{volume, iter_of_rankmap}, 另 : 一个multimap rankermap, size约束成10,存volumn->ticker, 自圆其说算是解决了 : ,面试的说cool cool,也不知道是真酷还是忽悠我,至今没想到其他方法。
|
s*********n 发帖数: 35 | 14 rankermap就是topN
【在 h**********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : how about it : the source code of top or htop.
|
h**********c 发帖数: 4120 | 15 没太看明白top (built in) in linux 是怎么实现的
【在 s*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : rankermap就是topN
|
s*********n 发帖数: 35 | 16 哥们儿你捣乱呢么 我在说这道题 和linux里的top没关系
【在 h**********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没太看明白top (built in) in linux 是怎么实现的
|
h**********c 发帖数: 4120 | 17 top in linux不就是按cpu usage 列topN吗
还有一个老中contributor 呢,不能现身来讲讲有什么高深算法吗?
一开头看见个 #include 'rbtree.h',心里疙瘩一下,听说过没用过
【在 s*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哥们儿你捣乱呢么 我在说这道题 和linux里的top没关系
|
s*********n 发帖数: 35 | 18 好吧。。。不好意思 我理解错了,你意思是参考top实现吧
你说用到了rbtree也make sense, map本身就是rbtree,linux用纯c没有stl只能自己实
现了
【在 h**********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : top in linux不就是按cpu usage 列topN吗 : 还有一个老中contributor 呢,不能现身来讲讲有什么高深算法吗? : 一开头看见个 #include 'rbtree.h',心里疙瘩一下,听说过没用过
|
h**********c 发帖数: 4120 | 19 ok,
你吃透了top,来讲讲吧
现在没有精力搞
或者前面回贴已经体现了所谓的扁平化的精髓,没太吃透
【在 s*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好吧。。。不好意思 我理解错了,你意思是参考top实现吧 : 你说用到了rbtree也make sense, map本身就是rbtree,linux用纯c没有stl只能自己实 : 现了
|