Разбор задач Одноклассников на Joker 2019

С 28 по 29 октября в Санкт-Петербурге проходила Joker 2019 – самая большая и хардкорная на просторах России конференция, посвященная Java-разработке. Мероприятие проходило в седьмой раз и как всегда побило рекорд по посещаемости, в этот раз мероприятие привлекло более 2000 специалистов.

Одноклассники традиционно принимают участие в Joker в качестве партнеров мероприятия. В этом году на нашем стенде можно было попробовать справиться со знаменитыми «нерешаемыми» задачами от главного инженера OK.RU – Андрея Паньгина. Участники конференции, правильно ответившие на вопросы, получили призы.

Справедливости ради надо сказать, что из 1 000 листочков с задачами, которые мы раздали, обратно было получено менее 100. Лучшим оказалось решение, набравшее 4.5 балла из 5 возможных.

Мы публикуем задачи и их решения, чтобы вы смогли проверить свои силы.

1. Героический enum

В исходниках одной малоизвестной игры обнаружился такой код. Чем плоха реализация Group.of, и как её исправить?

enum Group {
    Few(1, 4),
    Several(5, 9),
    Pack(10, 19),
    Lots(20, 49),
    Swarm(50, Integer.MAX_VALUE);

    Group(int min, int max) { ... }

    public static Group of(int count) {
        for (Group group : Group.values()) {
            if (count >= group.min &&
                count <= group.max) {
                return group;
            }
        }
        throw new IllegalArgumentException();
    }
}

Решение

Если не холиворить о стилях кодирования, у этого фрагмента есть объективный недостаток – потенциальная performance проблема. Хотя линейный поиск нередко оказывается узким местом, в данном случае дело не в нём, ведь у этого enum лишь пять элементов. А что действительно может негативно отразиться на производительности – это избыточное выделение памяти при вызове Group.values(). Проблема в том, что метод values() у enum каждый раз возвращает новую копию массива, и HotSpot пока не в силах это оптимизировать. Простым решением будет сделать собственную копию массива values() и итерироваться по ней:

private static final Group[] ALL_GROUPS = Group.values();

public static Group of(int count) {
    for (Group group : ALL_GROUPS) {
        ....
    }

2. Стрёмные стримы

Уже вышла Java 13, а Николай ещё только постигает стримы. Укажите ошибки в методе, вычисляющем разницу между максимальным и минимальным элементами стрима.

int getDiameter(Stream<Integer> stream) {
    int min = stream.min(Integer::compare).get();
    int max = stream.max(Integer::compare).get();
    return max - min;
}

Решение

Стримы в Java как правило одноразовые: вызвать вторую терминальную операцию (в данном случае, max) не получится:

java.lang.IllegalStateException: stream has already been operated upon or closed

Кроме того, min и max возвращают Optional, операция get() на котором выкинет NoSuchElementException для пустого стрима. Поэтому правильней перед вызовом get() проверять isPresent() или же воспользоваться другими методами Optional: orElse, orElseThrow и т. п.

Наконец, от внимательного разработчика не ускользнёт тот факт, что разница между двумя int уже может не влезть в int, и стоило бы изменить тип возвращаемого значения на long.

3. Безопасный буфер

С помощью какого примитива синхронизации Java можно сделать операции put и get потокобезопасными на общем ByteBuffer?

final ByteBuffer buf = ByteBuffer.allocate(SIZE);

int get(int offset) {
    return buf.get(offset);
}

void put(int offset, int value) {
    buf.putInt(offset, value);
}

Выберите наиболее эффективный вариант, если известно, что потоков много, а get выполняется гораздо чаще, чем put.

• synchronized
• ReentrantLock
• ReentrantReadWriteLock
• StampedLock
• Semaphore
• Чтение и запись int в Java и так всегда атомарны

Решение

В задачах про читателей-писателей напрашивается ReentrantReadWriteLock, и зачастую это будет эффективным решением. Но заметим, что в данном случае операции get и put очень простые – вероятность, что конкурентный put сможет помешать get, невелика, тем более что по условию задачи операции put случаются реже. Значит, можно применить механизм оптимистичной блокировки, который предоставляет StampedLock.

StampedLock будет эффективнее ReentrantReadWriteLock за счёт того, что в случае успеха оптимистичной блокировки (fast path) вообще не происходит обновления разделяемых переменных, в то время как ReentrantReadWriteLock даже в лучшем случае выполняет как минимум один CAS.

4. Подарочки

Илья разрабатывает витрину подарков в социальной сети. Помогите ему написать метод add для структуры, хранящей не более N самых новых подарков. Подарок не должен добавляться, если он уже присутствует, либо если он старее остальных N.

interface Present {
    long getId();
    Date getCreated();
}



void add(Present p) {
    // Implement me
}

Решение

В качестве структуры данных, чтобы эффективно добавлять подарки и удалять самые старые не хуже, чем за O(log N), естественным образом подходит TreeSet или PriorityQueue. Вся хитрость лишь в компараторе: недостаточно сравнивать подарки только по getCreated(), ведь дата создания не обязана быть уникальной. Поэтому сравнивать нужно сначала по getCreated(), затем по getId(). Такой компаратор обеспечит и уникальность элементов, и упорядоченность по дате.

TreeSet<Present> tree = new TreeSet<>(
        Comparator.comparing(Present::getCreated)
                .thenComparing(Present::getId));

Осталось дело за малым: при добавлении подарка проверить, что размер не превысил N, и при необходимости удалить первый, самый старый, элемент коллекции.

void add(Present p) {
    if (tree.add(p) && tree.size() > N) {
        tree.pollFirst();
    }
}

5. Не дождёшься

Почему Юля никогда не дождётся окончания этой программы?

var executor = Executors.newFixedThreadPool(4);
for (File f : File.listRoots()) {
    executor.submit(() -> f.delete());
}
executor.awaitTermination(2, TimeUnit.HOURS);

Решение

Документация к awaitTermination подсказывает, что завершению выполнения должен предшествовать shutdown request. Всё просто: Юля забыла вызвать executor.shutdown().

Let's block ads! (Why?)