Processing buy and sell orders

My code is too slow, it does the desired, but not in \$O(\log n)\$ or faster.

Explanation of the auction system:

For simplicity we will assume that all orders are for a single unit of the traded item. The
double action system operates as follows. When a new buy order of $x arrives it is simply
stored for future use if none of the stored sell orders has an asking price lower than or equal
to $x. Otherwise, the new buying bid is matched with the sell order with lowest asking price
(earliest such order if there are ties). The two matched orders are removed from the system,
and the buyer receives the item in exchange for paying a clearing price equal to the matched
sell order asking price, i.e., the lowest asking price available at the time the new buy order
was received.

It's supposed to be a simple program that takes orders per line and sells or buys. The program must read from the standard input a list of buy and sell orders in the format given in the samples below, with one order per line. The program must print to the standard output the number of units exchanged and the total clearing price, using the format given in the examples below, and printing a new line at the end. Note that after processing the input there can be orders left uncleared.

Sample Input

order 1 sell at 30 
order 2 buy at 20

Output for Sample Input

units exchanged 0 total clearing price 0

```
public static void main(String args[]) {
// Create an array list for order to read data from the file
ArrayList orders = new ArrayList();

// Create sell and buys array list to get the list of
// buyers and sellers
ArrayList sells = new ArrayList();
ArrayList buys = new ArrayList();

// declare the required variables
int price = 0;
int exchange = 0;

// since we are using files put the execution code in try..catch
// block
try {
// create a file object by passing it to scanner class
// to read the file data
Scanner input = new Sca

You should always convert the input data in something sane ASAP. Dealing with string can get inefficient and unreadable pretty soon. Something like

enum Type {SELL, BUY}

@RequiredArgsConstructor
@Getter
@ToString
class Order {
    private final Type type;
    private final int id;
    private final int price;
}

sounds good. The above annotations are from Lombok, but you can write the boilerplate manually if you really want to.

By using a class instead of extracting the information from the string again and again, you'll surely gain a factor of 10+. That's good, but the more important part is the quadratic complexity.


Otherwise, the new buying bid is matched with the sell order with lowest asking price (earliest such order if there are ties).

This sounds like a Comparator: Order by price and then by id. I'd probably go for Guava's ComparisonChain, but it's simple enough:

class OrderComparator implements Comparator {
    public int compare(Order o1, Order o2) {
        int result = Integer.compare(o1.price, o2.price);
        if (result != 0) {
            return result;
        }
        return Integer.compare(o1.id, o2.id);
}

In theory, we could create an array of all sells and use Arrays.sort with our OrderComparator on it. However, when a new sell comes in, we'd need to insert it in the appropriate position or sort the array again. Too bad.

But we need no sorted array. All we need is

• to get the least element

• remove it if it's good enough

• add a new element

Fortunately, there's a PriorityQueue, which provides these operations efficiently (O(log n)). So we're nearly done.

A piece of code could look like

private void processNextBuy(Order buy) {
    assert buy.type == Type.BUY;
    // just look at it, but don't remove yet
    Order sell = sellQueue.peek();
    if (sell!=null && sell.price <= buy.price) {
        sellQueue.poll(); // paired, so remove it
        price += 2 * buy;
        exchange += 2;
    } else {
        buyQueue.add(buy); // unpaired, so process later
    }
}

From the description, I'm unsure if a new sell should be processed the same way. The boring parts around are left as an exercise for the reader. ;)

StackExchange Code Review Q#87247, answer score: 3