Гонял мой кореш тут недавно на собес

Дали офигательную задачку! В которой нужно самому подумать, а не вспомнить какой-то хитрый метод...

Дан массив строк со знаками + * и числами — нужно вычислить значение

НО!

Сделать это нужно за O(1) по дополнительной памяти

---

Бился он с ней минут 30 и таки решил, потом после собеса сказал мне, что еле решил и чёт прям громоздко у него получилось

А решение всего на +-10 строк

from typing import List

def calculate(s: List[str]) -> int:
    result = 0
    prev_multiply = int(s[0])
    
    for i in range(1, len(s), 2):
        if s[i] == "*":
            prev_multiply *= int(s[i + 1])
        elif s[i] == "+":
            result += prev_multiply
            prev_multiply = int(s[i + 1])
    result += prev_multiply    
    return result

Тут главная фишка в prev_multiply

Если скажем пример 1*2*3+4+5*6, то он будет принимать такие значения: 6, потом 4, потом 30

И при каждом обновлении добавляет всё в result

Вот и получаем 6 + 4 + 30 = 40

А внутри цикла проходимся по нечетным позициям только, потому что там всегда стоят знаки

---

Получилась классика жанра — кореш видит решение и всё очевидно, но на собесе наговнокодил 😂

В то же время интервьюер: дает одну и ту же задачу и 80% гавнокодят

Вот такой круговорот ..кода в природе

P.S. Го соберем 50 🌭 по фану)

Набор в группу подготовки к собесам

Что делаем:
- Даём свежие задачи с реальных собеседований
- Ты решаешь → ревью → доводим решение до эталонного
- Созвоны в мини-группах по 3-4 человека

Пример задач, которые решаем:
- Backend
- ML
(В основном решаем задачи с новой секции Яндекса - Advanced Code и от VK - там похожая секция есть)

Кто ведёт:
- Cross review делают Middle+ разработчики из группы
- Группу лидит Senior+

Бонусы:
- Премиум на algocode.io на время участия (+ задачи в раннем доступе)
- Консультации по карьере / System Design / алгоритмам
- Если ты в Москве — офлайн-сходки раз в месяц

Условия:
Бесплатно. Мы собираем группу сильных разработчиков — за счёт этого cross review получается качественным. Вы обмениваетесь экспертизой и готовитесь к собесам, а мы добавляем разобранный контент на платформу. Win-win

———

Отзыв от Саши:

Тебе, Макс, отдельное спасибо, что делаешь классную платформу и за возможность в этом поучаствовать, а также что собрал и организовал нас) Для меня участие было полезным, для себя я выполнил свои цели на 100%)) 1. не просел навык по Go после рута; 2. занетворкал; 3. сменил работу на Бигтех)

Отзыв Алекса:

Я же как раз к Яндексу готовился, поэтому отозвался. Прикольные задачки теперь решаю, прокачиваюсь потихоньку. Ревьюил ты вначале детально, накидывал много, я тогда хорошо многопоточку подтянул. Просто приятная небольшая компания у нас собралась.

———

Кого ищем:
- Middle+ с продакшен-опытом
- Есть опыт прохождения собесов
- Желание прокачивать многопоточку (для backend направлений) - много задач с ней решаем
- 4-5 часов в неделю на подготовку

Направления (можно выбрать любое):
- Golang
- C++
- ML
- Python
- C#

———

👉 Если интересно
Пиши @SleeplessChallenger — пришлём мини-тестовое

Если что-то не понял, то уточнить так же можно у @SleeplessChallenger (отвечает в течении дня)

Как алгоритмы сделали меня богатым

Первую работу я получил с трудом - это была локальная конторка в Нижнем Новгороде и на собесе они отметили мои знания по алгосам и решили меня взять

Радость была нереальная!

Но больше всего мне хотелось в BigTech - посмотреть на процессы, на крутых чуваков - и тогда я пособесился в Huawei и прошел!

Мне дали задачку на графы: до сих пор помню ее

Нужно было посчитать число компонент связности и я решил ее и через DFS и BFS и еще оптимизации всякие порассказывал

Оффер прислали моментально!

И еще год я был в R&D команде, где разрабатывали параллельный алгоритм поиска критического пути на графах

Ну а потом Яндекс!

Никогда не забуду - было 3 алго-собеса и на всех я разваливал 2 задачки за 30-40 минут и всегда оставалось время - которое я всегда тратил на одно: поболтать с интервьюером про Яндекс

А через год Т-Банк

И снова алго-секция пройдена лучше всего. Помню, еще сокомандник пришел и сказал:

видел у тебя за секцию Senior стоит - красавчик!

В общем, в начале своей карьеры я сделал ставку на алгоритмы и не пожалел - я получил офферы от всех компаний где мечтал работать (от Авито и заканчивая Яндексом)

Именно так и появилось сообщество algocode.io - я подумал, что могу передать свой опыт другим ребятам

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

Да, я стал зарабатывать меньше, но буквально вчера прилетел очередной отзыв в ЛС

Макс, привет, хотел сказать тебе спасибо за твою платформу - подготовка реально приносит результат! В пн проходил алго-собес - решил 2 задачи из 2 за 33 минуты. Буду рекомендовать ребятам кто так же захочет в бигтех👍

Но после такого не считаю, что стал беднее ни на грамм

2 задачи за 33 минуты - да он на 7 минут меня обогнал когда я в Яндекс собесился 😂 - просто красавчик!

Прям ностальгия накатила

В общем, я занимаюсь любимым делом, которое меня заряжает и считаю, что у каждого оно должно быть

А то как выжить во времена банковской ставки >10%

Все нервы ни к черту будут

Пеп, фа - как я провалил алго-секцию в Яндекс:

У меня было две попытки трудоустройства в красную компанию со стульями Herman Miller

Первый раз - самый лютый факап

Пришел на собес и было 2 задачи: первая сжать последовательность вида ([1,2,3,5,8,9] в "1-3,5,8-9")

Ее я щелкнул минут за 20

А вот вторая - лютейшая тогда для меня задачка на BST (бинарное дерево поиска)

Дан корень бинарного дерева. Нужно проверить, является ли дерево правильным бинарным деревом поиска.

8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13

Тут ответ будет true - все элементы в левом поддереве меньше текущего, а в правом - больше текущего

Например: 6-ка в левом поддереве 8 и в правом у тройки, значит 3 < 6 < 8

То что я там нагородил было вообще немыслимо - я хотел зафигачить итеративную реализацию

Бился я минут 40, пока интервьюер просто на меня смотрел и особо ничего не говорил

Я то рассказывал вслух, то молчал минут по 5-10

Он просто смотрел...

А когда время кончилось ушел... 😂
---

Я после собеса полетел сразу смотреть: вата фа пеп йоу

Шо за тема деревьев и почему я решаю олимпиадные задачки уже год а ее не встречал

Смотрю на решение а там:

f

rom typing import *
from algocodelib import TreeNode

def is_valid_bst(root: TreeNode) -> bool:
    def is_valid(node: TreeNode, low: int, high: int) -> bool:
        if node is None:
            return True
        if not(low < node.val < high):
            return False
        return (is_valid(node.left, low, node.val) and
               is_valid(node.right, node.val, high))
    return is_valid(root, float("-inf"), float("inf"))

Мое лицо -> 🤡

Решение в пару строк...

Потом буквально за неделю я прорешал задач 50 на leetcode и больше никогда не заваливался на деревьях

Но в тот момент меня могла спасти простая мысль: деревья в 95% случаев решаются рекурсией

И этого было бы достаточно

Именно поэтому первая тема которую добавил на algocode - были деревья
Я просто не хотел чтобы другие так же страдали

Да и стримов я больше всего посвятил деревьям

Вот, кстати, как раз по BST: https://www.youtube.com/watch?v=XGzBKj2HO30

Чтобы как я не опрофанились)

Сколько знаешь способов поменять 2 инта местами?

Способ 1 - нормальный человек
tmp = a
a = b
b = tmp

Способ 2 - учит алгоритмы год
a = a + b
b = a - b
a = a - b

# a = 3, b = 5
# a = 8
# b = 3
# a = 5


Способ 3 - учит алгоритмы с детства
Работает как верхний, но через xor
a = a ^ b
b = a ^ b
a = a ^ b

Способ 4 - бог здравого смысла
a, b = b, a

---

P.S. на собесе пару раз понтовался этим, так что забирай)

На сколько полезен blind75?

blind75 - один из популярных списков задач, с которых советуют начать решать leetcode

Я его сравнил с тем, что спрашивают в Российском Big Tech прямо сейчас и делюсь результатами

3+ RU BigTech сейчас:
- Слияние интервалов (algocode | leetcode)
- Разворот связного списка (algocode | leetcode)

2-ух RU BigTech сейчас:
- Правильная последовательность скобок (algocode | leetcode)
- Удаление с N-ого с конца (algocode | leetcode)
- Поиск в сдвинутом массиве (algocode | leetcode)
- Топ К частых элементов (algocode | leetcode)
- Число островов (algocode | leetcode)
- K-ый наименьший в BST (algocode | leetcode)
- Валидная анаграмма (algocode | leetcode)

И еще 12 задач встречаются в 1 BigTech

Итого: 21/75

В целом, неплохо
---

По последнему тренду заметно, что наши бигтехи придумывают свои задачи

Если раньше все брали из Яндекса, то теперь прям свои делают в основном

Пул задач размывается

Поэтому сейчас фокусируемся с командой на конкретных компаниях и подготовке к собесам ко всем секциям

Вчера буквально закончил задачки Яндекса по алгосам обновлять так что дальше Advanced Code и секция про найм

P.S. активный пул Яндекса прям сужают, но сами задачи уже оригинальные, а не просто с leetcode

Очередь кандидатов в Яндекс длиннее пробки на МКАДе

Сейчас в Яндексе такие тех-секции для backend:
• Advanced code
• Алгоритмы
• System Design
• Tech Deep Dive

Так вот, даже если ты прошёл advanced code — ЖДИ 2–3 НЕДЕЛИ МИНИМУМ чтобы пройти алгосы!

Мне стало интересно, откуда такое явление, и поговорил с корешами оттуда

В общем, такое саммари:

Раньше было 3 алгосекции, и чтобы проводить финальную (3-ю алго-секцию), нужно было проходить доп. обучение и сдавать экзамен

Обучение — до 6 месяцев

А сейчас секция одна, и проводят ее ТОЛЬКО те, кто проводил последнюю и число интервьюеров резко сократилось...

Так что стоять так ещё минимум 3–4 месяца

Ни*уя «Плавающее окно» — это не паттерн!

Характеристики паттерна:
1. Есть явные green flags.
2. Есть чёткая структура кода.
3. Есть типовая Big O.
4. Есть конкретные 1–2 проблемы, над которыми нужно думать, чтобы решить задачу этим паттерном.

Плавающее окно — это тема, в которой есть 3 базовых паттерна:
• плавающее окно фиксированной длины
• непересекающиеся окна
• пересекающиеся окна

Каждый из них имеет такие 4 чёткие характеристики

Если этих характеристик нет - это просто общий подход, но не паттерн

—-

Сейчас готовлю большой видос на YouTube про паттерны по всем темам.

А для ребят из сообщества сделаю эксклюзив — глубокое погружение во всю систему, чтобы с первого сабмита все задачки решали

Самое прикольное во всей системе, которую собираю — это фреймворки

Фреймворк — это простая блок-схема: идёшь по ней, отвечая «да» или «нет», и понимаешь, какой паттерн использовать

В общем, готовлю для вас большое обновление! Скоро будет на YouTube и в сообществе!

Бахни 🌭 - гарантированно ускоряет выход контента!

Всем, кто собесится в Авито, посвящается!

В 2025 году Авито решили не проводить классическую алго-секцию
Теперь у вас НЕ 2 АЛГО-ЗАДАЧКИ, А ЦЕЛЫХ 5

В общем, будут задачки наваливать, пока не начнешь просить пощады или не кончится 60 минут

НО! Зато сами задачи простые

Можно зайти и потренироваться в Avito Code, чтобы прям обстановка была 1 в 1 как на собесе

Ну и подгончик в виде парочки задач

Задача 1
У нас есть статистика по серверам по стабильности в процентах по бейзлайну 9999.
Необходимо вернуть распределение серверов по показаниям.

in: [{server:1, stability:99}, {server:2, stability:97}, {server:3, stability:34}, {server:4, stability:97}, {server:5, stability:97.1}]
out: { '34':[3], '97':[2,4], '99':[1], '97.1':[5] }

type Statistic struct { ServerID int; Stability float32 }

---

Задача 2
Необходимо проверить 2 строки, являются ли они анаграммами.
Если это так — вернуть true, иначе false. Буквы: латиница и кириллица.

in: s="anagram", t="nagaram" → out: true
in: s="кит", t="ток" → out: false

Мне нравится, куда идёт Авито, потому что сам провожу секцию похожим образом, когда нанимаю в algocode, но только я даю 20 задачек, а не 5, но без написания кода

Ставь 🌭, если хочешь больше таких подгонов

P.S. вот накидали лайков на прошлом посте и я реально X2 с видосом ускорился. В начале марта будет на ютубе

Чертова задача! Решаю алго-задачи и забываю... Как не забывать?

100% в детстве ты учил формулу прямой в математике y = k*x + b

Вряд ли ты такой — ну все понятно, пойду ебашить практические задачки

Пришлось посмотреть пару примеров на пальцах

Некоторые объяснялись не один раз

----

Так и тут, бро)

С первого раза ничего не сработает

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

----

Если бы сейчас я забыл все, что знаю в алгоритмах, и у меня был бы месяц для подготовки к собесу в Яндекс, и я должен его пройти или меня повесят

Я бы заперся в бункере со всеми задачами Яндекса с algocode и разбирал бы их по паттернам, тренируя нейронку

Ушатал свой мозг так, чтобы за секунду по условию видел
- паттерн
- ключевую проблему
- типичные оценки сложности
- код

И все это превратил бы в структурированный рассказ интервьюеру

---

Примерно с 4-5 прорешивания задачи я бы вышел на такой уровень, что знал задачи Яндекса лучше самого Яндекса

Так что не думай, что прорешал задачу 1 раз и потом не вспомнил — то все потеряно — еще ничего и не начиналось)

А потом возникнет магия...

Эта база закрепится в голове и новые задачи будут легко на нее настраиваться без особых усилий

Лучшая стратегия торговли за ЗП от моего кореша

Собесился, значит, кореш во ВкусВилл

Приходит ко мне — говорит, Макс, расскажи, как торговаться за ЗП

Ну я ему зачитал голосовых...

Прям методики, конверсии, наработки и вся фигня

ДЕНЬ ФИНАЛА

Приходит после собеса довольный

Говорит, катнули офер и еще +50 000 накинули после того, как поторговался

Я такой: ну рассказывай, что сработало

ОН:

Да я рекрутера попросил, чтобы она за меня поторговалась просто

Тем временем я со всеми своими формулами: 🤡🤡🤡

Как попасть на собеседование в 2026 без накрутки?

Лично я бы так искал работу в 2026, если бы начинал с 0

1) Анализирую LinkedIn нанимающих менеджеров IT-компаний (чтобы при этом у компании в целом были вакансии) и выписываю продукт, которым они занимаются. Задача - найти как можно больше команд, которые делают +- одинаковый продукт

2) Выбираю топ 1 такую группу по числу команд (минимум 5-6 команд чтобы было) и делаю пет-проект за 1.5 недели, который копирует основной функционал

3) Пишу всем чувакам, кто занимается похожими проектами, с просьбой консультации

Письмо примерно такое

"Привет! Я Макс, занимаюсь разработкой сервиса XYZ в учебных целях <ССЫЛКА>. У тебя крутой бэкграунд в этом домене и очень хочу с тобой проконсультироваться по своему проекту. Сможешь помочь?"

Нужно примерно 50 отправок разным чувакам

Целился бы в response rate 5%

и получил бы примерно 2 ответа

4) Задача на созвоне — узнать о возможных улучшениях в системе и архитектурных проблемах + показывать максимальную бицуху свою

Если есть вакансия - 100% позовут на собес, а если не позовут, то получу консультацию, доработаю проект и пойду с ним же к еще более топовым чувакам

---

Есть 2 исхода:
1) меня пригласят на собес, как только в командах откроется вакансия
2) сделаю бизнес в этом домене и просто всех конкурентов нагну (Правда, придется пожить с родителями пару лет 🤡)

Я это к тому, что варианты есть всегда. Тут даже не вся схема, что бы я делал, но я верю, что этого должно быть достаточно

Я верю в это потому, что тут есть WIN-WIN для тебя и работодателя

Все стратегии с такой политикой работали для меня ахуенно на протяжении всей карьеры

Тут нужно вложится временем и конечно это сделаем максимум 1% и именно поэтому это сработает

На 23 февраля пожелаю только самое необходимое

1. Чтобы SLA был крепким как Т-34, а алерты сервиса до тебя не долетали

2. Уже наконец то починить API, чтобы носки все время хранились вместе и не терялись

3. Поменьше трогать клавиатуру, но побольше зарабатывать денег

Ну и бро, афигенно тебе отметить праздник!

Собрал коллекцию про*баных оферов...

Ситуация такая:
• Готовился знакомый к собесу в Озон
• Всё прошёл, выкатили офер
• Ждут его ответа...

Он такой — бля, надо быстрее собеситься. Ещё в пару компаний с трёх ног залетает, проходит секции...

А Озон уже давит
Ну шо, идёшь или нет?

В итоге принял офер на 312 000 от синего маркетплейса

И как только принял сразу Яндекса дал катлету на. 360 000 net

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

Базовая база: но коли уж идёшь — ставь собесы рядом, желательно чтобы одинаковые секции были в одинаковых неделях

А это одна история из 3–4, которые долетают до меня ежемесячно

Ставь 🌭 и запишу курс, как жонглировать мылом и не ронять его)))

А пиздато подготовиться к собесам можно на algocode.io

Когда нужен полный перебор на собеседовании?

Когда начинал учить алгосы, натыкался на видосы c таким тейком

вот предложи решение с полным перебором сначала, а потом оптимизируй

Них*ясебе совет, я вам скажу

Вообще полный перебор — нифига не тривиальная штука, на мой взгляд. Я его понял, когда решил в районе 20–30 задач

Посмотрев на достаточное число задач в этой теме, могу сказать так: если вам нужно генерировать самим все перестановки / прям явно собирать все комбинации и т. д. — это 100% полный перебор (bruteforce) или поиск с возвратом (backtracking)

В остальных случаях ну вот прям не нужен он с 99% вероятностью

bruteforce — это вот прям полный-полный перебор

backtracking — это отсечение вариантов, которые точно дадут неверный результат (в общем, оптимизация)

P.S. Пятница) Надо пати устроить, чтобы быть довольным как чел на фортке, а не про брутфорс и бектрекинг писать

но что есть то есть

Advanced Code — теперь самый жёсткий этап собеса в Яндексе

Формат такой: 60–90 минут, тебе дают production like задачу, ты уточняешь детали у интервьюера — и пишешь код

Причём задача усложняется прямо в процессе. Например:

Есть микросервисная архитектура. Реализуй тип Balancer,
который реализует интерфейс Backend и распределяет запросы
между экземплярами сервиса.

Сначала уточняешь: алгоритм балансировки, concurrency, обработку ошибок. Потом пишешь код...

В конце интервьюер говорит:

А теперь доработай Balancer, чтобы он временно исключал проблемные бэкенды из ротации

Проверяют сразу всё: System Design + live кодинг + умение задавать правильные вопросы

И писать код так чтобы не переписывать его с нуля нафиг при следующем усложнении 🧨

Другие примеры задач:
— обёртка для долгой ресурсоёмкой операции
— буфер для переливки данных из Kafka в ClickHouse
— переливка из OLTP в OLAP
— и ещё десятки похожих

🤙 А это была ахуительно полезная реклама algocode.io

А вот прямая ссылка для тех, кто уже с нами

Если "ДЕК" для тебя что-то знакомое, но до конца не уверен...

- Ты не знаешь чем он отличается от двусвязного списка
- Без понятия какие там реализации

То ты 👉: среднестатистический разработчик

И сейчас я тебя прокачаю!

В общем, дек — абстрактный тип данных, который поддерживает вставку и удаление из начала и конца за O(1)

Абстрактный — значит реализация может быть любая и главное, чтобы выполнялись правила выше

Например, двусвязный список — это одна из реализаций дека

Или можно реализовать его на двух стеках

В общем — как угодно

НО! C++ ТУТ УДЕЛАЛ ВСЕХ!

Он сделал реализацию на chunked array, за счет чего появилась операция доступа по индексу за O(1)...

Т е натуральная имба, которая мало того что удаление и вставка в начало и конец, так еще и O(1) получить элемент по индексу

И вся магия в реализации...

А если соберем 100 🌭 до пятницы — расскажу как это работает под капотом

UPD: разбору быть)

Вставляю за O(1) и в коней и в начало. Кто я?

Правильно — дек!

Как и обещал — раскрываю магию std::deque из C++ или как в деке поддержать доступ по индексу за O(1)

Если коротко — нам нужен chunked array

Идея гениальна:

Вместо одного большого массива используется массив указателей на маленькие массивы (чанки)

👉 Структура

[ chunk1 ] [ chunk2 ] [ chunk3 ] [ chunk4 ]
↓ ↓ ↓ ↓
[..............] [..............] [..............] [..............]

Каждый chunk — небольшой массив фиксированного размера B
(обычно 8, 64 или 128 элементов — зависит от типа данных)

И дополнительно хранится таблица указателей на чанки:

chunks = [&chunk1, &chunk2, &chunk3, &chunk4]

👉 Начальное состояние

При создании deque выделяется первый chunk.

Кроме этого создаётся таблица указателей на чанки (chunks).
Она выделяется с запасом и стартует примерно с середины массива.

Это сделано специально, чтобы таблица могла расти и влево, и вправо.

Например:

chunks = [ _ _ _ &chunk1 _ _ _ ]

Теперь внутри chunk выбирается позиция:

head = tail

[ _ _ _ _ _ _ _ _ ]
↑
head, tail

Это означает, что дек пустой.

head — позиция первого элемента
tail — позиция сразу после последнего элемента

То есть элементы всегда лежат в диапазоне:

[ head ........ tail )

🚨 КАПЕЦ ВАЖНО!!!

head и tail — это глобальные позиции в структуре,
а не индексы внутри конкретного чанка.

Поэтому head может указывать НЕ на начало чанка, а на любую позицию внутри него.

Крайние чанки часто заполнены лишь частично — и это нормально.

Например дек может выглядеть так:

[ _ _ _ A B C D _ ]
↑ ↑
head tail

Здесь:

head -> указывает на первый элемент A
tail -> указывает на позицию сразу после последнего элемента D

То есть элементы лежат в диапазоне:

[ head ..... tail )

👉 Как работает push_front (вставка в начало)

Вставка в начало — это просто сдвиг head влево.

1) Уменьшаем head

head -= 1

2) Теперь нужно понять в какой chunk писать

chunk = head / m
offset = head % m
m — это размер чанка

3) Если нужного chunk ещё нет — создаём
и кладём ссылку на него в таблицу chunks

4) Записываем элемент

chunks[chunk][offset] = value

Если раньше head стоял в начале чанка — после head -= 1
мы автоматически перейдём в предыдущий chunk.

Никакие элементы не двигаются.

❗ Что если chunk получился отрицательным?

Это значит, что мы ушли левее начала массива chunks.

В этом случае:

1) создаётся новый массив указателей большего размера
2) старые указатели копируются примерно в середину нового массива
(копируются только указатели, не сами данные)
3) таблица снова получает свободное место слева и справа

После этого продолжаем вставку.

Такая операция происходит редко, поэтому вставка остаётся амортизированно O(1).


👉 Как работает pop_front (удаление из начала)

Удаление — это просто сдвиг head вправо.

1) Находим текущую позицию

chunk = head / m
offset = head % m
m — это размер чанка

2) Читаем элемент

value = chunks[chunk][offset]

3) Сдвигаем начало

head += 1

Если чанк слева полностью опустел — его можно удалить.

👉 Как получить i-й элемент (доступ по индексу)

Индекс i считается от текущего начала (head).

Сначала переводим его в абсолютную позицию:

pos = head + i

Теперь находим чанк и позицию внутри него:

chunk = pos / m
offset = pos % m
m — это размер чанка

И получаем элемент:

chunks[chunk][offset]

Вся магия в том, что deque никогда не двигает элементы

Он двигает только head/tail и добавляет новые чанки при необходимости

ФУУХХХХ

Если просто долистал до конца, то красавчик! Ставлю тебе 🌭

Как я начал видеть бинарный поиск вообще везде

В общем, была у меня проблема с бинарным поиском - я мало где его вообще видел

Если задача начиналась не с "массив отсортирован, нужно проверить наличие числа target" - то считал, что бинарным поиском вообще не решить...

Полечилось это очень интересным приседанием

Я стал искать способ решить буквально каждую задачу бинарным поиском

Даже на таких задачах:
• Даны массивы строк и нужно найти общий префикс
• Проверка, что число — степень двойки

И прикол в том, что это реально помогло

ИМЕННО БЛАГОДАРЯ ТАКИМ ПРОСТЫМ ЗАДАЧАМ Я ЕГО И НАЧАЛ ЧУВСТВОВАТЬ - где можно, а где нельзя его применить

Как только я понял, что существует "бинарный поиск по ответу" и бинарить можно не только по индексам, то дело пошло прям намного быстрее

И как оказалось даже неоптимальное и странное решение задач может дать свои плоды

В моем случае научился видеть бинарный поиск и больше не могу его развидеть 🌭

Свеженькая задача Яндекса

Недавно ребята из сообщества algocode.io гоняли на собесы и принесли такую задачку

Дан список перелётов tickets, где
tickets[i] = [A, B] — перелёт между городами A и B (направление неизвестно).

Все перелёты относятся к одному путешествию:
• каждый следующий перелёт начинается в городе, где закончился предыдущий
• ни один город не посещается дважды
• начальный город ≠ конечному

Нужно восстановить порядок городов в маршруте.
Если есть несколько вариантов — вернуть любой.

Пример

Ввод:
tickets = [["Berlin","Rome"],["Berlin","Dubai"]]

Вывод:
["Dubai","Berlin","Rome"] или ["Rome","Berlin","Dubai"]

Вся сложность в том, что направления запутаны!

Именно на этом валятся

Идея решения такая

• строим хеш-таблицу graph, где ключ — город отправления, а значение — список городов прибытия (в 2 стороны строим путь)

• находим любую вершину, у которой в значении только 1 город — это будет точка старта

• обходим граф из стартовой точки, поддерживая visited и не посещая уже отмеченные точки

И в итоге получим такое решение

from typing import *
from collections import defaultdict

def route(tickets: List[List[str]]) -> List[str]:
# для каждого города храним список городов, с которыми он связан
graph = defaultdict(list)
for a, b in tickets:
graph[a].append(b)
graph[b].append(a)

# начальный город — тот, у которого ровно одна связь (край маршрута)
start = ""
for city, neighbors in graph.items():
if len(neighbors) == 1:
start = city
break

# восстанавливаем маршрут, отмечая посещённые города
result = [start]
visited = {start}
for _ in range(len(tickets)):
current = result[-1]
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
result.append(neighbor)
break

return result


На leetcode не нашел такой задачки

Для тех кто уже в сообществе: решить можно самому ТУТ