Combination Sum - LeetCode with me 38

Очередная задачка на backtracking - выбрать из массива элементы, которые в сумме дают заданное число. Если представить, что ищем сумму двух элементов, которые вместе дают target, то нужно зафиксировать один элемент, допустим, А, то нужно найти второй, который равен (target - A). С тремя элементами так же - зафиксируем один элемент (А) и будем искать теперь два других, которые в сумме дают (target - A). Для суммы неограниченной длинны делаем несколько итераций, где каждый раз уменьшаем target на значение зафиксированного элемента.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Combination Sum II - LeetCode with me 39

Очень похоже на задачку, которую мы решали в прошлый раз, на Combination Sum. Основная сложность этой задачи состоит в том, что теперь исходные данные могут содержать дубликаты, а в результатах дубликатов быть не должно. Можем использовать структуры данных вроде множеств, который позволяют от дубликатов избавиться, либо отсортируем входные данные и будем пропускать дубликаты.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

First Missing Positive - LeetCode with me 40

Задачка уровня Hard на поиск первого положительного пропуска в массиве. Рассмотрим два решения - очевидное и оптимальное, используем циклическую сортировку.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Trapping Rain Water - LeetCode with me 41

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

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Multiply Strings - LeetCode with me 42

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

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Wildcard Matching - LeetCode with me 43

Еще одна сложная задача на написание собственного ограниченного движка регулярных выражений. Сначала попробуем применить наиболее логичный подход - класс Pattern, затем реализуем тривиальное решение, а затем решение на базе динамического программирования.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

https://javaswag.github.io/episode/72/

Слушать подкаст в Apple | Spotify | Yandex

В 72 выпуске подкаста Javaswag поговорили с Александром Барминым о Спринге и архитектуре Необанка

00:00 Начало
05:34 Значение доменной области в разработке
17:28 IBM FileNet и Java EE
22:45 Проблемы и эволюция Java EE
32:50 Spring и Spring Boot
48:10 Миграция между версиями Spring
56:05 Гибкость и сложности Spring Boot
01:01:02 Адаптация Spring к современным трендам
01:04:50 Проблемы зависимости от Spring
01:07:10 Конкуренция и эволюция Spring
01:14:49 Kotlin и Spring: синергия технологий
01:15:44 Эволюция TransferWise в Neobank
01:16:36 Архитектура Wise: микросервисы и AWS
01:19:21 Kubernetes и проблемы распределенных систем
01:24:55 Консистентность и механизмы реконсиляции
01:29:08 Управление микросервисами и версиями
01:33:20 Автоматизация обновления зависимостей
01:37:07 CI/CD и миграции баз данных
01:41:17 Деплой
01:46:49 Непопулярное мнение о языках программирования
01:50:00 Критика Spring Boot и его магии

Гость https://www.linkedin.com/in/abarmin/

Ссылки:
Канал Александра на YouTube - https://www.youtube.com/@ABarmin
Канал Java & Spring Weekly в Telegram - @java_weekly
Wise Tech Stack - https://medium.com/wise-engineering/wise-tech-stack-2022-edition-a6ac089a382f
Spring Cloud с Борисовым - https://youtu.be/4tSyz_v9w7Q

Кип сейф! 🖖

Jump Game II - LeetCode with me 44

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

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Permutations - LeetCode with me 45

Сегодня рассмотрим две задачи на генерацию перестановок. Обе решаются сходным образом - с использованием алгоритма backtracking.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Rotate Image - LeetCode with me 46

Задача на поворот двухмерного изображения. Берем и поворачиваем.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Group Anagrams - LeetCode with me 47

Группируем анаграммы вместе. Анаграммы - слова, которые могут быть преобразованы друг в друга путем перестановки букв в них. Очевидное решение с сортировкой работает, но не дает достаточной производительности, поэтому напишем свой несложный алгоритм хеширования.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Pow x ^ n - LeetCode with me 48

Реализуем функцию возведения в степень без использования стандартной библиотеки. Для повышения производительности воспользуемся знаниями из школьного курса алгебры.

Это последнее, семидесятое видео в 2024 году. За весь год мои видео посмотрели более 61 тысячи раз, что составляет более 8 тысяч часов. А еще на канал на YouTube подписалось больше 1100 новых зрителей. Довольно неплохой рост, на мой взгляд!

Спасибо всем, кто был со мной в 2024 году, увидимся в новом, 2025 году!

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

N-Queens - LeetCode with me 49

Первая задача в новом 2025 году. Начнем с уровня Hard и расставим ферзей по шахматной доске. Ничего сложного, обычный backtracking.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Maximum Subarray - LeetCode with me 50

Ищем подмассив произвольной длинный с максимальной суммой. Задача решается с использованием скользящего окна или алгоритма Кадано. Также разберем рекурсивный подход, основанный на идее divide and conquer.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Spring Shorts №1 - Embedded Database

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

Наверняка, многим известно, что если в Spring Boot добавить в качестве зависимости H2, то, по умолчанию, Spring Boot запустит H2 в памяти. Инстанс H2 можно настроить с помощью JDBC URL, который указывается в параметре spring.datasource.url в application.yml или application.properties. Если URL формата jdbc:h2:mem:test, то база данных будет запущена в памяти и все данные будут пропадать каждый раз, когда приложение перезапускается. Если же URL вида jdbc:h2:/data/test, то данные будут храниться на диске и сохраняться между перезапусками приложения.

Кроме этого, в самом Spring Framework есть возможность создавать in-memory инстансы не только H2, но также HSQL и Derby. Для этого нужно добавить соответствующую зависимость и объявить бин DataSource:

@Bean
DataSource dataSource() {
    return new EmbeddedDatabaseBuilder()
            .setType(EmbeddedDatabaseType.DERBY)
            .build();
}

EmbeddedDatabaseType это enum, в котором есть H2, HSQL и DERBY. Еще можно указать параметр generateUniqueName и при каждом создании бина у базы данных будет уникальное имя, а если указать addScript, то можно добавить имя файла из ресурсов, в котором будет SQL-скрипт для создания структуры таблиц или добавления данных.

Зачем может понадобиться отдельный DataSource с in-memory базой данных? Для тестов, например. А если хотите добавить поддержку свой базы, то можно через setDataSourceFactory передать свой DataSourceFactory, который будет, например, в докере запускать CouchDB.

Spring Shorts №2 - SQL Query

Расскажу еще про одну малоизвестную возможность Spring JDBC (не того, который Spring Data JDBC, а обычного). Самым часто используемым компонентом из этого модуля по праву считается JdbcTemplate - он и в базу пишет, и читает, и запросы выполняет.

В Spring Data есть отличная фича - при запуске приложения валидирует, правильно ли названы методы и есть ли в базе нужные колонки в таблицах. Hibernate делает то же самое для HQL, а вот у JdbcTemplate такой возможности нет. Зато в Spring JDBC есть класс SqlQuery, который позволяет обернуть обычный SQL запрос в объект и также валидировать при старте приложения.

Сделаю небольшой сетап - у меня будет таблица people, которая создается следующим скриптом:

CREATE TABLE people (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL
);

Доменный объект Person:

public record Person(
        Integer id,
        String name,
        Instant createdAt) {

    public Person(String name) {
        this(null, name, Instant.now());
    }

    public Person withId(int id) {
        return new Person(id, name, createdAt);
    }

}

А теперь, запрос на получение всех людей из базы данных:

public class FindPeopleQuery extends MappingSqlQuery<Person> {

    public FindPeopleQuery(DataSource dataSource) {
        super(
                dataSource,
                "SELECT id, name, created_at FROM people"
        );
        compileInternal();
    }

    @Override
    protected Person mapRow(ResultSet rs, int rowNum) throws SQLException {
        return new Person(
                rs.getInt("id"),
                rs.getString("name"),
                rs.getTimestamp("created_at").toInstant()
        );
    }
}

Все самое интересное - в конструкторе. Компонент зависит от DataSource, поэтому мы передаем его в качестве параметра в конструктор, а дальше вызываем родительский конструктор и передаем в него запрос, а затем вызываем compileInternal. compileInternal создает PreparedStatement и в этот-то момент и происходит валидация.

public FindPeopleQuery(DataSource dataSource) {
    super(
            dataSource,
            "SELECT id, name, created_at FROM people"
    );
    compileInternal();
}

Вторая часть - маппер в методе mapRow, который конвертирует строку из базы данных в доменный объект. Ну, здесь обычный RowMapper, такой же как и в JdbcTemplate.

Но как быть, когда в запросе есть параметры? Очень просто - параметры можно объявить и убедиться, что в запросе они точно есть. Выглядит вот так:

public class FindPersonByIdQuery extends MappingSqlQuery<Person> {

    public FindPersonByIdQuery(DataSource dataSource) {
        super(
                dataSource,
                "SELECT id, name, created_at FROM people WHERE id = ?"
        );
        declareParameter(new SqlParameter("id", Types.INTEGER));
        compile();
    }

    public List<Person> findAll() {
        return execute();
    }
}

Так как это отдельный класс, то можно добавить дополнительные методы, например, findAll и из него уже вызывать внутренние методы SqlQuery.

Spring Shorts №3 - Simple JDBC Insert

В прошлый раз мы посмотрели на SqlQuery, но есть ведь еще SimpleJdbcInsert, который позволяет избежать написания запросов на вставку. Почему именно их? Потому что запросы на вставку довольно большие - insert into table values (column1, column2) values (:value1, :value2), а еще важно не перепутать порядок параметров и колонок.

Воспользуемся таблицей из прошлого поста:

CREATE TABLE people (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL
);

Вставлять будем Person - такой же, как и до этого. А для вставки создадим класс InsertPersonQuery:

public class InsertPersonQuery {

    private final SimpleJdbcInsert jdbcInsert;

    public InsertPersonQuery(DataSource dataSource) {
        this.jdbcInsert = new SimpleJdbcInsert(dataSource)
                .withTableName("people")
                .usingGeneratedKeyColumns("id")
                .usingColumns("name", "created_at");
    }

    public Person insertPerson(Person person) {
        final int generatedId = jdbcInsert.execute(Map.of(
                "name", person.name(),
                "created_at", person.createdAt()
        ));
        return person.withId(generatedId);
    }
}

В конструкторе создаем SimpleJdbcInsert, указываем, в какую таблицу вставлять и значения каких колонок генерируются автоматически базой данных. Также можно указать имена колонок для вставки.

И самое главное - jdbcInsert.execute. Сюда можно передать Map с параметрами, выглядит вот так:

final int generatedId = jdbcInsert.execute(Map.of(
    "name", person.name(),
    "created_at", person.createdAt()
));

а еще можно завернуть доменный объект в BeanPropertySqlParameterSource и тогда Spring будет сам перекладывать значения из объекта в запрос:

public Person insertPerson(Person person) {
    final int generatedId = jdbcInsert
            .execute(new BeanPropertySqlParameterSource(person));
    return person.withId(generatedId);
}

А вы что используете для доступа к базе данных? Вы все еще кипятите Hibernate? Тогда мы идем к вам!

Mockito Shorts №1 - Введение

В прошлый раз был Spring, до этого был Spring и вообще почти всегда я пишу и рассказываю про Spring. Пора рассказать о чем-то другом - сегодня будет про Mockito. Да, про библиотеку для замены реальных зависимостей на настраиваемые тестовые. Рассказывать я буду про совместную работу с JUnit 5 и MockitoExtension.

Юнит-тест с Mockito обычно выглядит как-то так:

@ExtendWith(MockitoExtension.class)
public class MockitoExtensionDemoTest {
}

Чем занимается MockitoExtension? Он выполняет несколько действий:

1. Перед запуском каждого теста он вызывает Mockito.mockitoSession().initMocks(this), который для всех свойств с аннотацией @Mock создает и настраивает объект мока, для всех свойств с аннотацией @Spy создает частичный мок (экземпляр класса, обернутый в мок), а также для всех свойств с аннотацией @InjectMocks создает экземпляр и внедряет зависимости.

2. После выполнения каждого теста вызывает Mockito.validateMockitoUsage(). Если вы видели сообщения вида Unnecessary stubbing или MissingMethodInvocationException, то это результат работы validateMockitoUsage - этот метод проверяет, что все используемые моки правильно настроены и использованы.

3. А еще MockitoExtension проверяет на наличие на тестовом классе аннотации @MockitoSettings, которая позволяет настроить строгость и не показывать ошибок вида unnecessary stubbing.

Можно обойтись и без MockitoExtension, если создавать моки самостоятельно. Для этого вызываем Mockito.mock() и передаем в качестве параметра класс, для которого нужно создать мок. Например, у меня есть следующие связанные компоненты, которые я хочу использовать в своем тесте:

interface ExecutionContext {
    ContextQuestions getQuestions();
}

interface ContextQuestions {
    boolean isFeatureEnabled(String featureName);
}

Чтобы создать мок для ExecutionContext можно создать поле в тесте и поставить на него аннотацию @Mock:

@ExtendWith(MockitoExtension.class)
public class MockitoExtensionDemo2Test {
    @Mock
    ExecutionContext context;
}

Или же создать мок вручную:

public class MockitoExtensionDemo2Test {
    ExecutionContext context;

    @BeforeEach
    void setUp() {
        context = mock(ExecutionContext.class);
    }
}

Теперь у нас есть мок и для работы его нужно настроить. Сделать это можно через метод when:

@Test
void getQuestions_shouldReturnQuestions() {
    final ContextQuestions questions = featureName -> true;
    when(context.getQuestions()).thenReturn(questions);

    assertThat(context.getQuestions()).isNotNull();
}

Что будет, если я попытаюсь вызвать context.getQuestions().isFeatureEnabled() без вызова when? Очевидно, будет NPE:

@Test
void getQuestions_shouldThrowException() {
    assertThatThrownBy(() -> context.getQuestions().isFeatureEnabled("abc"))
            .isInstanceOf(NullPointerException.class);
}

У Mockito достаточно много параметров, которые могут упростить работу и первый из них это smart nullls:

@Test
void getQuestions_withSmartNulls() {
    context = mock(ExecutionContext.class, Answers.RETURNS_SMART_NULLS);
    context.getQuestions().isFeatureEnabled("abc");
}

Или

@Mock(answer = Answers.RETURNS_SMART_NULLS)
ExecutionContext context;

В этом случае сообщение об ошибке будет более развернутое:

You have a NullPointerException here:
… name of the class goes here
because this method call was *not* stubbed correctly:

Если хочется замокать ContextQuestions, который находится внутри ExecutionContext, то можно создать два мока:

@Test
void getQuestions_nestedMocks() {
    ContextQuestions questions = mock(ContextQuestions.class);
    when(context.getQuestions()).thenReturn(questions);
    when(questions.isFeatureEnabled("abc")).thenReturn(true);

    assertThat(context.getQuestions().isFeatureEnabled("abc")).isTrue();
}

Обычно так и делается, однако, Mockito может существенно облегчить жизнь, если использовать Anwers.RETURN_DEEP_STUBS. В этом случае код больше не бросает NPE, а возвращает мок, который возвращает значение по умолчанию:

@Test
void getQuestions_withDeepMocks() {
    assertThat(context.getQuestions().isFeatureEnabled("abc")).isFalse();
}

Кроме этого, можно сразу настраивать возвращаемые моки:

@Test
void getQuestions_nestedMocks() {
    when(context.getQuestions().isFeatureEnabled("abc")).thenReturn(true);

    assertThat(context.getQuestions().isFeatureEnabled("abc")).isTrue();
}

Ну, и напоследок, можно попросить Mockito вызывать реальные методы вместо моков:

@ExtendWith(MockitoExtension.class)
class WithRealMethods {
    @Mock(answer = Answers.CALLS_REAL_METHODS)
    AllEnabledQuestions questions;
    @InjectMocks
    DefaultExecutionContext context;

    @Test
    void getQuestions_willCallRealMethods() {
        assertThat(context.getQuestions().isFeatureEnabled("abc")).isTrue();
    }
}

Это все на сегодня, в следующий раз посмотрим, как можно настроить мок с помощью thenAnswer вместо thenReturn.