由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问个design的问题
相关主题
Top K in N sorted array发个一直没有见过满意答案的题吧
An interview question of finding the median in a moving window.问一道题(9)
问大家一个cpp中function pointer的问题G家电面的两个题
Two-Sigma面经sliding windows中维持topk频繁的query
问个题LinkedIn面经(已跪),攒个rp
G家电面题目刚电面完l家,只敲了一道题,看来是挂了。。。
问两道google题面试用C++, heap 怎么办?
讨论一道题问个经典问题的improvement
相关话题的讨论汇总
话题: 股票话题: 问个话题: 涨幅话题: design话题: top
进入JobHunting版参与讨论
1 (共1页)
P*******b
发帖数: 1001
1
实时显示top 5的股票。大牛给讲讲设计思路?
thanks
s*****n
发帖数: 5488
2
多实事?
一般来说,股票5000只。更新大概1分钟10次。这个随便算算好了。
如果做到per tick的,现在的cpu速度也够了。
考虑到大多数情况下,股票的per tick涨跌都很小。top 5经常保持在*cache*中。
来了数据,先更新top 5。然后用last 5的涨幅作为base line.小于的不考虑, 大于的
加入到top cache里面去。最后sort下,取 top5 足够了。

【在 P*******b 的大作中提到】
: 实时显示top 5的股票。大牛给讲讲设计思路?
: thanks

P*******b
发帖数: 1001
3
来的数据是股票当前价吧,是不是还要算每个股票个价格变化呢?

【在 s*****n 的大作中提到】
: 多实事?
: 一般来说,股票5000只。更新大概1分钟10次。这个随便算算好了。
: 如果做到per tick的,现在的cpu速度也够了。
: 考虑到大多数情况下,股票的per tick涨跌都很小。top 5经常保持在*cache*中。
: 来了数据,先更新top 5。然后用last 5的涨幅作为base line.小于的不考虑, 大于的
: 加入到top cache里面去。最后sort下,取 top5 足够了。

p*****2
发帖数: 21240
4
什么算top5呢?股价吗?
M********5
发帖数: 715
5
应该是算涨的最多的吧,这个就是跟google finance的那个应该是一样的吧

【在 p*****2 的大作中提到】
: 什么算top5呢?股价吗?
p*****2
发帖数: 21240
6

当天的涨幅最多吗?

【在 M********5 的大作中提到】
: 应该是算涨的最多的吧,这个就是跟google finance的那个应该是一样的吧
M********5
发帖数: 715
7
应该是的,我觉得这个的意思应该就是跟google finance的那个一样的。。。

【在 p*****2 的大作中提到】
:
: 当天的涨幅最多吗?

P*******b
发帖数: 1001
8
这个是这样,变化最大的。

【在 M********5 的大作中提到】
: 应该是的,我觉得这个的意思应该就是跟google finance的那个一样的。。。
p*****2
发帖数: 21240
9

不懂股票。但是不知道这题有啥好设计的。新的信息来了,每个读一遍都要O(n)吧?取
5个那么小,就是个常数,优化不优化影响都不大了。

【在 P*******b 的大作中提到】
: 这个是这样,变化最大的。
f*******t
发帖数: 7549
10
我搜了一下,nasdaq股票数不到3000
这么小的数怎么算都行
o***d
发帖数: 313
11
我怎么觉得是maxheap阿?
这个问题似乎是这样的:
如果每秒钟来1000个股票的现在的价格,要求显示今天股票涨幅最多的5支.
说个错误的做法:
第一次来数据的时候,把1000个股票的前5个找到,放到sorted array里.
然后,下次再来的1000个股票,okay,挨个算涨幅,然后跟现在的5支挨个比较?然后再怎么
维护这个sorted array? time complexity太高了吧?每次要insert and then rearrang
ement.
正确的做法是用maxheap???

【在 p*****2 的大作中提到】
:
: 不懂股票。但是不知道这题有啥好设计的。新的信息来了,每个读一遍都要O(n)吧?取
: 5个那么小,就是个常数,优化不优化影响都不大了。

p*****2
发帖数: 21240
12
用heap也是min heap 不过size 5 性能没啥区别吧

【在 o***d 的大作中提到】
: 我怎么觉得是maxheap阿?
: 这个问题似乎是这样的:
: 如果每秒钟来1000个股票的现在的价格,要求显示今天股票涨幅最多的5支.
: 说个错误的做法:
: 第一次来数据的时候,把1000个股票的前5个找到,放到sorted array里.
: 然后,下次再来的1000个股票,okay,挨个算涨幅,然后跟现在的5支挨个比较?然后再怎么
: 维护这个sorted array? time complexity太高了吧?每次要insert and then rearrang
: ement.
: 正确的做法是用maxheap???

o***d
发帖数: 313
13
哦,对,minheap

【在 p*****2 的大作中提到】
: 用heap也是min heap 不过size 5 性能没啥区别吧
1 (共1页)
进入JobHunting版参与讨论
相关主题
问个经典问题的improvement问个题
弱弱的问个C++用priority_queue定义min heap的问题G家电面题目
攒人品,twitter电话面经问两道google题
又想起一道google题目讨论一道题
Top K in N sorted array发个一直没有见过满意答案的题吧
An interview question of finding the median in a moving window.问一道题(9)
问大家一个cpp中function pointer的问题G家电面的两个题
Two-Sigma面经sliding windows中维持topk频繁的query
相关话题的讨论汇总
话题: 股票话题: 问个话题: 涨幅话题: design话题: top