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&lt;String&gt; orders = new ArrayList&lt;String&gt;();

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

  // 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 Scanner(System.in);

      // read the lines from the text file 
      while (input.hasNextLine()) { 
           orders.add(input.nextLine()); 
      } 

      // separate the orders 
      for (int i = 0; i &lt; orders.size(); i++) { 
           System.out.println("" + orders.get(i));

           if (orders.get(i).contains("sell")) { 
                sells.add(orders.get(i)); 
           }

           if (orders.get(i).contains("buy")) { 
                buys.add(orders.get(i)); 
           }

      }

      // now get the price values from each line from the 
      // respective orders and compare the values 
      int buy = 0; 
      int sell = 0;

      for (int i = 0; i &lt; buys.size(); i++) { 
           buy = getPrice(buys.get(i)); 
           for (int j = 0; j &lt; sells.size(); j++) { 
                sell = getPrice(sells.get(j));

                // if the values are same, then compute the clear price 
                // values 
                // and increment the exchange value 
                if (buy == sell) { 
                     price += 2 * buy; 
                     exchange += 2; 
                } 
           } 
      }

      // print the final statement. 
      System.out.println("\nUnits of exchanged " + exchange + " total clearing price "+ price);
  } catch (Exception e) { 
      e.printStackTrace(); 
  } 
}

// getPrice method that retrieves the integer values from 
// each line 
 public static int getPrice(String s) { 
  // use the scanner object to access the line values 
  Scanner in = new Scanner(s).useDelimiter("[^0-9]+");

  int i = 0; 
  int j = 0;

  // get the integer values 
  while (in.hasNext()) { 
      i = in.nextInt(); 
      j = in.nextInt(); 
  }

  // return the required price value 
  return j; 
}
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&lt;Order&gt; {
    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 &amp;&amp; sell.price &lt;= 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. ;)