algorithm - What data structure will optimzied to represent stock market? -

data various stocks coming various stock exchange continuously. data structure suitable store these data?

things consider :

a) effective retrieval , update of data required stock data changes per second or microsecond during trading time.

i thought of using heap number of stocks more or less constant , frequent used operations retrieval , update heap should perform scenario.

b) need show stocks trending (as in volume of shares being sold active , least active, high profit , loss on particular day)

i nt sure how got this.

c) storing database using programming language has latency considering amount of stocks traded during particular time, how can u store transactional data persistently??

ps: interview question morgan stanley.

a heap doesn't support efficient random access (i.e. look-up index) nor getting top k elements without removing elements (which not desired).

my answer like:

a database preferred choice this, as, proper table structure , indexing, of required operations can done efficiently.

so suppose more theoretical question understanding of data structures (related in-memory storage, rather persistent).

it seems multiple data structures way go:

a) effective retrieval , update of data required stock data changes per second or microsecond during trading time.

a map make sense one. hash-map or tree-map allows fast look-up.

b) how show stocks trending (as in volume of shares being sold active , least active, high profit , loss on particular day)?

just sorted data structure seems make sense here (with above map having pointers correct node, or pointing same node). 1 activity , 1 profit.

i'd go sorted (double) linked-list. takes minimal time first or last n items. since have pointer element through map, updating takes long map lookup plus number of moves of item required sorted again (if any). if item moves many indices @ once, linked-list not option (in case i'd go binary search tree).

c) how can store transactional data persistently?

i understand question - if connection database lost or database goes down @ point, how ensure there no data corruption? if not it, would've asked rephrase.

just database course should cover this.

as far remember - has creating record, updating record, , setting real pointer record once has been updated. before might have set pointer old record can check if it's been deleted if happens after setting pointer away, before deletion.

another option having active transaction table add when starting transaction , remove when transaction completes (which stores required details roll or resume transaction). thus, whenever okay again, check table , roll or resume transactions have not yet completed.