7
\$\begingroup\$

I recently failed a Java interview exercise, and I'd like to know where I went wrong. As far as I can tell the code works, the tests pass, and the interviewer didn't give any specific feedback.

The task was to implement the PriceHistorySource interface, to provide data for an OHLC chart. Here is my implementation:

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Consumer;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class PriceHistorySourceImpl implements PriceHistorySource {

    private static class MutableOHLC {

        private long _ohlcTimestamp, _openTimestamp, _closeTimestamp;

        private BigDecimal _open, _high, _low, _close;

        /**
         * Must be called before first call to {@link #price(Price)}.
         */
        private void reset(long timestamp) {
            _ohlcTimestamp = timestamp;
            _open = null;
        }

        private boolean hasValue() {
            return null != _open;
        }

        private void price(Price price) {
            BigDecimal mid = price.getMid();
            long updateTime = price.getUpdateTime();
            if (hasValue()) {
                _high = _high.max(mid);
                _low = _low.min(mid);
                if (updateTime < _openTimestamp) { // First one wins.
                    _open = mid;
                    _openTimestamp = updateTime;
                }
                if (updateTime >= _closeTimestamp) { // Last one wins.
                    _close = mid;
                    _closeTimestamp = updateTime;
                }
            }
            else {
                _open = _high = _low = _close = mid;
                _openTimestamp = _closeTimestamp = updateTime;
            }
        }

        private void snapshotOrVoid(int instrument, Consumer<? super OHLC> target) {
            if (hasValue()) {
                target.accept(new OHLC(instrument, _open, _high, _low, _close, _ohlcTimestamp));
            }
        }

    }

    static final String IGNORING_LATE_PRICE_FORMAT = "Ignoring late price: {}";

    private class Ring {

        private final MutableOHLC[] _ring = new MutableOHLC[_maxIntervalCount];

        {
            for (int i = _ring.length - 1; i >= 0; --i) {
                _ring[i] = new MutableOHLC();
            }
        }

        private final int _instrumentId;

        private Ring(int instrumentId) {
            _instrumentId = instrumentId;
        }

        private int _biasedCursor = -1; // Must be biased by ring length (except initially) to keep LHS of % non-negative.

        private long _indexAtCursor = -1;

        /**
         * @param relIndex Must be in [-_ring.length, 0] but doesn't achieve lower bound in practice.
         */
        private MutableOHLC ohlc(int relIndex) {
            return _ring[(_biasedCursor + relIndex) % _ring.length];
        }

        /**
         * @param price Must have non-negative updateTime.
         */
        private synchronized void price(Price price) {
            long relIndex = price.getUpdateTime() / _intervalMillis - _indexAtCursor; // Bad result if updateTime is negative.
            if (relIndex <= -_ring.length) {
                _log.warn(IGNORING_LATE_PRICE_FORMAT, price);
            }
            else {
                if (relIndex > 0) { // May be large.
                    _biasedCursor = _ring.length + (int) ((_biasedCursor + relIndex) % _ring.length);
                    _indexAtCursor += relIndex;
                    for (int i = 1 - (int) Math.min(_ring.length, relIndex); i <= 0; ++i) {
                        ohlc(i).reset((_indexAtCursor + i) * _intervalMillis);
                    }
                    relIndex = 0;
                }
                ohlc((int) relIndex).price(price);
            }
        }

        private synchronized void getSnapshot(int intervalCount, Consumer<? super OHLC> target) {
            for (int i = 1 - intervalCount; i <= 0; ++i) {
                ohlc(i).snapshotOrVoid(_instrumentId, target);
            }
        }

    }

    private final Logger _log;

    private final long _intervalMillis;

    private final int _maxIntervalCount;

    PriceHistorySourceImpl(Logger log, long intervalMillis, int maxIntervalCount) {
        _log = log;
        _intervalMillis = intervalMillis;
        _maxIntervalCount = maxIntervalCount;
    }

    public PriceHistorySourceImpl(long intervalMillis, int maxIntervalCount) {
        this(LoggerFactory.getLogger(PriceHistorySourceImpl.class), intervalMillis, maxIntervalCount);
    }

    int maxIntervalCount() {
        return _maxIntervalCount;
    }

    private final ConcurrentHashMap<Integer, Ring> _idToRing = new ConcurrentHashMap<>();

    public void price(Price price) {
        // Observe we box instrumentId every time, it may be more efficient to keep it pre-boxed in the Price:
        _idToRing.computeIfAbsent(price.getInstrumentId(), Ring::new).price(price);
    }

    public List<OHLC> getPriceHistory(int intervalCount) {
        if (intervalCount <= 0 || intervalCount > _maxIntervalCount) {
            throw new IllegalArgumentException(String.valueOf(intervalCount));
        }
        Ring[] rings = _idToRing.values().stream().sorted((r1, r2) -> r1._instrumentId - r2._instrumentId).toArray(Ring[]::new); // Make deterministic.
        ArrayList<OHLC> history = new ArrayList<>(rings.length * intervalCount);
        for (Ring ring : rings) {
            ring.getSnapshot(intervalCount, history::add);
        }
        return history;
    }

}

The PriceHistorySource interface:

/**
 * Retrieve the most recent price history for the instrument.
 * @throws IllegalArgumentException if intervalCount is <=0 or >600
 * @param intervalCount the number of intervals to retrieve
 * @return the list of data. Never null, may be empty.
 */
List<OHLC> getPriceHistory(int intervalCount);

Note that Prices come as a stream, they are not known up-front. History requests may be concurrent with incoming prices.

The Price and OHLC classes are dumb POJOs that were provided in the exercise. I also wrote some unit tests:

import static PriceHistorySourceImpl.IGNORING_LATE_PRICE_FORMAT;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import java.math.BigDecimal;
import java.util.List;
import java.util.stream.IntStream;

import org.junit.Before;
import org.junit.Rule;
import org.junit.Test;
import org.slf4j.Logger;

public class TestPriceHistorySourceImpl {

    @Rule
    public final Mocks _mocks = new Mocks();

    private Logger _log;

    @Before
    public void setUp() {
        _log = _mocks.create(Logger.class);
    }

    private PriceHistorySourceImpl _source;

    private void replayAndCreate(long intervalMillis, int maxIntervalCount) {
        _mocks.replay();
        _source = new PriceHistorySourceImpl(_log, intervalMillis, maxIntervalCount);
    }

    private List<OHLC> maxHistory() { // For when we're not testing the effect of intervalCount.
        return _source.getPriceHistory(_source.maxIntervalCount());
    }

    @Test
    public void badIntervalCount() {
        int min = 1, max = 567; // The min is as per javadoc.
        replayAndCreate(123, max); // Don't care what intervalMillis is.
        IntStream.of(min - 1, max + 1).forEachOrdered(intervalCount -> {
            try {
                _source.getPriceHistory(intervalCount);
                fail("Expected illegal argument.");
            }
            catch (IllegalArgumentException e) {
                assertEquals(String.valueOf(intervalCount), e.getMessage());
            }
        });
        // But these are OK:
        _source.getPriceHistory(min);
        _source.getPriceHistory(max);
    }

    private static Price price(int instrumentId, long mid, long updateTime) {
        return Price.builder().withInstrumentId(instrumentId).withMid(BigDecimal.valueOf(mid)).withUpdateTime(updateTime).build();
    }

    private static void assertOhlc(int instrument, long timestamp, long open, long high, long low, long close, OHLC ohlc) {
        assertEquals(instrument, ohlc.getInstrument());
        assertEquals(timestamp, ohlc.getTimestamp());
        assertEquals(BigDecimal.valueOf(open), ohlc.getOpen());
        assertEquals(BigDecimal.valueOf(high), ohlc.getHigh());
        assertEquals(BigDecimal.valueOf(low), ohlc.getLow());
        assertEquals(BigDecimal.valueOf(close), ohlc.getClose());
    }

    @Test
    public void works() {
        replayAndCreate(100, 100);
        _source.price(price(5, 3, 250));
        _source.price(price(5, 1, 260));
        _source.price(price(5, 4, 270));
        _source.price(price(5, 2, 280));
        List<OHLC> history = maxHistory();
        assertOhlc(5, 200, 3, 4, 1, 2, history.remove(0));
        assertTrue(history.isEmpty());
    }

    @Test
    public void works2() {
        replayAndCreate(100, 10); // Total capacity is 1 second.
        _source.price(price(5, 43, 350));
        _source.price(price(5, 41, 360));
        _source.price(price(5, 44, 370));
        _source.price(price(5, 42, 380));
        _source.price(price(5, 63, 1250));
        _source.price(price(5, 61, 1260));
        _source.price(price(5, 64, 1270));
        _source.price(price(5, 62, 1280));
        {
            List<OHLC> history = maxHistory();
            assertOhlc(5, 300, 43, 44, 41, 42, history.remove(0));
            assertOhlc(5, 1200, 63, 64, 61, 62, history.remove(0));
            assertTrue(history.isEmpty());
        }
        {
            // If we ask for 1 don't return both:
            List<OHLC> history = _source.getPriceHistory(1);
            assertOhlc(5, 1200, 63, 64, 61, 62, history.remove(0));
            assertTrue(history.isEmpty());
        }
    }

    @Test
    public void latePrice() {
        Price goodPrice = price(5, 42, 0);
        Price latePrice = price(5, 44, 0);
        _log.warn(IGNORING_LATE_PRICE_FORMAT, latePrice); // Mock verification ensures this happened.
        replayAndCreate(100, 10); // Total capacity is 1 second.
        _source.price(price(5, 41, 999));
        _source.price(goodPrice);
        _source.price(price(5, 43, 1000)); // Makes latePrice late.
        _source.price(latePrice);
    }

    /**
     * This unit test enforces a design decision, an alternative would be to treat intervalCount as a max number of intervals to return per instrument.
     */
    @Test
    public void treatIntervalCountAsHowFarToLookBackRatherThanMaxItemsToReturn() {
        replayAndCreate(100, 100);
        _source.price(price(8, 44, 450));
        _source.price(price(8, 55, 550));
        _source.price(price(8, 77, 750));
        {
            List<OHLC> history = _source.getPriceHistory(3);
            assertOhlc(8, 500, 55, 55, 55, 55, history.remove(0));
            // Nothing at 600.
            assertOhlc(8, 700, 77, 77, 77, 77, history.remove(0));
            assertTrue(history.isEmpty());
        }
        {
            List<OHLC> history = _source.getPriceHistory(4);
            assertOhlc(8, 400, 44, 44, 44, 44, history.remove(0));
            assertOhlc(8, 500, 55, 55, 55, 55, history.remove(0));
            // Nothing at 600.
            assertOhlc(8, 700, 77, 77, 77, 77, history.remove(0));
            assertTrue(history.isEmpty());
        }
        IntStream.of(1, 2).forEachOrdered(intervalCount -> {
            List<OHLC> history = _source.getPriceHistory(intervalCount);
            assertOhlc(8, 700, 77, 77, 77, 77, history.remove(0));
            assertTrue(history.isEmpty());
        });
    }

    @Test
    public void instrumentDoesNotHavePowerToEvictDataOfOtherInstrument() {
        replayAndCreate(100, 100); // Ten seconds capacity per instrument.
        _source.price(price(8, 44, 450));
        _source.price(price(8, 55, 550));
        _source.price(price(8, 66, 650));
        _source.price(price(9, 66, 650)); // Will be evicted by the 10650 price.
        _source.price(price(9, 44, 10450));
        _source.price(price(9, 55, 10550));
        _source.price(price(9, 66, 10650));
        {
            List<OHLC> history = _source.getPriceHistory(2);
            assertOhlc(8, 500, 55, 55, 55, 55, history.remove(0));
            assertOhlc(8, 600, 66, 66, 66, 66, history.remove(0));
            assertOhlc(9, 10500, 55, 55, 55, 55, history.remove(0));
            assertOhlc(9, 10600, 66, 66, 66, 66, history.remove(0));
            assertTrue(history.isEmpty());
        }
        {
            List<OHLC> history = maxHistory();
            assertOhlc(8, 400, 44, 44, 44, 44, history.remove(0));
            assertOhlc(8, 500, 55, 55, 55, 55, history.remove(0));
            assertOhlc(8, 600, 66, 66, 66, 66, history.remove(0));
            assertOhlc(9, 10400, 44, 44, 44, 44, history.remove(0));
            assertOhlc(9, 10500, 55, 55, 55, 55, history.remove(0));
            assertOhlc(9, 10600, 66, 66, 66, 66, history.remove(0));
            assertTrue(history.isEmpty());
        }
    }

    @Test
    public void firstOpenAndLastCloseAreTheWinners() {
        replayAndCreate(100, 100);
        _source.price(price(8, 100, 410));
        _source.price(price(8, 101, 410));
        _source.price(price(8, 200, 490));
        _source.price(price(8, 201, 490));
        List<OHLC> history = maxHistory();
        assertOhlc(8, 400, 100, 201, 100, 201, history.remove(0));
        assertTrue(history.isEmpty());
    }

    @Test
    public void cursorMustBeBiasedByRingSize() {
        replayAndCreate(100, 10); // Capacity 1 second.
        _source.price(price(8, 100, 1050)); // First OHLC in ring.
        _source.price(price(8, 101, 150)); // Second in ring, should not blow up.
        List<OHLC> history = maxHistory();
        assertOhlc(8, 100, 101, 101, 101, 101, history.remove(0));
        assertOhlc(8, 1000, 100, 100, 100, 100, history.remove(0));
        assertTrue(history.isEmpty());
    }

    @Test
    public void timestampsAreNotTruncated() { // Should blow up if the implementation casts long to int when unsafe to do so.
        replayAndCreate(1, 10);
        _source.price(price(8, 101, Integer.MAX_VALUE));
        List<OHLC> history = maxHistory();
        assertOhlc(8, Integer.MAX_VALUE, 101, 101, 101, 101, history.remove(0));
        assertTrue(history.isEmpty());
    }

    @Test
    public void timestampsAreNotTruncated2() {
        replayAndCreate(1, 10);
        _source.price(price(8, 201, 1L + Integer.MAX_VALUE));
        List<OHLC> history = maxHistory();
        assertOhlc(8, 1L + Integer.MAX_VALUE, 201, 201, 201, 201, history.remove(0));
        assertTrue(history.isEmpty());
    }

    @Test
    public void canActuallyGetWholeHistory() {
        replayAndCreate(100, 5);
        _source.price(price(8, 200, 50));
        _source.price(price(8, 201, 150));
        _source.price(price(8, 202, 250));
        _source.price(price(8, 203, 350));
        _source.price(price(8, 204, 450));
        {
            List<OHLC> history = maxHistory();
            assertOhlc(8, 0, 200, 200, 200, 200, history.remove(0));
            assertOhlc(8, 100, 201, 201, 201, 201, history.remove(0));
            assertOhlc(8, 200, 202, 202, 202, 202, history.remove(0));
            assertOhlc(8, 300, 203, 203, 203, 203, history.remove(0));
            assertOhlc(8, 400, 204, 204, 204, 204, history.remove(0));
            assertTrue(history.isEmpty());
        }
        _source.price(price(8, 205, 550));
        _source.price(price(8, 206, 650));
        _source.price(price(8, 207, 750));
        {
            List<OHLC> history = maxHistory();
            assertOhlc(8, 300, 203, 203, 203, 203, history.remove(0));
            assertOhlc(8, 400, 204, 204, 204, 204, history.remove(0));
            assertOhlc(8, 500, 205, 205, 205, 205, history.remove(0));
            assertOhlc(8, 600, 206, 206, 206, 206, history.remove(0));
            assertOhlc(8, 700, 207, 207, 207, 207, history.remove(0));
            assertTrue(history.isEmpty());
        }
    }

}

All Mocks does is automatically verify all the EasyMock mocks it created, provided the test was successful.

Summary of additional info in the brief:

  • use Java 8 and any of the shiny new features that it provides. Feel free to use anything from Guava
  • Price provides mid, ask and bid prices. You're only expected to handle the mid price
  • process every price as quickly as possible
  • Your implementation will be judged on performance, maintainability, documentation, testability and design, as well as your use of algorithms, data structures and concurrency
  • What happens if we don't receive any prices within an interval?
\$\endgroup\$
  • \$\begingroup\$ What is an OHLC chart? \$\endgroup\$ – Simon Forsberg Feb 14 '17 at 17:58
  • 2
    \$\begingroup\$ @SimonForsberg for each interval of incoming prices, the Open (first), High, Low and Close price are recorded. See en.wikipedia.org/wiki/Open-high-low-close_chart \$\endgroup\$ – Andrzej Cichocki Feb 14 '17 at 18:09
  • \$\begingroup\$ Were you told to use BigDecimal, or did the problem description indicate that you would need it? I read 10 lines of your code and that was the first thing that jumped out at me. \$\endgroup\$ – JS1 Feb 14 '17 at 19:14
  • \$\begingroup\$ @JS1 it's what the provided Price and OHLC classes used. I thought it was weird, but it didn't get in the way of my solution so I didn't feel the need to change it to something more sensible \$\endgroup\$ – Andrzej Cichocki Feb 14 '17 at 19:29
  • 1
    \$\begingroup\$ @AndrzejCichocki did the provided classes implement equals/hashcode? \$\endgroup\$ – Timothy Truckle Feb 14 '17 at 20:56
6
\$\begingroup\$

Here is what I think of your code.

Disclaimer: My thoughts may be completely different to why the potential employer rejected your approach.

Formal weaknesses

Confusing code structure

You put the public method inherited from the interface at the last position in your class file. Usually public methods are placed at the top right behind the constructors or at least right before the methods with lesser visibility the "entry point" uses.

Also you have a "hidden" property (_idToRing) which is defined among the methods instead of before the constructor. The same applies for IGNORING_LATE_PRICE_FORMAT.

(Unused) Getter

You created a getter for maxIntervalCount which is never used (as far as I see...)

But the major problem with that is that getters violate the information hiding paradigm of OOP and should only be used in DTOs.

Naming conventions (minor)

You prefix class member variables with _ which is explicitly discouraged by the Java naming conventions.

Although I use this naming scheme in my projects too it might not be the best idea to do so in a interview task...

Business solution weaknesses

Complex approach

Your approach is rather complex. Without having deeply thought about the problem it might be solvable with some (nested) sorted collections (e.g. TreeSet).

Separation of concerns

As far as I see there is no requirement to collect the Price objects yourself. It might be a good idea to let the user pass in the list of prices either via constructor or setter.

Bad naming

Classes

I don't know how the interval concept relates to a ring but maybe that's just me...

Methods

  • You added another public method to your (main) class price. It obviously adds another Price object to the statistics. Therefore it should be named addPrice or add.

  • Your method getSnapshot is void. Therefore it should not be named like a getter.

  • Your method ohlc gets a MutableOHLC object from the _ring array. It should have a "getter" name.

On the other hand the interfaces method should also not be named like a getter since it does some effort to calculate the result...

Variables

You use abbreviations in your variable names (relIndex).

Unneeded synchronization

You have some synchronized method which could by simply avoided if you would work on a local copy of the list of prices.

Unit Test

Your unit tests are to complex and do not support the understanding of the code. There are lots of "magic numbers" in them and lots of duplicated code (initializations of price objects).

Most important: good unit tests have method names that tell a story from the business requirements beginning with the one that is easiest to implement getting more and more complex (and should off cause be written right before implementing the tested behavior...).

E.g.:

with_empty_price_list_OHLC_list_is_empty()
single_price_in_list_creates_single_OHLC_list_entry()
two_prices_within_same_interval_result_in_single_OHLC_entry()
two_prices_in_different_intervals_result_in_two_OHLC_entries()
//...
// Yes, test method names may not follow Java nameing conventions, 
// but I do explicitly _not_ say that they have to be written this way...

Also you should have as few asserts in your unit test as possible. So instead of asserting the properties of the result list entries you should rely on the equals implementation.


Maybe there are some more weaknesses but I think there is enough to think about already... ;o)

\$\endgroup\$
  • \$\begingroup\$ Thanks for the detailed review. Prices come as a stream, they are not known up-front. Synchronization is needed as requests will be concurrent with incoming prices. I've updated the question to clarify. A ring is a fixed-size collection of recent intervals. I'm generally averse to relying on equals as people love to break equals, which may make my tests pass by accident. Which of your points would you consider the showstopper(s)? \$\endgroup\$ – Andrzej Cichocki Feb 15 '17 at 17:58
  • \$\begingroup\$ @AndrzejCichocki "Which of your points would you consider the showstopper(s)?" I don't think that there are individual points that "stopped the show", I think other candidates were just closer to what they expected. My suggestions to you are: Improve your skill to find good identifier names. (attend a code retreat near to you. Use the IDEs sorting feature to order member variables and methods. Read Robert "uncle Bob" Martins book "Clean Code". \$\endgroup\$ – Timothy Truckle Feb 15 '17 at 21:13
  • \$\begingroup\$ @AndrzejCichocki "Prices come as a stream, they are not known up-front. Synchronization is needed as requests will be concurrent with incoming prices." IMHO this is another flavor of SoP violation. You could collect the prices in a (synchonised) list and split them up into the intervals using a copy of that list. \$\endgroup\$ – Timothy Truckle Feb 15 '17 at 21:25
  • \$\begingroup\$ @AndrzejCichocki "I'm generally averse to relying on equals as people love to break equals" then you should verify your doubts by writing UnitTests that check the implementation of equals holds the contract. \$\endgroup\$ – Timothy Truckle Feb 15 '17 at 21:27
1
\$\begingroup\$

Thought just occurred to me that maybe guava has a ring class, which as the task explicitly allowed the use of guava would have saved a lot of effort. And indeed it does, EvictingQueue. Maybe this, together with optional parts of the solution that I could have written in the time saved, was the showstopper for the interviewer.

\$\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.