🧠 Метод двух указателей: как найти пару чисел с нужной суммой

Задача: в массиве, отсортированном по возрастанию, найти два числа, сумма которых равна заданному числу. На собеседовании она звучит как продолжение Two Sum: что изменится, если массив уже отсортирован?

Для примера возьмём массив 1, 3, 4, 6, 9, 11 и будем искать сумму 13.

Можно перебрать все пары и проверить каждую, но это медленно: в массиве из тысячи чисел почти полмиллиона пар, а в массиве из миллиона чисел около полутриллиона.

Метод двух указателей находит ответ за один проход. Указателем здесь называют обычную переменную, в которой хранится номер позиции в массиве. Левый указатель ставим на первое число, самое маленькое, а правый на последнее, самое большое. На каждом шаге складываем два числа под указателями. Если сумма меньше нужной, сдвигаем левый указатель на одну позицию вправо, к большим числам. Если сумма больше нужной, сдвигаем правый указатель на одну позицию влево, к меньшим. Если сумма совпала, пара найдена.

Пройдём по примеру. Сначала складываем 1 и 11, получается 12, это меньше 13, поэтому левый указатель переходит на 3. Числа 3 и 11 дают 14, это уже больше, и правый указатель переходит на 9. Числа 3 и 9 дают 12, снова мало, и левый указатель переходит на 4. Наконец, 4 и 9 дают ровно 13. Пара найдена за четыре шага.

Почему метод не пропускает ответ? Возьмём момент, когда сумма оказалась меньше нужной. Правое число в этот момент самое большое из всех, что ещё остались. Если даже вместе с ним левое число не набирает нужную сумму, то с любым меньшим числом оно не наберёт её тем более. Значит, у левого числа пары нет, и его можно больше не рассматривать. Когда сумма больше нужной, рассуждение такое же, только пары нет у правого числа.

Каждый шаг отбрасывает одно число, поэтому шагов не больше, чем чисел в массиве: для миллиона чисел это не больше миллиона шагов вместо полутриллиона пар. Дополнительная память почти не нужна, хватает двух переменных.

На Java это выглядит так:

static int[] findPair(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left < right) {
        long sum = (long) numbers[left] + numbers[right];
        if (sum == target) {
            return new int[] {left, right};
        }
        if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[0];
}

Метод возвращает номера позиций двух чисел. Сумму считаем в типе long. Если в массиве есть числа, близкие к наибольшему значению int, их сумма в типе int может переполниться и стать отрицательной, и тогда указатель сдвинется не в ту сторону. Если пары в массиве нет, указатели встретятся, цикл закончится, и метод вернёт пустой массив.

Тот же приём помогает проверить, читается ли строка одинаково слева направо и справа налево, а ещё на нём построены известные задачи о контейнере, в который помещается больше всего воды, и о тройках чисел с нулевой суммой. На собеседовании стоит объяснить вслух, почему сдвиг указателя не теряет ответ: именно это рассуждение доказывает, что решение верное.

tags: #алгоритмы #java #собеседование

👉 Гайды с вопросами с собесов, книга по алгоритмам, шпаргалки, гайды на заказ, подгон резюме — в @Java Jub Pro

📱 Java Jub

🎯 Гайд: Senior Java · Музыкальные рекомендации · VK

🔗 Откликнуться: team.vk.company/vacancy/54790/

❗️Новый формат гайда — подробно о нём в следующем посте.

Вопросы обновил: в основе — 34 вопроса с недавних реальных собесов на эту позицию (по фидбэку прошедших). Их меньше, чем в прошлых гайдах (там бывало 200–380), но каждый разобран вглубь: другие формулировки и что спросят следом.

📊 Как проходит собес
➡️ 3–4 встречи, техническая — около 1,5 часа
➡️ Ядро — сервис с хранилищем в памяти, который разбирают до продакшена
➡️ Теория цепочками: от «что такое куча» до «как выключить GC»
➡️ Spring и Kafka — уже на встрече с командой

📄 Что внутри
➡️ 96 страниц, 13 тем, 54 вопроса с разбором
➡️ Ответ вслух на 30–40 секунд + лестница уточнений Middle → Senior
➡️ 18 задач:
➖ 6 алгоритмических и 3 live-coding
➖ 3 на анализ кода и 3 SQL
➖ 3 System Design: «Микс дня» за 150 мс, A/B-тест
➡️ Эталоны прогнаны тестами, 109 фактов сверены с документацией — с учётом Java 27
➡️ Минимум на вечер — 2 ч 22 мин, планы на завтра, 3 дня и неделю
➡️ Репетиция на 90 минут, чек-лист и шпаргалка
➡️ Гарантия: тема не из гайда — разбор за 48 часов, больше трети не из гайда — вернем деньги за него (смотреть подробности в превью и гайде на предпоследней странице)

🤔 Сомневаешься — глянь превью (в боте)👇

👉 Полный гайд и превью — в @Java Jub Pro
━━━━━━━━━━━━━━━━

⏳ ВАЖНО ПРО ДОСТУП
Гайд свежий — а значит, он входит в поток и доступен по любой подписке: месяц, 3 месяца, год.
Но как только выйдут следующие гайды, этот уйдёт в архив. А архив — только на годовой подписке или отдельным заказом.

👉 Хочешь забрать его — сейчас самое время.
━━━━━━━━━━━━━━

📥 Забрать гайд:
https://t.me/java_jub_pro_guides_bot?start=guide_74

⚠️ Один пройденный собес окупит подписку десятки раз. Отзывы (ссылка)

tags: #java #собеседование #senior_guide #vk #москва #гибрид #рекомендации #ml

👉 Гайды с вопросами с собесов, книга по алгоритмам, шпаргалки, гайды на заказ, подгон резюме — в @Java Jub Pro

📱 Java Jub

❗️ С 23 октября гайды выходят в новом формате

Гайд по-прежнему строится вокруг реальных требований компании и вопросов, которые кандидаты слышали на её собеседованиях, но теперь он раскрывает каждый вопрос до конца и готовит ко всему собеседованию целиком. Каждый вопрос с её собеседований за последний полгода разобран и привязан к одной из тем гайда. База пополняется отчётами подписчиков, и по ней я проверяю, что в гайде есть всё, о чём спрашивали.

Разбирая эти отчёты, я заметил одну закономерность. Интервьюеры перефразируют вопросы и после первого ответа задают уточнения. Чаще всего кандидаты теряют уверенность на третьем уточнении, и выученный список вопросов в этот момент уже не помогает. Ещё подписчики просили больше практики, особенно задач с кодом и SQL. Из этого и вырос новый формат. С ним ты заранее знаешь, о чём спросят, и понимаешь, куда интервьюер поведёт разговор дальше.

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

Каждая тема разобрана с тех сторон, с которых о ней спрашивают. Для каждой стороны есть одна или две формулировки в том виде, в каком вопрос обычно звучит на собесе. Так на собеседовании ты узнаешь вопрос, даже если интервьюер задаст его своими словами. Рядом с формулировками стоит короткий ответ, который можно проговорить вслух примерно за сорок секунд. Следом идёт лестница из двух или трёх уточнений, которые обычно задают после первого ответа. На каждой ступени есть ответ уровня Middle и пояснение, что добавит к нему Senior. Закрепить тему помогают задания посложнее исходного вопроса, хотя бы одно из них с кодом, и задачи в формате собеседования с подробным разбором.

Когда ты указываешь дату собеседования, гайд собирает маршрут под оставшееся время. Если собеседование завтра, маршрут займёт до двух часов. Обязательный минимум закрывает не меньше восьми вопросов и проходится за три часа. Перед собеседованием можно пройти репетицию с тем же порядком этапов и тем же временем на каждый из них, и на настоящую встречу ты придёшь уже во второй раз. В последний вечер останется свериться с чек-листом готовности и перечитать шпаргалку на две или три страницы (внутри соответствующего гайда).

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

Новые гайды живут на платформе Jub (выпуск платформы будет 31го октября, до этого в боте), и доступ к ним больше не зависит от Telegram.

Платформа откроется 31 октября, и в этот день я выложу здесь ссылку.

📱 Java Jub

🪤 Ловушка недели: REQUIRES_NEW внутри своего класса

Секция код-ревью, Middle+, банк из топ-10.
Сколько транзакций откроется, когда контроллер вызовет build()?

@Service
public class ReportService {
    @Transactional
    public Report build() {
        return toReport(load());
    }

    @Transactional(propagation = Propagation.REQUIRES_NEW)
    public List<Row> load() {
        return repo.findAll();
    }
}

Голосуй 👇 Разбор завтра.
tags: #ловушка #java #spring

📱 Java Jub

📚 Книга про алгоритмы: короткие ответы перед покупкой

❔Чем она отличается от LeetCode?
На LeetCode тысячи задач, у нас 112 отобранных: 96 с собесов с июня этого года и 16 классических. У задач указано, в каких компаниях встречаются похожие, у Яндекса таких 22, у Сбера 20. В каждом разборе есть, что уточнить у интервьюера до кода и как он развивает задачу после.

❔ А если я читал «Грокаем алгоритмы»?
Там объясняются сами алгоритмы, примеры на Python. У нас задачи с собесов на Java и то, как рассказать решение под таймером.

❔Подойдёт ли Junior?
Да, если знаешь циклы, массивы и коллекции. Начни с маршрута «за выходные»: 15 задач, решения разобраны по строкам.

❔Чем она интересна Senior?
Там есть решения, до которых на собесе обычно не додумываются. Например, своя хеш-таблица на примитивах вместо HashMap или сортировка там, где все сразу пишут HashMap. Замеры JMH в 43 разборах показывают, когда такое решение быстрее.

❔Код есть?
Maven-проект на Java 21: решения всех 112 задач и 384 теста JUnit. Стираешь тело метода, пишешь своё решение и запускаешь тесты главы.

❔Зачем EPUB?
Добавить в книги и читать с телефона. Текст подстраивается под экран.

❔Что делать если собес через неделю, а в книге 862 страницы?
Подряд читать не нужно. В «Карте подготовки» есть маршруты: за выходные 15 задач, за две недели 44 задачи по 3 или 4 в день.

⏳ До конца скидки на книгу осталось 3 дня, она действует до 28 октября включительно. На комплект со шпаргалкой Senior скидка тоже есть, цены в боте

👉 Книга в боте: https://t.me/java_jub_pro_guides_bot?start=guide_69
🎁 Бесплатный фрагмент, разбор Two Sum: https://t.me/java_jub_pro_guides_bot?start=free_70

tags: #java #алгоритмы #собеседование #livecoding

📱 Java Jub

🪤 Задача с собеседования в Уралсиб (вакансия сегодня вечером): два списания одним запросом

Сначала кандидату показывают код, который читает баланс, проверяет его и записывает новое значение (обычно указано findById и save). Кандидат переписывает списание в один запрос, и тогда начинаются уточнения.

На счёте 100 рублей. Две транзакции почти одновременно выполняют такой запрос:

UPDATE accounts
SET balance = balance - 100
WHERE id = 1 AND balance >= 100;

База данных PostgreSQL. Первая транзакция изменила строку и ещё не выполнила COMMIT. Вторая в этот момент доходит до неё. Снимок данных второй транзакции, то есть состояние базы, которое она видит, сделан до коммита первой.

В первом опросе уровень изоляции READ COMMITTED, во втором REPEATABLE READ. Сегодня вечером в гайде объяснение ответов =)

tags: #ловушка #java #postgresql

📱 Java Jub

🎯 Гайд нового формата · Senior Java · Уралсиб

Вопросы обновил и добавил свежие. В основе отчёты кандидатов о собесах в Уралсиб.

📊 Собес идёт час-полтора. Почти всегда будут рассказ о проекте, Spring вглубь, SQL руками и задача про деньги. Больше всего времени, до 20 минут, уходит на транзакции, изоляцию и блокировки. Алгоритмов мало, в конце часто дают чужой код на ревью.

📄 В гайде
➡ 59 вопросов по 13 темам в порядке собеса
➡ к каждому ответ вслух до 40 секунд и подробный разбор
➡ 131 уточнение «что спросят следом» с ответами уровня Middle и Senior
➡ минимум за 2 часа, если собес завтра
➡ 18 задач: деньги и конкурентность, ревью кода, SQL, алгоритмы, API и System Design
➡ репетиция собеса на 90 минут и шпаргалка
➡ 121 страница

Пришлёшь отчёт о собесе с темой, которой нет в гайде, разберу её за 48 часов.

🤔 Сомневаешься — глянь превью (в боте)👇

👉 Полный гайд и превью — в @Java Jub Pro
━━━━━━━━━━━━━━━━

⏳ ВАЖНО ПРО ДОСТУП
Гайд свежий — а значит, он входит в поток и доступен по любой подписке: месяц, 3 месяца, год.
Но как только выйдут следующие гайды, этот уйдёт в архив. А архив — только на годовой подписке или отдельным заказом.

👉 Хочешь забрать его — сейчас самое время.
━━━━━━━━━━━━━━

📥 Забрать гайд:
https://t.me/java_jub_pro_guides_bot?start=guide_75

⚠️ Один пройденный собес окупит подписку десятки раз. Отзывы (ссылка)

tags: #java #собеседование #senior_guide #уралсиб #банки #финтех #новыйформат

👉 Гайды с вопросами с собесов, книга по алгоритмам, шпаргалки, гайды на заказ, подгон резюме — в @Java Jub Pro

📱 Java Jub

// рекомендации

Пока основной канал был заблокирован, мы во временном канале отбирали ребят на рекомендации в компании. Одних кандидатов мы рекомендовали по реферальным программам. Других предлагали напрямую в конкретные компании по договорённости, и их резюме попадало к команде без первичного отбора у HR. На скрине пост из начала октября с вакансиями, под которые мы тогда вели кандидатов.

📊 За это время мы провели больше 70 технических собеседований, и кандидатов было намного больше. Шесть человек мы уже направили по рекомендациям. Резюме некоторых из них сейчас рассматривают, а некоторые уже прошли первые собеседования.

📝 Почти у всех мы видели похожие проблемы с резюме и его оформлением:
• у мест работы не указаны годы;
• не названы компании;
• в резюме попали не все инструменты, с которыми человек работал;
• не написано, что конкретно кандидат делал сам.

Как оформить резюме, мы подробно разобрали в бесплатном гайде «Резюме Java-разработчика: пройти ATS». Загляни в него, прежде чем подавать кандидатуру в следующий раз.
🎁 Гайд в боте: https://t.me/java_jub_pro_guides_bot?start=guide_47

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

⚠️ Рекомендация бесплатная. Оффер мы гарантировать не можем, потому что дальше все зависит от вам на собеседованиях в компаниях.

tags: #рекомендации #резюме #java #собеседование

━━━━━━━━━━━━━━
Осталось около 24 часов до окончания скидки на книгу

👉 Книга в боте: https://t.me/java_jub_pro_guides_bot?start=guide_69
🎁 Бесплатный фрагмент, разбор Two Sum: https://t.me/java_jub_pro_guides_bot?start=free_70

📱 Java Jub

⏳ Сегодня последний день скидки на книгу «Алгоритмы на Java-собеседовании»

➡️ Фрагмент из книги, которого нет в бесплатной части:

Задача 10.1 посвящена бинарному поиску. Его можно написать по массиву int[] или по списку ArrayList<Integer>, и на собеседовании часто спрашивают, какой вариант быстрее.

Мы проверили это замером JMH, это инструмент для точных замеров производительности в Java. На 100 000 элементов поиск по int[] занимает 84 наносекунды, а поиск по ArrayList<Integer> занимает 127 наносекунд. Из 43 наносекунд разницы 41 приходится на чтение объектов Integer. В int[] число лежит прямо в массиве. В ArrayList лежит ссылка на объект, поэтому на каждом шаге поиска процессор читает сначала ссылку, а потом сам объект. Проверка индекса внутри метода get почти не влияет на результат.

Такие замеры есть в 43 разборах книги. После них ты можешь ответить интервьюеру, какое решение быстрее и по какой причине.

🕙Скидка действует до 28 октября включительно, то есть до конца сегодняшнего дня (00:00 по Мск.). Завтра цена книги вырастет. Скидка есть и на комплект книги со шпаргалкой Senior, а подписчикам Pro книга обходится ещё дешевле.

👉 Книга в боте: https://t.me/java_jub_pro_guides_bot?start=guide_69
🎁 Бесплатный фрагмент, разбор Two Sum: https://t.me/java_jub_pro_guides_bot?start=free_70

tags: #java #алгоритмы #собеседование #livecoding

📱 Java Jub