# Thread-safe algorithm to make trades based on moving window of prices

Here is problem to be solved

TradingAlgorithm employs a trading algorithm which, based on the prices it receives, will return a trade to execute. The trading algorithm must implement the following interface:

public interface TradingAlgorithm {
Trade buildTrades(Price price);
}


A Price is made up of a product name and a numerical price.
A Trade is made up of a product name, a direction (buy or sell), a numerical price and a quantity.
Write an implementation of the TradingAlgorithm interface that satisfies the following:
Accepts an array of product names (String[]) at the time of construction. These are the products that can be traded. Returns a buy trade for a quantity of 1000 at the newest price, if the simple average of the last 4 prices is greater than the oldest price in that collection of 4 prices e.g. {1,2,3,4} will result in a trade, as will {4,5,6,4} but {9,4,2,1} will not. In other words a trade will be made when the simple average of a moving window of prices has an upward trend. The implementation should be thread-safe, and performant.

Here is my implementation.

public class Price {
private String product;
private BigDecimal price;
// getters and setters
}


public class Trade {
private String product;
private String direction;
private BigDecimal price;
private Integer quantity;
// getters and setters
}


public class DirectionAlgorithmImpl implements DirectionAlgorithm {

private static final int PRICE_SAMPLES_SIZE = 4;
private static final String DIRECTION_BUY = "buy";
private static final String DIRECTION_SELL = "sell";
private final Queue<BigDecimal> priceQueue = new LinkedList<>();
private BigDecimal movingSum = BigDecimal.ZERO;
private final Object lock = new Object();

@Override
public String getDirection(BigDecimal newPrice) {
synchronized (lock) {

priceQueue.add(newPrice);
movingSum = movingSum.add(newPrice);

if (priceQueue.size() > PRICE_SAMPLES_SIZE) {
BigDecimal removedPrice = priceQueue.remove();
BigDecimal oldestPrice = priceQueue.peek();

movingSum = movingSum.subtract(removedPrice);
BigDecimal sma = movingSum.divide(BigDecimal.valueOf(PRICE_SAMPLES_SIZE));

return getDirection(sma, oldestPrice);
} else if (priceQueue.size() == PRICE_SAMPLES_SIZE) {
BigDecimal oldestPrice = priceQueue.peek();

BigDecimal sma = movingSum.divide(BigDecimal.valueOf(PRICE_SAMPLES_SIZE));

return getDirection(sma, oldestPrice);
}

return null;
}
}

private String getDirection(BigDecimal sma, BigDecimal oldestPrice) {
return sma.compareTo(oldestPrice) > 0 ? DIRECTION_BUY : DIRECTION_SELL;
}

}


public class TradingAlgorithmImpl implements TradingAlgorithm {

private static final Integer TRADE_QUANTITY = 1000;
private final ConcurrentMap<String, DirectionAlgorithm> productToDirectionAlgoMap = new ConcurrentHashMap<>();

public TradingAlgorithmImpl(String[] productNames) {
if (productNames == null || productNames.length == 0) {
throw new IllegalArgumentException("product names cannot be null or empty");
}
for (String productName : productNames) {
productToDirectionAlgoMap.put(productName, new DirectionAlgorithmImpl());
}
}

@Override
public Trade buildTrades(Price price) {
String product = price.getProduct();
BigDecimal newPrice = price.getPrice();

// time complexity: O(1)
DirectionAlgorithm directionAlgorithm = productToDirectionAlgoMap.get(product);
if (directionAlgorithm != null) {
// time complexity: O(1)
String direction = directionAlgorithm.getDirection(newPrice);
if (direction != null) {
return new Trade(product, direction, newPrice, TRADE_QUANTITY);
}
}
return null;
}

}


## Questions

1. Is this code thread-safe?
2. Is there any way its time complexity can be improved?

## 1 Answer

Is this code thread-safe?

Yes.

Is there any way its time complexity can be improved?

No, the algorithmic time complexity is probably as low as can be.

Overall impression: This is pretty good code.

There are ways to make the code more performant in terms of instructions executed:

• BigDecimal.valueOf(PRICE_SAMPLES_SIZE) is recalculated each time; you can extract this into a static constant.

• BigDecimal multiplication is less involved than division. Rather than dividing the sum, multiply oldestPrice.

It could be argued that an ArrayList would perform better than a LinkedList despite this really being the LinkedList's turf. This is because we're talking about small amounts of data and a predictable amount of it (4); arraycopy-ing has good cache locality in this case, and won't take extra allocations. (*)

Code duplication? You branch on the size of priceQueue in getDirection, but the code is very similar.

Fewer than 4 elements: It is still possible to calculate an average and have an oldest pricing when the window is not full. The window can not be empty, because the relevant methods are called with a new price as parameter.

Whether this is desirable depends on the expectations of who will be evaluating the solution, but I find it helpful to limit the number of null-pointers in circulation. It also allows for some code merging.

Putting it together: Squeaking these changes into place cut wall time to about 25% in my local measurements.

@Override
public String getDirection(BigDecimal newPrice) {
synchronized (lock) {
priceQueue.add(newPrice);
movingSum = movingSum.add(newPrice);

if (priceQueue.size() > PRICE_SAMPLES_SIZE) {
BigDecimal removedPrice = priceQueue.remove();
movingSum = movingSum.subtract(removedPrice);
}

BigDecimal oldestPrice = priceQueue.peek();
oldestPrice = oldestPrice.multiply(BIGDECIMAL_PRICE_SAMPLES_SIZE);

return getDirection(movingSum, oldestPrice);
}
}


(*) This is purely in terms of processing speed. LinkedList has the better algorithmic complexity for these operations. ArrayList has the speed advantage in these circumstances.