8
$\begingroup$

Consider two 2D-Array $B_{ij} $ (the buy array) and $S_{ij}$ (the sell array) where each $i^{th}$ element is associated with an array of floating-point values and each of the floating point value, in turn, is associated with an array of integers.

For example

B = [ 
  0001 => [ 32.5 => {10, 15, 20}, 
            45.2 => {48, 16, 19}, 
            ...,
            k1
          ], 
  0002 => [ 35.6 => {17, 35, 89}, 
            68.7 => {18, 43, 74}, 
            ...,
            k2
          ] 
] 

and similiarly for the sell array.

This is akin to an order association system of a stock/commodity exchange

BuyOrderBook = [
                 CompanyName => [
                                 Price1 => [Qty1, Qty2...],
                                 Price2 => [Qty1, Qty2...]
                                ]
                 SecondCompany = [...]
               ]

What is the fastest way known to solve the following problem:

Input: Buy array $B$, Sell array $S$
Problem: Decide wether there are $(c_1 \Rightarrow p_1 \Rightarrow q_1) \in B$ and $(c_2 \Rightarrow p_2 \Rightarrow q_2) \in S$ with $q_1, q_2 > 0$ and $p_2 \geq p_1$.

In short, what is the fatest way of matching orders for an exchange?

Update in response to comments

Lets say, MSFT has 25 shares @ \$60 to be sold and there is buyer who is willing to offer \$61 for 10 shares of MSFT. Then the buyer gets 10 shares @ \$60 and the buy order book becomes empty while the sell order book now is updated with new quantity - 15 shares @ \$60.

Now take the reverse case, MSFT has 25 shares @ \$60 to be bought and there is seller who is willing to receive \$61 for 10 shares of MSFT. Then the trade will not be executed because seller is demanding a minimum of \$61 and the buyer is offering a maximum of \$60. The orders are now stored and await until new orders are received.

(This is the limit order principle, where the seller specifies minimum price at which he is willing to sell at and buyer specifies maximum price at which he is willing to buy).

Post execution, the sell order book will be (25-10)=15@86.5 while buy order book will be empty (10-10)=0.

$\endgroup$
  • $\begingroup$ I edited heavily; please check that the meaning is still the one you intended. Is "stack" really the word you want to use here? I guess the data structure is not a stack, so is it a domain expression? As for the question, note that the decision problem you state and finding all matchings are not necessarily equally hard; in particular, matchings may conflict. $\endgroup$ – Raphael Apr 3 '12 at 17:21
  • $\begingroup$ @Raphael Made a small change in the problem statement with regards to $q_1, q_2$. The structure is a stack in that new orders are 'pushed' onto the order book. However, the association between company, price and quantity is important. Modify the structure as required. $\endgroup$ – check123 Apr 3 '12 at 17:43
  • $\begingroup$ @Raphael 'Matchings may conflict' An example? $\endgroup$ – check123 Apr 3 '12 at 17:44
  • $\begingroup$ 1) Stacks typically do not allow to access any but the top-most element. You want random access, right? 2) There may be two buy orders that both fit the same sell order but can not both be satisfied. $\endgroup$ – Raphael Apr 3 '12 at 17:50
  • $\begingroup$ @Raphael 1)Oh! Yes may be Array is a better word 2) If there are match conflicts they are resolved based on FIFO principle the older order gets preference (Most exchanges follow this principle) $\endgroup$ – check123 Apr 3 '12 at 17:54
5
$\begingroup$

Maintain your buy-order book as an array of companies. For each company, keep a priority queue of prices (max for buy and min for sell). For each price, keep a queue of orders.

To check for matching orders, for each company, call find-min() and find-max() on the company in the sell array and buy array to find the best buy/sell prices. If max > min, then try to fulfill the order. To fulfill the order, pull elements off of your buy and sell queues for that company and price, until one of your price queues is empty. When the price queue is empty, delete the corresponding element from its priority queue, and perform the check again.

This strategy costs constant time per order, and $O(\log p_i)$ per price change, where $p_i$ is the number of prices for company $i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.