Effective data structures for data mapping

Question

What are the most efficient data structures for comparing data? For example, suppose I am presented with the following scenario:

<time available> <buy or sell> <company name> <buy or sell price> <amount to buy or sell> 

So that the file could contain:

 0 sell yahoo $100 #1 2 sell yahoo $14 #1 2 sell yahoo $28 #1 .. 95 other yahoo sells <$125 and amount #1 3 sell yahoo $17 #1 5 sell yahoo $33 #1 9 buy yahoo $125 #100 

Is it possible to correlate this last purchase with the previous 100 sales in O (n) time, where n = 100, if the purchase should be matched with the lowest selling price corresponding to the company that it wants to buy (or the one that comes first in tie case)?

I know a naive solution would be to sort the list and go in order, but it takes longer than O (n). What are the most effective data structures to solve this problem and similar ones?

Answer 1

Try using a hash card from the name of the company to a bunch of sell orders that are priced. The insertion of a sales order is now O(log n) , and the purchase order becomes permanent if the purchase does not use a sell order, or O(log n) if it does (your problem statement is not indicated)

Answer 2

Since the purchase and sale will deal with the same organization, it is better to save all purchase records (or) on the card, since all yahoo records are stored in a list that hashed on the card using "yahoo", as a key, this minimizes your search space. Sort according to the time, price, quantity, and then you can implement your desired function with the optimal cost when implementing this structure, during input. Then for any query after this, less time will be required, since the search space was minimal.