n****e
发帖数: 43 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: njhome (njhome), 信区: JobHunting
标 题: 一道关于数据结构的面试题
发信站: BBS 未名空间站 (Thu Aug 1 17:49:47 2013, 美东)
如果每天接受上百万的股票交易信息，但是只想储存某个公司的股票在时间上最近的前
十次交易的信息，其他信息都不要，应该最好用什么样的数据结构？比如今天头十个微
软股票交易， MSFT $31.67 100 shares 17:30:01,MSFT $31.67 200 shares 17:20:
01, MSFT $31.67 300 shares 16:30:01... |
k**********g
发帖数: 989 | 2
20:
circular buffer
【在 n****e 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: njhome (njhome), 信区: JobHunting
: 标 题: 一道关于数据结构的面试题
: 发信站: BBS 未名空间站 (Thu Aug 1 17:49:47 2013, 美东)
: 如果每天接受上百万的股票交易信息，但是只想储存某个公司的股票在时间上最近的前
: 十次交易的信息，其他信息都不要，应该最好用什么样的数据结构？比如今天头十个微
: 软股票交易， MSFT $31.67 100 shares 17:30:01,MSFT $31.67 200 shares 17:20:
: 01, MSFT $31.67 300 shares 16:30:01...
|
l*****v
发帖数: 498 | 3 没看懂考点在哪，很多circle的都可以吧。circle array，circle array of pointer
，circle double linked list |
n****e
发帖数: 43 | 4 能稍微详细的说一下怎么保证这个circular buffer只能放十个数据？然后怎么保证这
个circular buffer 放进去的数据是时间上最靠前的十个？多谢。
【在 k**********g 的大作中提到】
:
: 20:
: circular buffer
|
b*****e
发帖数: 474 | 5 it's implementing the queue with a circular buffer. The assumption is that
your program tries to enqueue each transaction in time order.
【在 n****e 的大作中提到】
: 能稍微详细的说一下怎么保证这个circular buffer只能放十个数据？然后怎么保证这
: 个circular buffer 放进去的数据是时间上最靠前的十个？多谢。
|
b*******s
发帖数: 5216 | 6 看不懂题目了，究竟是最早的10个交易 （你说的“今天头10个微软交易”br />
还是时间
上最近的10次br />
20:
【在 n****e 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: njhome (njhome), 信区: JobHunting
: 标 题: 一道关于数据结构的面试题
: 发信站: BBS 未名空间站 (Thu Aug 1 17:49:47 2013, 美东)
: 如果每天接受上百万的股票交易信息，但是只想储存某个公司的股票在时间上最近的前
: 十次交易的信息，其他信息都不要，应该最好用什么样的数据结构？比如今天头十个微
: 软股票交易， MSFT $31.67 100 shares 17:30:01,MSFT $31.67 200 shares 17:20:
: 01, MSFT $31.67 300 shares 16:30:01...
|
b*******s
发帖数: 5216 | 7 只放10个你用个计数就是了，每放进去一个加一，到10个就只能update不能add
时间上如果你不要求顺序存放，也就是update时顶多10次比较
【在 n****e 的大作中提到】
: 能稍微详细的说一下怎么保证这个circular buffer只能放十个数据？然后怎么保证这
: 个circular buffer 放进去的数据是时间上最靠前的十个？多谢。
|
b*******s
发帖数: 5216 | 8 再优化下就是纪录每次被从buffer中抛弃的那个交易记录的时间
要更新时，先和这个值比一下
【在 b*******s 的大作中提到】
: 只放10个你用个计数就是了，每放进去一个加一，到10个就只能update不能add
: 时间上如果你不要求顺序存放，也就是update时顶多10次比较
|
j*****I
发帖数: 2626 | 9 这种数据都是insensitive to loss的。前面丢了的，过会就补上了。
【在 b*******s 的大作中提到】
: 再优化下就是纪录每次被从buffer中抛弃的那个交易记录的时间
: 要更新时，先和这个值比一下
|
