👀 Задача с собеса: Поиск наибольшей общей подпоследовательности (LCS) (mid+)

Найдите длину наибольшей общей подпоследовательности (LCS) двух строк:

— Даны две строки A и B.
— Нужно найти длину наибольшей общей подпоследовательности между ними.

▪️ Условия

1. Строки могут быть длиной до 1000 символов.
2. Используйте динамическое программирование для решения.
3. Подсчитайте длину LCS.

💡 Ключевые моменты

— Используйте таблицу для хранения промежуточных результатов.
— Если символы в строках совпадают, то прибавляйте 1 к предыдущему значению. Если не совпадают — выбирайте максимум из предыдущих значений.
— Убедитесь, что алгоритм работает с большими строками за время O(n*m), где n и m — длины строк.

💬 Возможная реализация в комментариях. Пишите свои варианты и обсудим разные подходы.

🐸 Библиотека собеса по Java

💬 Обратная связь

Как вы относитесь к формату постов в канале?

🔥 — Удобно, интересно
🤔 — Нейтрально
😁 — Неудобно (предложу что-то в комменты)

🐸 Библиотека собеса по Java

❓ Что делает аннотация @Entity?

Аннотация используется для обозначения класса как сущности, которая будет сопоставлена с таблицей в базе данных при использовании JPA (Java Persistence API). Класс, помеченный этой аннотацией, становится частью модели данных, и каждый его экземпляр будет соответствовать строкам в базе данных. Также важно, чтобы такой класс имел конструктор без параметров и корректно определял идентификатор сущности с помощью аннотации @Id.

🐸 Библиотека собеса по Java

❓ Для чего нужны профили в Spring?

Профили используются для того, чтобы разделить конфигурацию приложения в зависимости от различных сред (например, development, testing, production). Это позволяет гибко настраивать приложение для разных условий, активируя или деактивируя определенные бины, конфигурации и зависимости в зависимости от активного профиля. Профили помогают избежать жесткой привязки к среде, упрощая тестирование и развертывание приложения.

🐸 Библиотека собеса по Java

❓ Что делает аннотация @Transactional в Spring?

@Transactional управляет транзакцией на уровне метода или класса. При вызове метода Spring открывает транзакцию, выполняет код, а затем:

если метод завершился успешно — транзакция коммитится
если возникло непроверяемое (runtime) исключение — транзакция откатывается

Также можно тонко настроить поведение (какие исключения приводят к rollback, изоляцию транзакции, propagation и т. д.). В итоге эта аннотация упрощает работу с транзакциями: разработчик пишет бизнес-логику, а управление транзакциями берет на себя Spring.

🐸 Библиотека собеса по Java

❓ Что такое optimistic и pessimistic locking?

Optimistic locking — подход, при котором предполагается, что конфликты редки. Обновление данных проверяется через версионное поле (например, @Version в JPA). Если два потока изменяют одну запись, тот, кто сохраняет изменения вторым, получит ошибку OptimisticLockException. Это дешево по ресурсам, но требует обработки ошибок при конфликте.

Pessimistic locking — «жесткая блокировка»: при чтении или изменении данных сразу ставится блокировка на строку или таблицу (SELECT ... FOR UPDATE). Другие транзакции ждут, пока блокировка не освободится. Это надежнее в сценариях с высокой конкуренцией, но дороже по производительности и может приводить к дедлокам.

👉 На практике выбор зависит от нагрузки: при редких конфликтах лучше optimistic, при частых — pessimistic.

🐸 Библиотека собеса по Java

❓ Что такое deadlock?

Deadlock (взаимная блокировка) возникает, когда несколько потоков удерживают разные ресурсы и при этом ждут освобождения ресурса, который заблокирован другим потоком. В итоге ни один поток не может продолжить работу.

Например: поток А захватил ресурс 1 и ждёт ресурс 2, а поток B — наоборот. JVM их не прерывает автоматически, и система может «замёрзнуть». Чтобы избегать deadlock, используют единый порядок захвата ресурсов, таймауты блокировок или более высокоуровневые примитивы (java.util.concurrent).

🐸 Библиотека собеса по Java

❓ Что такое livelock?

Livelock (живая блокировка) — ситуация, когда потоки не «зависают» в жёсткой блокировке, но бесконечно меняют своё состояние, мешая друг другу завершить работу.

Классическая аналогия: два человека встречаются в узком коридоре, оба вежливо делают шаг в сторону, но одновременно — и так продолжается бесконечно. В коде это проявляется, когда потоки постоянно реагируют на изменения друг друга, но никто не достигает цели.

🐸 Библиотека собеса по Java

💬 Обратная связь

Хотели бы видеть в канале теги для навигации? Если большинство будет За, попробуем в тестовом формате.

🔥 — Да, введите теги по уровню вопроса
👍🏼 — Да, введите теги по теме вопроса
❤️ — Да, предложу в комменты идею для тегов
😁 — Всё равно, особых плюсов не вижу

🐸 Библиотека собеса по Java

❓ Что такое starvation?

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

Например, если один поток работает с высоким приоритетом, а другой — с низким, второй может почти не выполняться. В Java это чаще всего связано с неправильным использованием синхронизации или очередей, где один поток постоянно перехватывает ресурсы. Решение — справедливые блокировки (ReentrantLock(true)), балансировка нагрузки, корректные политики планировщика.

🐸 Библиотека собеса по Java

❓ В чём разница между дизайном и архитектурой ПО?

Архитектура — это высокоуровневое видение системы: какие модули есть, как они взаимодействуют, какие протоколы и технологии выбраны. Это про стратегические решения, которые трудно менять.

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

🐸 Библиотека собеса по Java

❓ Что делает аннотация @Test в JUnit5?

Аннотация @Test помечает метод как тестовый. Такой метод будет автоматически выполнен фреймворком JUnit при запуске тестов.
В JUnit 5 можно также использовать дополнительные аннотации (@BeforeEach, @AfterEach и др.) для настройки окружения, но @Test — базовый маркер, что это именно тест.

🐸 Библиотека собеса по Java

#tests

❓ Что такое Java Memory Model и зачем он нужен?

Java Memory Model (JMM) описывает, как потоки взаимодействуют через память и какие гарантии по видимости и упорядоченности операций даёт JVM.

Без JMM многопоточные программы работали бы непредсказуемо: один поток мог бы не увидеть изменения другого. JMM определяет правила: когда изменения в кэше процессора становятся «видимыми» другим потокам, и как работает синхронизация.

🐸 Библиотека собеса по Java

#concurrency

❓ Что такое "diamond problem" и как его решает Java?

«Diamond problem» возникает при множественном наследовании, когда класс может унаследовать одну и ту же реализацию от разных родителей.
В Java классы не поддерживают множественное наследование, а только интерфейсы позволяют такое. Если два интерфейса имеют одинаковый default-метод, то компилятор потребует явного переопределения в классе. Это и есть решение проблемы.

🐸 Библиотека собеса по Java

#tests

👀 Задача с собеса: «Single-flight» объединение запросов к внешнему API (middle+)

Компания ловит шторма трафика: десятки потоков одновременно дергают один и тот же медленный эндпоинт (например, профили клиентов). Хотят убрать дубликаты запросов и снизить нагрузку на апстрим. Задача:

Реализуйте in-memory «single-flight» слой, который:

— Для одного и того же ключа выполняет ровно ОДНУ загрузку, остальные ожидают тот же результат.
— Имеет короткоживущий кэш (TTL) для защиты от штамповки (cache stampede).
— Потокобезопасен и работает за O(1) на обращение (без полных проходов).
— Прозрачно пробрасывает исключение всем конкурентным ожидателям, если загрузчик упал.

▪️ Условия

— API: CompletableFuture<V> getOrLoad(K key, Supplier<V> loader) (или Supplier<CompletableFuture<V>>, если загрузка уже async).

— Если в кэше есть не сгоревший ключ, вернуть немедленно. Если нет — запустить единственную загрузку на ключ и раздать один и тот же Future всем конкурентным вызовам.

— По завершении загрузки положить результат в кэш с expireAt.

— Удаление сгоревших записей ленивое (на чтении/записи), без фоновых сканеров.

— Критические секции минимальные; без глобальных блокировок.

💡 Ключевые моменты

— Объединение запросов: ConcurrentHashMap<K, CompletableFuture<V>> inFlight + computeIfAbsent исключит дубликаты.

— Кэш: ConcurrentHashMap<K, Entry<V>> cache, где Entry хранит value и expireAt.

— TTL: проверка сроков строго точечная; протухшее удаляем перед использованием.

— Ошибки: один промах/ошибка должны одинаково прилететь всем конкурентным ожидающим.

— Производительность: никакой синхронизации на весь объект; один ключ — одна «тонкая» операция.

💬 Возможная реализация в комментариях. Пишите также ваши реализация и способы оптимизации.

🐸 Библиотека собеса по Java

#practice