n*****g
发帖数: 178 | 1 我在careercup上看到一道题目是：
Write a class that displays average of stock prices for a given stock symbol
for the last 10 minutes. We have a service that sends stock updates about
5000 times per second. The structure of the message is :
Message {
long timestamp;
String symbol; // E.g. AAPL
double price;
}
像这种类型的题目，大家有没有好的资料，可以集中练习的？
顺便问一下这道题怎么解，多谢各位！ |
R*****i
发帖数: 2126 | 2 需要把数据放进堆里吧？如果堆没满，只有死求平均价了，如果堆满了，前一个平均价
跟后一个平均价有非常简单的关系。
也许不需要把所有5000*600的价钱都存起来，一秒100次也许足够了？ |
n*****g
发帖数: 178 | |
s********x
发帖数: 81 | 4 这是网上看到的别人的解答。
http://www.careercup.com/question?id=4827656025538560
Use a ring buffer (circular queue) of type Message of size 5000*60*10 which
is 3000000B or 3MB. The memory footprint will be 3MB*sizeof(Message) so that
gives us upper limit of 100MB (string ticker are no more than 4B and fixed
length for int64/double).
Maintain a rolling sum (type double) and every time adding a stock price,
add it to sum and subtract the last purged value.
Simply return sum/Total entries |
n*****g
发帖数: 178 | 5
which
that
fixed
我也是看的这个帖子.....
【在 s********x 的大作中提到】
: 这是网上看到的别人的解答。
: http://www.careercup.com/question?id=4827656025538560
: Use a ring buffer (circular queue) of type Message of size 5000*60*10 which
: is 3000000B or 3MB. The memory footprint will be 3MB*sizeof(Message) so that
: gives us upper limit of 100MB (string ticker are no more than 4B and fixed
: length for int64/double).
: Maintain a rolling sum (type double) and every time adding a stock price,
: add it to sum and subtract the last purged value.
: Simply return sum/Total entries
|
R*****i
发帖数: 2126 | 6
which
that
fixed
我个人比较反对用circular queue, 双向链表效率低下，在这种实时要求很高的情况下
，显然不是好办法。
因为数据大小已经固定，所以我觉得可以用固定数组。然后分别用两个index来指出头
和尾，这样FIFO操作可以直接替换数据.
【在 s********x 的大作中提到】
: 这是网上看到的别人的解答。
: http://www.careercup.com/question?id=4827656025538560
: Use a ring buffer (circular queue) of type Message of size 5000*60*10 which
: is 3000000B or 3MB. The memory footprint will be 3MB*sizeof(Message) so that
: gives us upper limit of 100MB (string ticker are no more than 4B and fixed
: length for int64/double).
: Maintain a rolling sum (type double) and every time adding a stock price,
: add it to sum and subtract the last purged value.
: Simply return sum/Total entries
|
n*****g
发帖数: 178 | 7
能否给个代码？
【在 R*****i 的大作中提到】
:
: which
: that
: fixed
: 我个人比较反对用circular queue, 双向链表效率低下，在这种实时要求很高的情况下
: ，显然不是好办法。
: 因为数据大小已经固定，所以我觉得可以用固定数组。然后分别用两个index来指出头
: 和尾，这样FIFO操作可以直接替换数据.
|
