Тестовое задание. Senior Java Developer

Автор: Петр Арсентьев


Broker

Когда я начинаю заниматься с новым учеником, первое, что мне нужно знать, – это его опыт устройства на работу и опыт решения тестовых заданий, которые ему при этом предлагались. Это дает мне первичную информацию о целях ученика. В основном тестовые задания представляют собой однотипные задачи либо на знание технологий, либо на демонстрацию знаний алгоритмов. Обычно это скучные мини-проекты – их выдают, чтобы проверить, как человек оформляет код, пишет ли тесты и может ли в целом нормально решать типовые задачи.

По своему опыту я могу сказать, что если вам прислали тестовое задание, есть два варианта: либо у вас мало опыта, либо контора эта не очень хорошая. Почему это так? Во-первых, у опытного разработчика должны быть свои наработки, проекты, которые можно показать. Во-вторых, по тестовому заданию можно судить только о том, что человек что-то может сделать, но не больше. И не факт, что вообще задание выполнил он сам. Например, мое первое тестовое задание я выполнил при помощи друга.

Однажды я стал заниматься с новым учеником, который уже пробовал устраиваться на работу. Ему выдали тестовое задание. Это задание привлекло мое внимание по нескольким причинам:

  1. Позиция, на которую претендовал ученик, была Senior Developer.
  2. Тема тестового – обработка заказов на бирже.
  3. Одно из требований – высокая производительность. Время исполнения программы должно быть в районе 6 секунд.
  4. Заработная плата на данную позицию начиналась от 150 000 рублей.
Таким образом, в этом задании есть все: знакомая тема и вызов (смогу ли я?).

Условия тестового задания

Я не могу выложить подробный текст задания во избежание каких-либо проблем с фирмой. Постараюсь изложить условия своими словами, чтобы оно отображало основную суть задания.

Дано: XML-файл, размер файла 205 МБ. Файл состоит из заявок на покупку и продажу акций. Заявки могут как выставляться, так и сниматься.
  • tag – AddOrder – заявка выставлена
  • tag – DeleteOrder – заявка снята
Пример выставления заявки:
                    <AddOrder book=\"stock-1\" operation=\"SELL\" price=\"100.50\" volume=\"81\" orderId=\"1\" />
                

  • tag – book – идентификатор акции
  • tag – operation – тип операции, покупка/продажа
  • tag – price – цена
  • tag – volume – объем заявки, сколько лотов (акций) купить/продать
  • tag – id – идентификатор заявки
Требуемые задачи:
  1. Распарсить входной файл.
  2. Разбить заявки по группам акций.
  3. Сделать агрегацию заявок с одинаковой ценой.
  4. Сделать сопоставление заявок купли / продажи. Например:
  5. Акция 1. Заявка на покупку 10 лотов по цене 32 рубля. Заявка на продажу 10 лотов по цене 30 рублей.
    Такие заявки должны сопоставиться и удалиться из общей группы.
    Общий принцип: цена покупки >= цена продажи. И наоборот: цена продажи <= цена покупки.
  6. Вывести на экран биржевой стакан всех групп акций.
Необходимые условия:
  • Использовать только средства, входящие в пакет Java SE.
  • Скорость обработки ~ 6 сек.
  • Качество кода.

Первое, с чего я начал решать задачу, – это определение частей кода, которые можно выполнить параллельно. За счет этого должна увеличиться скорость выполнения программы. Из задания понятно, что вся программа состоит из двух основных блоков:

  1. Парсинг входного файла.
  2. Обработка полученных данных.

Для парсинга XML-файла обычно используется два разных подхода:

  • Через поток. Решение SAX, StAX.
  • Через память. Решение DOM.
Поскольку нам нужно быстрое решение, я попробовал сделать это через SAX. Я не стал решать задачу целиком. Сначала я хотел проверить, сколько времени займет парсинг файла. К моему разочарованию время было неприемлемое:
  • SAX – time: 5838 ms.
  • StAX – time: 10280 ms.
Оба решения оказались не применимы для данной задачи: время парсинга файла без разделения на группы и объекты было выше, чем указано в условии задачи.

В своей практике мне периодически нужно решать задачи по парсингу файлов, где одно из требований – это скорость. Подобные задачи я решаю самописными парсерами. Поскольку в этом задании данные имеют простую схему, сделать парсер такого файла достаточно легко. Огромный минус такого решения – неуниверсальность. Если поставщик файла изменит порядок тегов либо добавит новый, парсер перестанет работать. Но в данном случае требуется минимальное время на выполнение, поэтому такое решение может быть использовано.

Считывание файла по строке:

try (BufferedReader br = new BufferedReader(new FileReader("orders.xml"))) {
    String line;
    while ((line = br.readLine()) != null) {
        if (line.startsWith("<A")) {
            final Order order = this.parse(line, true);
            HashMap<Integer, Order> list = orders.get(order.book);
            if (list == null) {
                list = new HashMap<Integer, Order>();
                orders.put(order.book, list);
            }
            list.put(order.id, order);
        } else if (line.startsWith("<D")) {
            final Order order = this.parse(line, false);
            orders.get(order.book).remove(order.id);
        }
    }
}
                    

Парсинг строки:
                            public Order parse(final String text, boolean add) {
                                boolean start = false;
                                int pos = -1;
                                String[] values = new String[5];
                                int current = 0;
                                for (int i=0;i!=text.length();++i) {
                                    if (text.charAt(i) == '\"') {
                                        if (start) {
                                            values[current++] = text.substring(pos+1, i);
                                            start = false;
                                        } else {
                                            start = true;
                                        }
                                        pos = i;
                                    }
                                }
                                if (add) {
                                    return new Order(
                                            values[0],
                                            "SELL".equals(values[1]) ? Order.Type.SELL : Order.Type.BUY,
                                            Float.valueOf(values[2]),
                                            Integer.valueOf(values[3]),
                                            Integer.valueOf(values[4])
                                    );
                                } else {
                                    return new Order(values[0], Order.Type.BUY, 0f, 0, Integer.valueOf(values[1]));
                                }
                            }
                    

После прохождения этого состояния на выходе будет карта из составленных объектов Order.
Далее нам надо разобрать заявки на группы и произвести дальнейшее вычисление в отдельных потоках. Для выполнения параллельного вычисления я использовал ExecuteService и Callable, Future конструкции. Я выбрал именно эти конструкции, т. к. нужно дождаться, пока все вычисления закончатся.

                        public void match() throws InterruptedException, ExecutionException {
                            List<Future<Book>> futures = new ArrayList<>(list.size());
                            for (final HashMap<Integer, Order> orders : list.values()) {
                            futures.add(pool.submit(new Callable<Book>() {
                                @Override
                                public Book call() throws Exception {
                                    Book book = new Book(orders.values());
                                    book.calculate();
                                    return book;
                                }
                                }));
                                }
                                for (Future<Book> future : futures) {
                                    future.get();
                                }
                            pool.shutdown();
                        }
                    

Далее в классе Book производятся агрегация заявок с одинаковой ценой и сортировка, причем сортировку выполняет коллекция TreeMap (поэтому важно очень хорошо разбираться в коллекциях).
После этого я могу получить биржевой стакан:

BUY 	PRICE SELL
		101.3      70
		100.9      86
		100.8      70
		100.7      46
		100.6      88
		100.5     800
		100.4   10698
		100.3  123328
		100.2  454086
		100.1 1024264
		100.0 1484290
		 99.9  469632
		 99.8  445490
		 99.7  404565
		 99.6  365271
		 99.5  310715
		 99.4  255846
		 99.3  205994
		 99.2  151606
		 99.1  112117
		 99.0   76596
		 98.9   50235
		 98.8   31844
		 98.7   20559
		 98.6   13665
		 98.5    6389
		 98.4    3682
		 98.3    2155
		 98.2    1109
		 98.1     778
		 98.0     339
		 97.9     193
		 97.8       8
		 97.6      44
     87  98.8
     58  99.0
     37  99.2
     16  99.3
    194  99.4
    465  99.5
  10885  99.6
 122787  99.7
 451619  99.8
1029027  99.9
1475579 100.0
 465343 100.1
 439919 100.2
 413034 100.3
 367049 100.4
 320736 100.5
 255797 100.6
 199429 100.7
 154344 100.8
 108765 100.9
  79794 101.0
  51008 101.1
  37026 101.2
  20180 101.3
  12335 101.4
   5603 101.5
   4175 101.6
   1980 101.7
    862 101.8
    454 101.9
    159 102.0
    143 102.1
                

Далее я решил поэкспериментировать и прогнать программу 100 раз подряд, чтобы получить средную выборку.
Диаграмма приведена ниже. Время выполнения получилось где-то 5200 миллисекунд – это даже лучше, чем требуется в условиях задачи. Но в задании следует учесть соотвествующие позиции, о чем я расскажу во второй части.

image

Исходный код