❗️Задача для конкурса в честь дня программиста

Условие:

Даны две строки s и f (начальная и конечная) и словарь D (набор слов).

Нужно определить, можно ли преобразовать s в f, используя только слова из словаря D. При этом каждое преобразование должно менять только один символ, а длина слова должна оставаться неизменной. Если преобразование возможно, нужно найти кратчайшую последовательность таких преобразований и вернуть ее длину. Если преобразование невозможно, вернуть "Преобразование невозможно".

Пример ввода 1:

    D = ["cat", "cot", "dot", "dog", "bat", "dag"]
    s = "cat"
    t = "dog"

Вывод:
Минимальное количество шагов для преобразования 'cat' в 'dog': 3

Пример ввода 2:

    D = ["cat", "cot", "bat"]
    s = "cat"
    t = "dog"

Вывод:
Минимальное количество шагов для преобразования 'cat' в 'dog': Преобразование невозможно

❓ Как работает AtomicInteger?

AtomicInteger — это класс из пакета java.util.concurrent.atomic, который обеспечивает атомарные операции над целыми числами. Он используется в многопоточных средах без явной синхронизации.

Ключом к потокобезопасности является механизм CAS (Compare-And-Swap), который сравнивает текущее значение переменной с ожидаемым и заменяет его на новое, если значения совпадают. Это предотвращает состояние гонки, так как только один поток может успешно завершить операцию, а остальные будут повторять попытки.

Механизм CAS (Compare-And-Swap):

Представьте, что два потока одновременно пытаются увеличить значение переменной:

Поток A читает значение 10.
Поток B тоже читает значение 10.
Поток A увеличивает значение до 11 и с помощью CAS заменяет 10 на 11.
Поток B пытается сделать то же самое, но так как его ожидаемое значение было 10, а сейчас уже 11, CAS не позволяет ему выполнить замену, и поток B повторяет операцию.

В отличие от блокировок (synchronized), AtomicInteger не блокирует потоки, что делает его более быстрым в условиях параллелизма.

❓ Что делает метод Thread.yield()?

Метод yield() — это статический метод класса Thread, который даёт возможность текущему потоку «уступить» своё время процессора другим потокам того же приоритета. Когда поток вызывает этот метод, он переходит в состояние готовности (runnable) и ждёт, пока планировщик потоков вновь даст ему доступ к CPU. Важно отметить, что вызов yield() — это лишь рекомендация, а не обязательное действие для планировщика потоков, и его поведение зависит от реализации JVM.

❓ Что такое монолит?

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

🔹 Ключевые особенности:
▪️ Единая кодовая база.
▪️ Центральная точка развертывания.
▪️ Тесная взаимозависимость модулей.
▪️ Масштабируется как единое приложение.

🔹 Плюсы:
▪️ Простота разработки на начальных этапах.
▪️ Легко управлять одной кодовой базой.
▪️ Отсутствие необходимости в сложной инфраструктуре.

🔹 Минусы:
▪️ Сложность масштабирования по частям.
▪️ Высокая связанность увеличивает риски при изменениях.
▪️ Затруднена разработка и развертывание отдельных компонентов.

ℹ️ Как устроен под капотом ArrayList?

ArrayList — это реализация динамического массива в Java. Он базируется на массиве, который может изменять свой размер по мере добавления элементов.

🔹 Массив как основа
В основе ArrayList лежит массив типа Object[]. Этот массив инициализируется с начальной емкостью (по умолчанию 10, если не указано иное).

🔹 Динамическое изменение размера
Когда добавляется элемент, а текущий массив заполнен, ArrayList расширяет массив, создавая новый с увеличенной емкостью — обычно это 1.5x от текущего размера. Старые данные копируются в новый массив с помощью System.arraycopy.

🔹 Добавление элементов
▪️ В среднем: добавление элемента занимает O(1), потому что в большинстве случаев просто добавляется новый элемент в конец массива, без необходимости его увеличения.
▪️ В худшем случае: добавление элемента может занять O(n), потому что, если внутренний массив переполняется, ArrayList вынужден создать новый массив большего размера и скопировать в него все существующие элементы.

🔹 Удаление элементов
При удалении элемента сдвигаются все последующие элементы на одну позицию влево, что приводит к сложностям:
▪️ Удаление по индексу: O(n) в худшем случае (сдвиг элементов после удаленного).
▪️ Удаление последнего элемента: O(1).

🔹Преимущества и недостатки

▪️ Преимущества: Быстрое добавление в конец, быстрый доступ по индексу O(1).
▪️ Недостатки: Медленное удаление или вставка в середине массива O(n), особенно при работе с большими коллекциями.

❓ Что такое bytecode?

Bytecode — это набор инструкций, которые виртуальная машина Java (JVM) использует для выполнения программ. При компиляции Java-код, не превращается сразу в машинный код, а сначала в bytecode. JVM переводит этот bytecode в машинный код уже во время исполнения программы, что делает Java независимой от платформы — один и тот же байт-код может быть выполнен на любой системе, где есть JVM.

⚙️ Этот подход позволяет добиться переносимости Java-приложений на различные операционные системы без изменения исходного кода.

❓ Какая разница между java.util.Collection и java.util.Collections?

🔵 java.util.Collection — это интерфейс, который является основой для всех коллекций в Java. Он определяет общие методы, такие как add(), remove(), size(), и служит для работы с коллекциями объектов. Реализуется такими классами, как ArrayList, HashSet и другими.

Когда нужно работать с базовыми операциями коллекций — добавление, удаление, проверка размера и т. д.

🔵 java.util.Collections — это утилитарный класс, который предоставляет набор статических методов для работы с коллекциями. Эти методы позволяют сортировать коллекции, синхронизировать их или возвращать неизменяемые версии коллекций.

Когда нужно выполнять операции над коллекциями, такие как сортировка, синхронизация или создание неизменяемых коллекций.

🚀 Главное отличие:

Collection — это интерфейс, определяющий поведение коллекций.
Collections — это класс, предоставляющий вспомогательные методы для работы с коллекциями.

🙌 Хардкорный вышмат для тех, кто интересуется ML, AI, DS

Начать с вводных занятий можно здесь, ответив всего на 4 вопроса – https://proglib.io/w/12f47906

Что будет на демо?

🔹Вводный урок от CPO курса;

🔹Лекции со всеми преподавателями МГУ по темам: теория множеств, непрерывность функции, основные формулы комбинаторики, матрицы и операции над ними, градиентный спуск;

🔹Практические задания и дополнительные материалы!

⚡️Переходите и активируйте – https://proglib.io/w/12f47906

❓ Что такое Unit Tests?

Unit-тесты — это тесты, которые проверяют работу отдельных, минимальных единиц кода (обычно это отдельные методы или классы). Они помогают убедиться, что каждый модуль работает корректно в изоляции от других.

Ключевые особенности:

🧩 Изоляция: Unit-тесты должны быть независимы от внешних зависимостей, таких как базы данных или сетевые запросы. Для этого используются такие техники, как mocking (например, с помощью Mockito).
🚀 Быстрота выполнения: Unit-тесты должны выполняться быстро. Если тест медленный, это признак, что он может быть слишком сложным или зависим от внешних ресурсов.
🔄 Покрытие кода: Основная цель unit-тестов — максимальное покрытие ключевой логики программы, но не за счёт избыточности. Правильный баланс между покрытием и поддерживаемостью критически важен.

ℹ️ Как устроен под капотом HashSet?

HashSet — это реализация множества (set), которое не допускает дублирующихся элементов. В его основе используется механизм хеширования для быстрого поиска, добавления и удаления элементов.

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

🔹 Хеширование
Когда вы добавляете элемент в HashSet, для него вычисляется хеш-код с помощью метода hashCode(). Этот хеш-код помогает определить, в какую "корзину" (bucket) поместится элемент. Если два элемента имеют одинаковый хеш-код (коллизия), они будут помещены в один и тот же бакет, и далее будут различаться с помощью метода equals().

🔹 Коллизии и структура бакета
До Java 8, если в бакет попадало несколько элементов (коллизия), они сохранялись в виде односвязного списка. Это приводило к тому, что в худшем случае производительность поиска и добавления элементов могла падать до O(n), если список становился слишком длинным.

С Java 8 при превышении 8 элементов в одном бакете, односвязный список преобразуется в красно-чёрное дерево, что улучшает производительность операций до O(log n). Когда количество элементов в бакете падает ниже 6, структура снова преобразуется обратно в связанный список для экономии памяти.

🔹 Добавление элементов
▪️ В среднем: добавление элемента занимает O(1), потому что благодаря хеш-кодам можно быстро находить нужную корзину для элемента.
▪️ В худшем случае: добавление элемента может занять O(n) до Java 8 (связный список) и O(log n) начиная с Java 8 (красно-чёрное дерево).

🔹 Удаление элементов
Удаление происходит также через хеш-код: ищется соответствующая корзина, а затем элемент удаляется, если он там есть. Сложность удаления аналогична добавлению: O(1) в среднем и O(n) или O(log n) в худшем случае (в зависимости от структуры бакета).

🔹 Преимущества и недостатки

▪️ Преимущества: Быстрое добавление, удаление и поиск элементов в среднем за O(1), так как используется хеширование. Улучшенная производительность с Java 8 благодаря использованию красно-чёрного дерева.
▪️ Недостатки: Не гарантирует порядок элементов, а при частых коллизиях, особенно в старых версиях Java, производительность может падать до O(n).

❓ Что такое this?

this — это ключевое слово в Java, которое ссылается на текущий объект внутри его метода или конструктора.

Важно: в static методах и контексте нельзя использовать this, так как они не привязаны к конкретному экземпляру класса.

ℹ️ Что такое состояние гонки

🏎 Состояние гонки (Race Condition) — это ситуация, когда несколько потоков одновременно получают доступ к общему ресурсу без должной синхронизации. В результате поведение программы становится непредсказуемым, так как порядок выполнения потоков может влиять на конечный результат.

Пример:

public class RaceConditionStringBuilder {
    public static void main(String[] args) throws InterruptedException {
        StringBuilder sb = new StringBuilder(); // Общий ресурс

        Runnable task = () -> {
            for (int i = 0; i < 10000; i++) {
                sb.append("A"); // Несинхронизированный доступ
            }
        };

        Thread t1 = new Thread(task);
        Thread t2 = new Thread(task);

        t1.start();
        t2.start();

        t1.join();
        t2.join();

        System.out.println("Result length: " + sb.length());
    }
}

👀 Что происходит?

▪️ Два потока одновременно добавляют символ "A" в один и тот же StringBuilder объект. Поскольку StringBuilder не является потокобезопасным, возможны ошибки, такие как потеря данных или некорректные результаты.

▪️ Потоки не знают о действиях друг друга. Если два потока одновременно читают строку длиной 500, каждый добавляет свой символ "A", а затем оба записывают новую строку с длиной 501, одно добавление теряется. Это и есть состояние гонки — результат зависит от того, как потоки "успеют" выполнить свои операции.

▪️ Ожидаемая длина строки — 20000, но на практике результат может быть меньше.

🛠 Как исправить?

🔵 Использовать StringBuffer, который синхронизирован и потокобезопасен.
🔵 Синхронизировать доступ к StringBuilder вручную:

synchronized(sb) {
    sb.append("A");
}

ℹ️ Какие есть способы создания объекта String?

▪️ Литерал строки:

Это наиболее распространённый способ. При создании строки с помощью литерала, объект помещается в String Pool, и если строка уже существует в пуле, то повторное создание этой строки не происходит.

String str1 = "Hello";

▪️ Конструктор класса String:

Создание строки с использованием оператора new. При этом всегда создаётся новый объект в памяти, даже если строка уже существует.

String str2 = new String("Hello");

▪️ Метод valueOf():

Этот метод преобразует аргумент в строку. Например, передавая число или другой тип данных, он вернёт строковое представление.

String str3 = String.valueOf(123);

❓ Можно ли переопределить метод toString() для Enum?

Да, можно переопределить метод toString() в Enum так же, как и в любом другом классе. По умолчанию toString() для Enum возвращает имя перечисления (то, что задано при объявлении). Однако, если вам нужно вернуть другое значение, вы можете переопределить этот метод в вашем перечислении.

Например, если переопределить toString(), можно для Day.MONDAY.toString() получить "Понедельник", вместо "MONDAY".

Пример в комментариях.