Here is a final exam problem from an earlier iteration of this course.
Write a program to manage buy and sell orders for a simple electronic market. For simplicity we will assume that only a single commodity gets traded in this exchange. As a further simplification, we will also assume that all orders in this system will not include a price and will only deal with how many units the client wants to buy or sell. Traders who participate in this market will be identified by integer ID numbers that have been issued to them by the exchange.
Your program will work by reading a list of buy and sell orders from a file named "orders.txt". Each line in the text file will take the form
<trader id> <order> <units>
Where <trader id> is the ID number of the trader who entered the order, <order> is either "buy" for a buy order or "sell" for a sell order, and <units> is the number of units of the commodity the trader wants to buy or sell.
Your program will read the orders and attempt to match buyers with sellers. After matching the orders, your program will print a list of trades in which one trader sells a number of units to another trader.
For example, if the "orders.txt" file contains the text
105 buy 250 333 sell 100 409 sell 500 632 buy 400 375 sell 100
your program should print
333 sells 100 units to 105 409 sells 150 units to 105 409 sells 350 units to 632 375 sells 50 units to 632
Trades should be executed in a "first come, first served" order, with orders to buy fulfilled in the order in which they appear in the order file.
The solution to this problem will require several classes. The first three classes are simple classes to represent a seller, a buyer, and a sale:
public class Seller {
private int id;
private int amount;
public Seller(int id,int amount) {
this.id = id;
this.amount = amount;
}
}
public class Buyer {
private int id;
private int amount;
public Buyer(int id,int amount) {
this.id = id;
this.amount = amount;
}
}
public class Sale {
private int sellerId;
private int buyerId;
private int amount;
public Sale(int seller,int buyer,int amount) {
sellerId = seller;
buyerId = buyer;
this.amount = amount;
}
}
Next, we need a class that will implement the matching algorithm between sellers and buyers. For that purpose we create a Market class:
public class Market {
private ArrayList<Seller> sellers;
private ArrayList<Buyer> buyers;
private ArrayList<Sale> sales;
public Market() {
sellers = new ArrayList<Seller>();
buyers = new ArrayList<Buyer>();
sales = new ArrayList<Sale>();
}
}
At this point the classes I have outlined above are in first draft form. To complete these classes we will need to add additional methods to each of the classes. Designing a solution to a problem is largely a process of discovering which methods we will need to write. There are several different approaches we can take to this discovery process.
An approach that I often use in programming is top-down design. In this approach we start by writing the top level code for the application in the main method. This gives us a broad outline of what needs to be done and an initial list of methods that we need to write.
Here is the main method for the application in the Market class:
public static void main(String[] args) {
Market m = new Market();
m.readOrders();
m.makeTrades();
m.saveSales();
}
This outlines three major methods that we will need to write in the Market class: a method to read the buy and sell orders from the text file, a method to match buyers and sellers, and a method to write the sales to the output file.
In the next round of the process we write those methods. The two simplest methods are the methods to the reading and writing from files:
public void readOrders() {
Scanner input = null;
try {
input = new Scanner(new File("orders.txt"));
} catch(Exception ex) {
System.out.println("Could not open order file.");
System.exit(1);
}
while(input.hasNext()) {
int id = input.nextInt();
String what = input.next();
int quantity = input.nextInt();
if(what.equals("buy")) {
Buyer b = new Buyer(id,quantity);
buyers.add(b);
} else {
Seller s = new Seller(id,quantity);
sellers.add(s);
}
}
input.close();
}
public void saveSales() {
PrintWriter pw = null;
try {
pw = new PrintWriter(new File("sales.txt"));
} catch (Exception ex) {
System.out.println("Can not open file for writing.");
System.exit(0);
}
for(Sale s : sales) {
s.writeTo(pw);
}
pw.close();
}
Since these two methods follow familiar patterns we have seen many times before in examples, I won't comment in detail on these methods. The one small thing I will point out here is the way I have handled the problem of printing sales to the output file. For simplicity, I have passed the work of printing a Sale over to the Sale object itself, since that object contains all of the information it needs to be able to print itself. Here is the code for the writeTo() method I added to the Sale class:
public void writeTo(PrintWriter pw) {
pw.println(sellerId + " sells " + amount + " units to " + buyerId);
}
The heart of the problem is the algorithm for matching sellers and buyers. In the code for reading the trades from the input file I put the Buyer and Seller objects in two separate lists. The algorithm for matching sellers and buyers will take one Seller and one Buyer at a time from these lists and get them to trade as many units as they are able to.
One small complication we have to deal with is the fact that most of the time a Seller and a Buyer will want to trade different amounts. For example, we could have a Seller who wants to sell 200 units and Buyer who only wants to buy 100 units. In cases like this the participant who wants to trade the smaller number of units determines the trade. In this example, we would create a Sale that has the Seller selling the Buyer 100 units. This would satisfy the Buyer's request: we could then remove this Buyer from the list of Buyers. This would only partially satisfy the Seller's request, so we would have to reduce the amount that the Seller wants to sell by 100 units and then leave the Seller in the list to match with another buyer in a later round.
Here now is the complete code for the method that does the trades:
public void makeTrades() {
while(sellers.size() > 0 && buyers.size() > 0) {
// Bring together the seller at the front of the sellers line
// with the buyer at the front of the line of buyers
Seller s = sellers.get(0);
Buyer b = buyers.get(0);
if(s.getQuantity() > b.getQuantity()) {
Sale sale = new Sale(s.getId(),b.getId(),b.getQuantity());
sales.add(sale);
buyers.remove(0);
s.reduceQuantity(b.getQuantity());
} else if(s.getQuantity() == b.getQuantity()){
Sale sale = new Sale(s.getId(),b.getId(),b.getQuantity());
sales.add(sale);
sellers.remove(0);
buyers.remove(0);
} else {
Sale sale = new Sale(s.getId(),b.getId(),s.getQuantity());
sales.add(sale);
sellers.remove(0);
b.reduceQuantity(s.getQuantity());
}
}
}
This code will require us to add a few additional methods to the Seller and Buyer classes. Again, this is all part of the process of discovering what methods we need.
At the top of these notes you will find a button that allows you download the project containing the full source code for this example.