Задачка прямо из Озона в ленту
День знаний — значит нужно что-то умное написать
В общем
В ОЗОНЕ встречается задачка на разворот числа
Есть, скажем, число 123 — нужно получить 321
Топ-1 ред флаг: преобразовать в строку, развернуть, преобразовать в число
NO! NO! NO!
Больше на собес после такого могут не позвать(шучу)
В общем, нужен другой способ и он есть!
Скажем, есть у нас n = 123 — давай посмотрим по шагам, как его можно развернут
Вообще алгоритм достаточно популярный, и его часто используют для разворота числа
Задача решена?
ХРЕНОС ДВА
В условии есть такая шляпа: если при этом происходит переполнение, функция должна вернуть 0.
Чтобы это сделать, нужно при формировании обратного числа всё время делать проверку на переполнение
Это уже неочевидная штука, но в итоге получится такое решение:
Именно if result > max_int // 10: и помогает решить проблему и детектить переполнение
И это единственный способ, потому что int64 и длинную арифметику тебе тут использовать не разрешат
В противном случае могут записать как –1 балл
Решить можно самому на algocode.io:
https://algocode.io/courses/algo-big-tech/problem/reverse-num
Или на LeetCode:
https://leetcode.com/problems/reverse-integer/description/
И кайфового тебе дня и больших оферов! ✌️
День знаний — значит нужно что-то умное написать
В общем
В ОЗОНЕ встречается задачка на разворот числа
Есть, скажем, число 123 — нужно получить 321
Топ-1 ред флаг: преобразовать в строку, развернуть, преобразовать в число
NO! NO! NO!
Больше на собес после такого могут не позвать
В общем, нужен другой способ и он есть!
Скажем, есть у нас n = 123 — давай посмотрим по шагам, как его можно развернут
ь:x = 0
n = 123
x = x * 10 + n % 10 = 0 + 3 = 3
n = n // 10 = 12
x = x * 10 + n % 10 = 30 + 2 = 32
n = n // 10 = 1
x = x * 10 + n % 10 = 320 + 1 = 321
n = n // 10 = 0
Вообще алгоритм достаточно популярный, и его часто используют для разворота числа
Задача решена?
ХРЕНОС ДВА
В условии есть такая шляпа: если при этом происходит переполнение, функция должна вернуть 0.
Чтобы это сделать, нужно при формировании обратного числа всё время делать проверку на переполнение
Это уже неочевидная штука, но в итоге получится такое решение:
from typing import *
def reverse_num(n: int) -> int:
result = 0
if n < 0:
return -reverse_num(-n)
max_int = 2 ** 31 - 1
while n > 0:
# проверка на переполнение
if result > max_int // 10:
return 0
result = result * 10 + n % 10
n //= 10
return result
Именно if result > max_int // 10: и помогает решить проблему и детектить переполнение
И это единственный способ, потому что int64 и длинную арифметику тебе тут использовать не разрешат
В противном случае могут записать как –1 балл
Решить можно самому на algocode.io:
https://algocode.io/courses/algo-big-tech/problem/reverse-num
Или на LeetCode:
https://leetcode.com/problems/reverse-integer/description/
И кайфового тебе дня и больших оферов! ✌️
❤🔥28🌭10
Как я готовил своего кореша в Яндекс
В общем, примерно полгода назад кореш попросил натаскать его по алгосам
Я такой — да без проблем, давай для начала устроим мок
Мок — это тот же собес, но не настоящий, а в кальянной 😂
В общем, дал ему для разминки такую задачу:
Есть массив и число target — нужно вернуть индексы позиций двух элементов, которые дают в сумме target
Мой кореш: «Да ты за лоха меня держишь? Я прекрасно знаю задачу two sum
А я, на секундочку, даже алгосов не знаю нормально»
Я: «Ну так реши раз просто»
Кореш: «Ну хеш-таблицу создаем, где ключ — элемент, а индекс — его позиция. По времени O(n) и по памяти тоже»
Я: «Не-а, по памяти не оптимально»
И тут до кореша доходит, что что-то тут не так
Я подсказываю ему, что решить задачу в текущей постановке нереально и нужно задавать дополнительные вопросы, чтобы понять, что делать
Хорошим вопросом был:
— А массив отсортирован?
Ответ: да.
Он такой — ну всё понятно, тогда ставим указатели на начало и конец, и если сумма = target, возвращаем индексы. В противном случае двигаем левый указатель если сумма текущих элементов меньше target и правый если больше. По времени O(n), по памяти O(1)
Я: «Не, кое-что не учли, и в некоторых случаях будет неправильный ответ»
Полыхать у него стало знатно 😂
Я не стал его душить и сказал, что проблема во множественных ответах, и ты не уточнял, какой именно брать...
🔥 ← мой кореш. Степень прожарки: medium rare.
Я решил добить до well done и сказал, что он не учитывает ещё возможное переполнение типов, а хотелось бы выбрасывать исключение на нём.
И в итоге получил полную прожарку кореша по алгосам.
Это я к чему:
Умение задавать вопросы — очень крутой навык, и некоторые задачи имеют много решений, а вопросы помогают понять, какое из них брать
И не все интервьюеры будут давать однозначное условие
Есть такие типы вопросов:
1) Ограничения
- какой длины массив максимум
- а сумма может давать переполнение типа
- какое максимальное/минимальное значение элементов в массиве
- а массив отсортирован
- и т. д.
2) Валидность данных
- могу ли я рассчитывать на ограничения или нужно их валидировать и выбрасывать исключение
3) Уточнить значение слов
- что такое палиндром
- что такое ось симметрии
- и т. д.
И ещё несколько типов, но самые важные я перечислил
Как правило, кандидаты с начальным уровнем алгоритмов задают вопросы:
- только для уточнения значения слов
- и для уточнения тесткейсов (почему в примере ответ XYZ)
А опытные кандидаты наоборот:
- задают вопросы только про ограничения
- и про валидность данных
Потому что значения слов они давно поняли, и у них в голове есть несколько решений
А вопросы про ограничения они используют, чтобы выбрать лучшее из всех вариантов и написать только его
Ну и бахни 🌭, если нашёл для себя в посте новые мысли и кайфанул
В общем, примерно полгода назад кореш попросил натаскать его по алгосам
Я такой — да без проблем, давай для начала устроим мок
Мок — это тот же собес, но не настоящий, а в кальянной 😂
В общем, дал ему для разминки такую задачу:
Есть массив и число target — нужно вернуть индексы позиций двух элементов, которые дают в сумме target
Мой кореш: «Да ты за лоха меня держишь? Я прекрасно знаю задачу two sum
А я, на секундочку, даже алгосов не знаю нормально»
Я: «Ну так реши раз просто»
Кореш: «Ну хеш-таблицу создаем, где ключ — элемент, а индекс — его позиция. По времени O(n) и по памяти тоже»
Я: «Не-а, по памяти не оптимально»
И тут до кореша доходит, что что-то тут не так
Я подсказываю ему, что решить задачу в текущей постановке нереально и нужно задавать дополнительные вопросы, чтобы понять, что делать
Хорошим вопросом был:
— А массив отсортирован?
Ответ: да.
Он такой — ну всё понятно, тогда ставим указатели на начало и конец, и если сумма = target, возвращаем индексы. В противном случае двигаем левый указатель если сумма текущих элементов меньше target и правый если больше. По времени O(n), по памяти O(1)
Я: «Не, кое-что не учли, и в некоторых случаях будет неправильный ответ»
Полыхать у него стало знатно 😂
Я не стал его душить и сказал, что проблема во множественных ответах, и ты не уточнял, какой именно брать...
🔥 ← мой кореш. Степень прожарки: medium rare.
Я решил добить до well done и сказал, что он не учитывает ещё возможное переполнение типов, а хотелось бы выбрасывать исключение на нём.
И в итоге получил полную прожарку кореша по алгосам.
Это я к чему:
Умение задавать вопросы — очень крутой навык, и некоторые задачи имеют много решений, а вопросы помогают понять, какое из них брать
И не все интервьюеры будут давать однозначное условие
Есть такие типы вопросов:
1) Ограничения
- какой длины массив максимум
- а сумма может давать переполнение типа
- какое максимальное/минимальное значение элементов в массиве
- а массив отсортирован
- и т. д.
2) Валидность данных
- могу ли я рассчитывать на ограничения или нужно их валидировать и выбрасывать исключение
3) Уточнить значение слов
- что такое палиндром
- что такое ось симметрии
- и т. д.
И ещё несколько типов, но самые важные я перечислил
Как правило, кандидаты с начальным уровнем алгоритмов задают вопросы:
- только для уточнения значения слов
- и для уточнения тесткейсов (почему в примере ответ XYZ)
А опытные кандидаты наоборот:
- задают вопросы только про ограничения
- и про валидность данных
Потому что значения слов они давно поняли, и у них в голове есть несколько решений
А вопросы про ограничения они используют, чтобы выбрать лучшее из всех вариантов и написать только его
Ну и бахни 🌭, если нашёл для себя в посте новые мысли и кайфанул
🌭87❤🔥5🤣2
Разваливаем собес Яндекса
Попалась задачка:
Дан массив отрезков segments, где segments[i] = [start, end] — бронирование комнаты для переговоров.
Нужно вернуть минимальное число комнат, чтобы все переговоры могли пройти.
Пример:
БАЗА? БАЗА!
---
Решение — метод точек
Суть в том, что каждый отрезок переводим в точки:
-1 означает конец отрезка, а +1 начало
Далее сортируем по первому и второму значениям точки
ЮХУ! Финешь близок
Дальше — простой цикл: суммируем +1/-1 и ищем максимум.
Это и будет минимальное количество переговорных.
------
Таким образом мы находим максимально число отрезков, которые пересекаются, что и будет ответом на задачу
-------
Если что-то не понял, это нормально!
Тема не самая простая, а вот и решение для наглядности, которое ожидает интервьюер
А решить самому можно на algocode.io:
https://algocode.io/courses/algo-big-tech/problem/meeting-rooms
Или leetcode
https://leetcode.com/problems/meeting-rooms-ii/description/ (Premium)
Важный момент! Если у нас отрезок [[1, 3],[3, 4]] то ответ будет 1 (сначала комната освобождается, потом занимается).
НО!
Интервьюер может на раз два поменять условие (чтобы комната сначала занималась и только потом освобождалась) и ответ уже будет 2
Это регулируется сортировкой
Чтобы добиться порядка [1, +1], [3,+1], [3,-1], [4, -1] можно сортировать так:
В общем, главное запомни, что порядок точек с равными значениями и их приоритет регулируется сортировкой и компаратором
Запомни только это и на собесе не будет ступора и быстро поймешь что делать!
Попалась задачка:
Дан массив отрезков segments, где segments[i] = [start, end] — бронирование комнаты для переговоров.
Нужно вернуть минимальное число комнат, чтобы все переговоры могли пройти.
Пример:
Ввод: [[2, 5], [1, 3]]
Вывод: 2
БАЗА? БАЗА!
---
Решение — метод точек
Суть в том, что каждый отрезок переводим в точки:
[2, 5] → [2, +1], [5, -1]
[1, 3] → [1, +1], [3, -1]
-1 означает конец отрезка, а +1 начало
Итого: [[2, +1], [5, -1], [1, +1], [3, -1]]
Далее сортируем по первому и второму значениям точки
[[1, +1], [2, +1], [3, -1], [5, -1]]
ЮХУ! Финешь близок
Дальше — простой цикл: суммируем +1/-1 и ищем максимум.
Это и будет минимальное количество переговорных.
------
Таким образом мы находим максимально число отрезков, которые пересекаются, что и будет ответом на задачу
-------
Если что-то не понял, это нормально!
Тема не самая простая, а вот и решение для наглядности, которое ожидает интервьюер
from typing import List
def count_meeting_rooms(segments: List[List[int]]) -> int:
points = []
for start, end in segments:
points.append([start, +1]) # начало — нужна комната
points.append([end, -1]) # конец — комната освободилась
# при равенстве точек: сначала освобождаем комнату, потом занимаем
points.sort()
max_rooms = 0
curr_rooms = 0
for _, delta in points:
curr_rooms += delta
max_rooms = max(max_rooms, curr_rooms)
return max_rooms
А решить самому можно на algocode.io:
https://algocode.io/courses/algo-big-tech/problem/meeting-rooms
Или leetcode
https://leetcode.com/problems/meeting-rooms-ii/description/ (Premium)
Важный момент! Если у нас отрезок [[1, 3],[3, 4]] то ответ будет 1 (сначала комната освобождается, потом занимается).
НО!
Интервьюер может на раз два поменять условие (чтобы комната сначала занималась и только потом освобождалась) и ответ уже будет 2
Это регулируется сортировкой
Чтобы добиться порядка [1, +1], [3,+1], [3,-1], [4, -1] можно сортировать так:
points.sort(key=lambda x: (x[0], -x[1]))
В общем, главное запомни, что порядок точек с равными значениями и их приоритет регулируется сортировкой и компаратором
Запомни только это и на собесе не будет ступора и быстро поймешь что делать!
🌭17❤🔥5
Не могу запомнить алго-задачу... Я тупой?
Когда я начинал учить алгосы и тупил на новой задаче всегда расстраивался
Что я делаю не так?
Почему не могу решить быстро?
И так хотелось бросить, что капец
НО
На стажировку в Яндекс хотелось сильнее 😂
В итоге я понял такую штуку: если я решаю задачку на какую-то идею и просто иду дальше, то потом очень низкий шанс, что я её решу снова
Но если решить хотя бы одну похожую задачу или просто тупо решить через время эту же, то результаты кратно круче
- Во-первых, лучше запоминается идея решения
- В новых задачах начинают виднеться уже изученные подходы
И наконец-то я начал видеть результат от изучения алгосов
В общем, максимально советую завести себе RETRY LIST (мне он помог)
RETRY LIST — это список ключевых задач лично для тебя, которые научили новому подходу, показали новую идею или просто важная задача, но никак не запомнишь
Если возвращаться к этим задачкам (их должно быть 15-20 не больше) то сможешь держать себя в форме
И не жди мега быстрого результата
Мне в своё время пришлось перерешивать все задачи по 2 раза и только потом открывался "третий глаз"
В общем, главное не останавливайся! Ты красавчик и всё сможешь!
Когда я начинал учить алгосы и тупил на новой задаче всегда расстраивался
Что я делаю не так?
Почему не могу решить быстро?
И так хотелось бросить, что капец
НО
На стажировку в Яндекс хотелось сильнее 😂
В итоге я понял такую штуку: если я решаю задачку на какую-то идею и просто иду дальше, то потом очень низкий шанс, что я её решу снова
Но если решить хотя бы одну похожую задачу или просто тупо решить через время эту же, то результаты кратно круче
- Во-первых, лучше запоминается идея решения
- В новых задачах начинают виднеться уже изученные подходы
И наконец-то я начал видеть результат от изучения алгосов
В общем, максимально советую завести себе RETRY LIST (мне он помог)
RETRY LIST — это список ключевых задач лично для тебя, которые научили новому подходу, показали новую идею или просто важная задача, но никак не запомнишь
Если возвращаться к этим задачкам (их должно быть 15-20 не больше) то сможешь держать себя в форме
И не жди мега быстрого результата
Мне в своё время пришлось перерешивать все задачи по 2 раза и только потом открывался "третий глаз"
В общем, главное не останавливайся! Ты красавчик и всё сможешь!
❤🔥32🌭12🤣3
Вот такая задачка попалась мне в VK
АРЯЯЯЯ, ВОТ ЭТО ЗАДАЧКА, ВОТ ЭТО Я ПОНИМАЮ
Дан список возрастов и нужно выполнять запросы вида — сколько человек с возрастом от 2 до 100 лет, потом от -1000 до 100 000 и так далее
Да, столько не живут и возраста ограничены от 0 до 140 лет, но вот запросики могут быть в любом диапазоне
Прикол в том, что в ВК была 1 задача на 1 час
Но для нее так же писали тестики и т д, да и в целом интервью глубже получилось, потому что решали одну задачку и обговаривали все нюансы
Чтобы решить ее оптимально нужно знать:
- технику подсчета
- префиксные суммы
(префиксные суммы ) Те самые, что за O(1) помогают находить сумму на отрезке
Тут собственно точно такая же идея — заводим массив count на 141 элемент
count[i] — число людей с таким возрастом
А потом самое интересное: нужно построить префиксные суммы по возрастам
И Я ЗУБ ДАЮ, что многие на этом валятся и получают не оптимальное решение
Ну и остается аккуратно написать обработку запросов
Итого получаем O(1) по времени и памяти на запрос и O(n) по времени и памяти на моменте инициализации
Все это работает быстро только потому что изначальный список возрастов не меняется, а запросов много
Если бы запрос на статистику возрастов был 1, то конечно все это не имеет смысла
Поэтому важно общаться с интервьюером
А меня позвали в VK, но я отказался)
А порешать задачку можно тут:
https://algocode.io/courses/algo-big-tech/problem/age-statistics
(На leetcode не нашел аналога)
+ там же есть все темы чтобы научиться самому решать такие задачи
И больших тебе офферов!
АРЯЯЯЯ, ВОТ ЭТО ЗАДАЧКА, ВОТ ЭТО Я ПОНИМАЮ
Дан список возрастов и нужно выполнять запросы вида — сколько человек с возрастом от 2 до 100 лет, потом от -1000 до 100 000 и так далее
Да, столько не живут и возраста ограничены от 0 до 140 лет, но вот запросики могут быть в любом диапазоне
Прикол в том, что в ВК была 1 задача на 1 час
Но для нее так же писали тестики и т д, да и в целом интервью глубже получилось, потому что решали одну задачку и обговаривали все нюансы
Чтобы решить ее оптимально нужно знать:
- технику подсчета
- префиксные суммы
(префиксные суммы ) Те самые, что за O(1) помогают находить сумму на отрезке
Тут собственно точно такая же идея — заводим массив count на 141 элемент
count[i] — число людей с таким возрастом
А потом самое интересное: нужно построить префиксные суммы по возрастам
И Я ЗУБ ДАЮ, что многие на этом валятся и получают не оптимальное решение
# Подсчитываем количество людей по каждому возрасту
freq = [0] * 141
for age in ages:
freq[age] += 1
# Строим префиксную сумму по возрастам
px = [0] * 142
count = 0
for i in range(1, 142):
count += freq[i - 1]
px[i] = count
result = []
# Обработка запросов
....
Ну и остается аккуратно написать обработку запросов
Итого получаем O(1) по времени и памяти на запрос и O(n) по времени и памяти на моменте инициализации
Все это работает быстро только потому что изначальный список возрастов не меняется, а запросов много
Если бы запрос на статистику возрастов был 1, то конечно все это не имеет смысла
Поэтому важно общаться с интервьюером
А меня позвали в VK, но я отказался)
А порешать задачку можно тут:
https://algocode.io/courses/algo-big-tech/problem/age-statistics
(На leetcode не нашел аналога)
+ там же есть все темы чтобы научиться самому решать такие задачи
И больших тебе офферов!
🌭23❤🔥10
Вчера гоняли Go-шной командой в ресторан)
В общем, собрал 5 сильных ребят по гошке, и мы по выходным решаем задачки с собесов разных компаний
Дорешали все задачи с Яндекс Advanced Code и решили встретиться вживую — поехали в рестик познакомиться лично
Вообще кайфно получилось: и задачки порешали, и познакомились — всё в одном флаконе
Хочу собрать ещё одну группу единомышленников по алгосам
Если у тебя крутая экспертиза в алгоритмах и хочется потусоваться с единомышленниками — пиши в ЛС
@fatinmaks
- расскажу подробно, как всё устроено
- даём всем ребятам бесплатный доступ к algocode.io
- для разнообразия иногда выбираемся в рестораны и т. д. для личного знакомства
Кому подойдёт:
- уже есть экспертиза в алгоритмах
- есть желание и возможность раз в неделю разбирать задачи c собесов
- есть коммерческий опыт
В общем, если есть кайф — пиши 😉
https://t.me/fatinmaks
В общем, собрал 5 сильных ребят по гошке, и мы по выходным решаем задачки с собесов разных компаний
Дорешали все задачи с Яндекс Advanced Code и решили встретиться вживую — поехали в рестик познакомиться лично
Вообще кайфно получилось: и задачки порешали, и познакомились — всё в одном флаконе
Хочу собрать ещё одну группу единомышленников по алгосам
Если у тебя крутая экспертиза в алгоритмах и хочется потусоваться с единомышленниками — пиши в ЛС
@fatinmaks
- расскажу подробно, как всё устроено
- даём всем ребятам бесплатный доступ к algocode.io
- для разнообразия иногда выбираемся в рестораны и т. д. для личного знакомства
Кому подойдёт:
- уже есть экспертиза в алгоритмах
- есть желание и возможность раз в неделю разбирать задачи c собесов
- есть коммерческий опыт
В общем, если есть кайф — пиши 😉
https://t.me/fatinmaks
🌭15❤🔥3
Алгоритмы нужны не всем!
В целом к алгоритмам есть много вопросов:
- кому их учить
- как глубоко учить
- какой профит от этого
- ...
И чтобы ответить на вопрос «а надо ли оно мне» — давай поговорим честно.
Я прохожу собес на джуна, мне нужны алгосы?
— Спорно... Да, в вакансиях о них пишут, но по большей части они нужны только для стажировок в BigTech (Яндекс, Авито, Т-Банк и т. д.).
Я бы сказал, что для обычных вакансий достаточно очень базового уровня.
А вот для стажировок в BigTech нужны знания на серьёзном, олимпиадном уровне.
Я прохожу собес на мидла, мне нужны алгосы?
Уххх, брат! Ты прям в точку!
Вот как раз тебе алгоритмы могут дать самый большой карьерный буст!
1) Тебе открывается лёгкая дорога в BigTech — ведь алго-собес намного проще, чем контекст на стажёра
2) Подготовка к собеседованию в BigTech по алгосам занимает 2–3 месяца при плотной работе. Обычно порядка 50–60 задач достаточно, чтобы уверенно себя показывать
3) Можно закрыть гештальт и спокойно откликаться на большее число вакансий
Я прохожу собес на синьора, мне нужны алгосы?
Нуууу... ХЗ, ХЗ, ХЗ
Только если хочешь в BigTech. А так, лучше прокачивать навыки проектирования или менеджерские — с этого будет больше выхлопа
А так, у тебя скорее всего уже есть некоторая бицуха в алгосах
---
В общем, на мой взгляд, учить алгоритмы на мидловой позиции — самое выгодное занятие
И если хочешь порешать задачки конкретных компаний или узнать инсайды по собесам — залетай в сообщество algocode.io
Только за последний месяц у нас +7 ребят устроились в Яндекс :)
В целом к алгоритмам есть много вопросов:
- кому их учить
- как глубоко учить
- какой профит от этого
- ...
И чтобы ответить на вопрос «а надо ли оно мне» — давай поговорим честно.
Я прохожу собес на джуна, мне нужны алгосы?
— Спорно... Да, в вакансиях о них пишут, но по большей части они нужны только для стажировок в BigTech (Яндекс, Авито, Т-Банк и т. д.).
Я бы сказал, что для обычных вакансий достаточно очень базового уровня.
А вот для стажировок в BigTech нужны знания на серьёзном, олимпиадном уровне.
Я прохожу собес на мидла, мне нужны алгосы?
Уххх, брат! Ты прям в точку!
Вот как раз тебе алгоритмы могут дать самый большой карьерный буст!
1) Тебе открывается лёгкая дорога в BigTech — ведь алго-собес намного проще, чем контекст на стажёра
2) Подготовка к собеседованию в BigTech по алгосам занимает 2–3 месяца при плотной работе. Обычно порядка 50–60 задач достаточно, чтобы уверенно себя показывать
3) Можно закрыть гештальт и спокойно откликаться на большее число вакансий
Я прохожу собес на синьора, мне нужны алгосы?
Нуууу... ХЗ, ХЗ, ХЗ
Только если хочешь в BigTech. А так, лучше прокачивать навыки проектирования или менеджерские — с этого будет больше выхлопа
А так, у тебя скорее всего уже есть некоторая бицуха в алгосах
---
В общем, на мой взгляд, учить алгоритмы на мидловой позиции — самое выгодное занятие
И если хочешь порешать задачки конкретных компаний или узнать инсайды по собесам — залетай в сообщество algocode.io
Только за последний месяц у нас +7 ребят устроились в Яндекс :)
🌭15❤🔥9
Спрашиваю кандидата: "Когда можно применять бинарный поиск?"
Ответ: когда массив отсортирован
Ну все, приехали как говорится :)
После такого ответа люблю спросить такую задачку:
Дано число x и нужно найти его корень без деления и встроенных функций в ЯП
И тут как правило кандидат садится на мель...
А задачка то решается тоже через бинарный поиск
Всего есть 3 фазы в бин. поиске
1) определить левую и правую границу между которыми ищем - допустимый диапазон для ответа
В данной задаче:
L = 0
R = x + 1
2) Определить функцию good, которая скажет двигать левый указатель для смещения диапазона или правый
ВОТ ЭТО САМЫЙ СЛОЖНЫЙ МОМЕНТ!
Объясняю на примере
вот есть число 4
И есть ряд чисел от 0 до 5 - ответ на вопрос какой корень из 4 точно лежит в этом диапазоне
Теперь давай отметим все элементы которые если возвести в квадрат получится <= 4 и будем считать их хорошими (G - good)
А все остальные (B - bad) плохими
0 1 2 | 3 4 5
G G G | F F F
Видно, что последовательность разделилась так: сначала все хорошие, а потом все плохие
И ЕСЛИ МОЖЕМ ПРИДУМАТЬ ТАКУЮ ФУНКЦИЮ
Которая разделит все последовательности во всех случаях сначала на хорошие элементы а потом на плохие
ТО ТОЛЬКО ТОГДА МОЖНО БИН ПОИСК ДЕЛАТЬ
В нашем случае функция good будет:
Где m - текущее число (от 0 до x + 1)
3) Просто написать базовую болванку подставив туда значения L и R и функцию good
Вообще, в хорошем бинарном поиске меняются только 3 строки:
1) значение L стартовое
2) значение R стартовое
3) функция good
Мало того что подход очень универсальный так и в нем понятно что в результате бинарного поиска
L - всегда смотрим на последний хороший элемент
R - на первый плохой
L R
0 1 2 | 3 4 5
G G G | F F F
И очень легко возвращать ответ с полным пониманием что такое L и R в результате бин. поиска
Более глубоко об этом рассказывал в видосе: https://www.youtube.com/watch?v=p-9zskDoaUE
До сих пор ору с этого видоса. Я там капец робот 😂😂😂
По контенту нормас)
-----------
А когда встретимся на собесе я обязательно спрошу тебя: а когда бинарный поиск можем использовать?
-----------
А решить задачку на algocode.io:
https://algocode.io/courses/algo-big-tech/problem/search-sqrt
Или leetcode:
https://leetcode.com/problems/sqrtx/description/
В общем, бин поиск это не только про массивы и применять его можно для чисел и даже для не отсортированных массивов. Есть даже задачка "Поиск в неотсортированном массиве" - решается тоже через бин. поиск
Ответ: когда массив отсортирован
Ну все, приехали как говорится :)
После такого ответа люблю спросить такую задачку:
Дано число x и нужно найти его корень без деления и встроенных функций в ЯП
И тут как правило кандидат садится на мель...
А задачка то решается тоже через бинарный поиск
Всего есть 3 фазы в бин. поиске
1) определить левую и правую границу между которыми ищем - допустимый диапазон для ответа
В данной задаче:
L = 0
R = x + 1
2) Определить функцию good, которая скажет двигать левый указатель для смещения диапазона или правый
ВОТ ЭТО САМЫЙ СЛОЖНЫЙ МОМЕНТ!
Объясняю на примере
вот есть число 4
И есть ряд чисел от 0 до 5 - ответ на вопрос какой корень из 4 точно лежит в этом диапазоне
0 1 2 3 4 5
Теперь давай отметим все элементы которые если возвести в квадрат получится <= 4 и будем считать их хорошими (G - good)
А все остальные (B - bad) плохими
0 1 2 | 3 4 5
G G G | F F F
Видно, что последовательность разделилась так: сначала все хорошие, а потом все плохие
И ЕСЛИ МОЖЕМ ПРИДУМАТЬ ТАКУЮ ФУНКЦИЮ
Которая разделит все последовательности во всех случаях сначала на хорошие элементы а потом на плохие
ТО ТОЛЬКО ТОГДА МОЖНО БИН ПОИСК ДЕЛАТЬ
В нашем случае функция good будет:
m * m <= x
Где m - текущее число (от 0 до x + 1)
3) Просто написать базовую болванку подставив туда значения L и R и функцию good
from typing import *
def find_sqrt(x: int) -> int:
# Note: работаем именно с целыми числами
# если работать с не целыми, то получим неточный ответ
# из-за накапливающейся неточности во float
l, r = 0, x + 1
while r - l > 1:
m = (l + r) // 2
if m * m <= x: # Функция good
l = m
else:
r = m
return l
Вообще, в хорошем бинарном поиске меняются только 3 строки:
1) значение L стартовое
2) значение R стартовое
3) функция good
Мало того что подход очень универсальный так и в нем понятно что в результате бинарного поиска
L - всегда смотрим на последний хороший элемент
R - на первый плохой
L R
0 1 2 | 3 4 5
G G G | F F F
И очень легко возвращать ответ с полным пониманием что такое L и R в результате бин. поиска
Более глубоко об этом рассказывал в видосе: https://www.youtube.com/watch?v=p-9zskDoaUE
До сих пор ору с этого видоса. Я там капец робот 😂😂😂
По контенту нормас)
-----------
А когда встретимся на собесе я обязательно спрошу тебя: а когда бинарный поиск можем использовать?
-----------
А решить задачку на algocode.io:
https://algocode.io/courses/algo-big-tech/problem/search-sqrt
Или leetcode:
https://leetcode.com/problems/sqrtx/description/
В общем, бин поиск это не только про массивы и применять его можно для чисел и даже для не отсортированных массивов. Есть даже задачка "Поиск в неотсортированном массиве" - решается тоже через бин. поиск
🌭21🤣1
Когда только начинал работать в Huawei познакомился с Лерой
Победитель ICPC
Мамма мия - победитель в олимпиадной проге - просто МАШИНА
Мне стало интересно как ее нанимали и какие задачки давали на входе
Оказалось, одной из задач было это:
"Дано число n Нужно вернуть true, если n является степенью двух, иначе false"
Честно, я ждал большего...
Ну там деревья крутануть пару раз...
Графы, сложные задачи на DP и все такое
САМОЕ ИНТЕРСНОЕ, что задачку на проверку степени двойки, котрая решается в 1 строчку
Лера забыла как решать
Ей было и смешно и стыдно, так как она знала это решение, но вот чет заклинило...
В итоге решила самым простым способом через деление и ее взяли
Я это к чему
На собесе бывает всякое и решить задачку хоть как-то лучше, чем не решить ничего
А когда пообщался с олимпиадниками, то понял, что им дает точно такие же задачи что и всем остальным
Интервьюеры то не олимпиадники по большей части 😂
Победитель ICPC
Мамма мия - победитель в олимпиадной проге - просто МАШИНА
Мне стало интересно как ее нанимали и какие задачки давали на входе
Оказалось, одной из задач было это:
"Дано число n Нужно вернуть true, если n является степенью двух, иначе false"
Честно, я ждал большего...
Ну там деревья крутануть пару раз...
Графы, сложные задачи на DP и все такое
САМОЕ ИНТЕРСНОЕ, что задачку на проверку степени двойки, котрая решается в 1 строчку
from typing import *
def is_power_of_two(n: int) -> bool:
return n > 0 and (n & (n - 1) == 0)
Лера забыла как решать
Ей было и смешно и стыдно, так как она знала это решение, но вот чет заклинило...
В итоге решила самым простым способом через деление и ее взяли
Я это к чему
На собесе бывает всякое и решить задачку хоть как-то лучше, чем не решить ничего
А когда пообщался с олимпиадниками, то понял, что им дает точно такие же задачи что и всем остальным
Интервьюеры то не олимпиадники по большей части 😂
🌭22❤🔥10
Quick sort повержен!
Закончил сценарий quick sort для ролика по сортировкам
Коротенечко пробежимся по основным подходам
В quick sort есть два стула:
- 2-way quick sort
- 3-way quick sort
2-way — делим массив на две части и сортируем каждую
3-way — делим на три части, но сортируем только две 😂
На картинке все наглядно видно
3-way спасает, когда в массиве куча повторяющихся элементов — не гоняем их туда-сюда по сто раз
НО ЭТО ТОЛЬКО БАЗА
В ролике копнем глубже: от учебной реализации до in-place quick sort с tailrec подходом и гарантией глубины рекурсии в log(n) + пооптимизируем сортировку мелких массивов
А еще в ролике будут:
- insertion sort
- selection sort
- count sort
- merge sort
- heap sort
Первые две — чисто разминка, а дальше пойдет настоящее мясо
Мой монтажер уже тихо плачет от количества анимаций, так что накидаем лойсов и поддержим его 😎
P.S. каждый лойс ускоряет выход ролика. Не байт, реально быстрее делаем)
Закончил сценарий quick sort для ролика по сортировкам
Коротенечко пробежимся по основным подходам
В quick sort есть два стула:
- 2-way quick sort
- 3-way quick sort
2-way — делим массив на две части и сортируем каждую
3-way — делим на три части, но сортируем только две 😂
На картинке все наглядно видно
3-way спасает, когда в массиве куча повторяющихся элементов — не гоняем их туда-сюда по сто раз
НО ЭТО ТОЛЬКО БАЗА
В ролике копнем глубже: от учебной реализации до in-place quick sort с tailrec подходом и гарантией глубины рекурсии в log(n) + пооптимизируем сортировку мелких массивов
А еще в ролике будут:
- insertion sort
- selection sort
- count sort
- merge sort
- heap sort
Первые две — чисто разминка, а дальше пойдет настоящее мясо
Мой монтажер уже тихо плачет от количества анимаций, так что накидаем лойсов и поддержим его 😎
P.S. каждый лойс ускоряет выход ролика. Не байт, реально быстрее делаем)
❤🔥91🌭22
Подготовься к Go-собесам!
Новый курс для участников сообщества algocode.io
"Подготовься к Go-собесам"
Что внутри:
- 25+ задач на конкурентность — от fan-in/fan-out до свежих задач из секции Advanced Code в Яндексе
- 40+ задач всего, и к каждой есть эталонное решение — именно такое, какое ждёт интервьюер
- ботановская теория — чтобы наконец разобраться, что такое этот ваш GMP
- чат, где можно задать любые вопросы по курсу
---
Если есть кайф — залетай:
https://algocode.io/community
На всякий случай напомню: в подписке доступ не только к Go-курсу, но и к:
- Алгоритмам и структурам данных
- System Design
Так что гошнику можно подготовиться от и до
UPD: а скоро в подписке будет еще курсец по SQL для собесов
Новый курс для участников сообщества algocode.io
"Подготовься к Go-собесам"
Что внутри:
- 25+ задач на конкурентность — от fan-in/fan-out до свежих задач из секции Advanced Code в Яндексе
- 40+ задач всего, и к каждой есть эталонное решение — именно такое, какое ждёт интервьюер
- ботановская теория — чтобы наконец разобраться, что такое этот ваш GMP
- чат, где можно задать любые вопросы по курсу
---
Если есть кайф — залетай:
https://algocode.io/community
На всякий случай напомню: в подписке доступ не только к Go-курсу, но и к:
- Алгоритмам и структурам данных
- System Design
Так что гошнику можно подготовиться от и до
UPD: а скоро в подписке будет еще курсец по SQL для собесов
❤🔥10🌭7
Интервьюер жестко докопался к Big O
В общем, зашел тут ко мне кореш
Тут все просто: друган дал слабину там, где ее показывать нельзя
В тюрьме нельзя ронять мыло, а в алгоритмах — ошибаться в Big O
В целом, ошибаться можно
НО!
Когда кандидат оценивает в Big O память как O(n*n), а время O(n), то и у меня как у интервьюера возникает капец много вопросов
Простое правило: оценка по памяти НЕ МОЖЕТ ПРЕВЫШАТЬ ВРЕМЯ
Ведь аллокация той же самой памяти требует времени
После этого хочется понять — насколько глубоко кандидат реально разбирается
Вот и полетели другану дополнительные вопросы
---
В целом, редко встречаются оценки кроме как:
- O(1)
- O(n)
- O(n*log(n))
- O(n*n)
- O(n^n)
И есть +- понятные правила к каждой оценке
Например, для оценки времени:
- O(n*log(n)) — если используем встроенную сортировку и это самая затратная операция
- O(n) — один или несколько раз пробежаться по массиву
- O(n*n) — вложенный цикл в цикл (не путать с плавающим окном), в общем перебор всех пар в массиве
- O(1) — в оценке по времени почти никогда не используется
- O(n^n) — это полный перебор
- O(log(n)) - бинарный поиск как правило
Если говорить про частотность оценок времени, то я бы сказал так:
- O(n)
- O(n*log(n))
- O(n*n)
- O(n^n)
- O(log(n))
- O(1)
Это обусловлено частотностью разных тем на собесах
Например, сейчас в тренде задачки на массивы, указатели, хеш-таблицы — а это всё как правило O(n)
Сортировка бывает, но не так часто — O(n*log(n)
А по объему памяти обычно это:
- O(1)
- O(n)
- O(log(n))
Остальные оценки по памяти встречаются редко, а различить O(1) и O(n) несложно.
O(log(n)) встречается в сортировках и при рекурсивных обходах сбалансированных деревьев - тут не запутаешься тоже
В общем, тут я раскидал все основные аспекты, чтобы ты не запутался и с кайфом решал алгосы!
В общем, зашел тут ко мне кореш
Максон, был на собесе, но чет душить интервьюер стал
Я замялся с Big O маленько, а он накинулся и не давал писать код, пока не оценю...
Тут все просто: друган дал слабину там, где ее показывать нельзя
В тюрьме нельзя ронять мыло, а в алгоритмах — ошибаться в Big O
В целом, ошибаться можно
НО!
Когда кандидат оценивает в Big O память как O(n*n), а время O(n), то и у меня как у интервьюера возникает капец много вопросов
Простое правило: оценка по памяти НЕ МОЖЕТ ПРЕВЫШАТЬ ВРЕМЯ
Ведь аллокация той же самой памяти требует времени
После этого хочется понять — насколько глубоко кандидат реально разбирается
Вот и полетели другану дополнительные вопросы
---
В целом, редко встречаются оценки кроме как:
- O(1)
- O(n)
- O(n*log(n))
- O(n*n)
- O(n^n)
И есть +- понятные правила к каждой оценке
Например, для оценки времени:
- O(n*log(n)) — если используем встроенную сортировку и это самая затратная операция
- O(n) — один или несколько раз пробежаться по массиву
- O(n*n) — вложенный цикл в цикл (не путать с плавающим окном), в общем перебор всех пар в массиве
- O(1) — в оценке по времени почти никогда не используется
- O(n^n) — это полный перебор
- O(log(n)) - бинарный поиск как правило
Если говорить про частотность оценок времени, то я бы сказал так:
- O(n)
- O(n*log(n))
- O(n*n)
- O(n^n)
- O(log(n))
- O(1)
Это обусловлено частотностью разных тем на собесах
Например, сейчас в тренде задачки на массивы, указатели, хеш-таблицы — а это всё как правило O(n)
Сортировка бывает, но не так часто — O(n*log(n)
А по объему памяти обычно это:
- O(1)
- O(n)
- O(log(n))
Остальные оценки по памяти встречаются редко, а различить O(1) и O(n) несложно.
O(log(n)) встречается в сортировках и при рекурсивных обходах сбалансированных деревьев - тут не запутаешься тоже
В общем, тут я раскидал все основные аспекты, чтобы ты не запутался и с кайфом решал алгосы!
🌭34❤🔥11
Fit-собес — это самый главный этап во всех BigTech.
Тот самый собес, к которому рекрутер говорит "не готовься", но который на самом деле определяет:
- твой грейд
- ЗП
- команду...
Давай по порядку. Есть такие секции собеседований в BigTech:
- Скрининг (иногда скипают) — около 30 минут
- Платформа (проверяют знание языка) — 60 минут
- Алгоритмы — 60 минут
- System Design (для senior)
- Fit-собес
Fit-собес — это финальное интервью с твоим будущим руководителем, который как раз принимает финальное решение: интересно ли ему брать тебя в команду или нет.
а, да — именно Fit-собес, а не технические.
Если ты плохо прошёл технику — это твой ограничитель,
а если хорошо — это ещё не гарант Senior-грейда.
Живой пример — Авито.
Полно ребят, которые прошли все секции на Senior,
но в итоге получили Middle+, потому что не готовились к Fit-собесу...
На fit задают такие вопросы, как:
- Расскажи о себе (в профессиональном контексте)
- Расскажи о самой сложной технической задаче
- Как устроены процессы в команде?
- Как ты решаешь задачи?
- ...
Вопросы могут звучать странно, особенно если ты не понимаешь, на что они нацелены.
Пример хорошего ответа на вопрос "Расскажи о себе":
"Сейчас работаю в компании XYZ — она занимается B2B-решениями в аналитике и предоставляет SaaS-продукты.
Наша команда из шести человек разрабатывает AB-платформу для проведения A/B-тестов внутри всей компании.
Я занимаю роль Feature Lead-а и отвечаю за функциональность двух сервисов.
Первый — админка. Её основные пользователи — аналитики. Главная сложность — поддержание eventual consistency модели с соседними сервисами XYZ и ZYC.
Второй — сплитовалка, которая занимается распределением трафика. Здесь основной фокус — на performance и оптимизации.
Хочу рассказать об интересной челендж-задаче, которую решал для этого сервиса: ..."
Что здесь хорошо:
1. Кратко обозначено, чем занимается компания
2. Чётко описаны команда, роль и зона ответственности
3. Есть контекст по сервисам и взаимодействию с другими частями системы
Рассказывание занимает буквально 30 секунд, но уже создаёт прозрачное понимание, чем ты занимаешься.
Чем выше грейд собеседующего — тем больше он ценит точность формулировок. Поэтому стоит подготовиться заранее.
А теперь мега-фишка!
Найм — это всегда про доверие.
Если лид верит, что ты справишься с задачами — он готов выбивать тебе лучшие условия.
Если нет — то нет.
И вызвать это доверие очень просто:
- Подготовь структурированный рассказ
- Сделай презентацию к своему рассказу (так почти никто не делает!)
- Вместо вопросов вроде "А какая у вас версия Python?" спроси:
— какие планы на квартал или год
— какие ожидания от тебя как от кандидата
— каков основной фокус продукта
Так ты покажешь, что не просто технически подкован, но и умеешь принимать продуктовые решения.
Тех, кто может молча писать код, — пруд пруди.
А вот твоё конкурентное преимущество в 2025 году — это развитые soft skills.
Всё, что я перечислил выше, — это практические навыки, которые выделяют тебя на фоне остальных и дают стабильность даже в турбулентные времена.
Для ребят из сообщества algocode.io я уже провёл три эфира (суммарно более 6 часов), где детально разобрали все на реальных примерах + есть отдельно по Авито.
Если ты уже в сообществе — обязательно посмотри запись:
"Готов к BigTech"
https://t.me/c/2290576342/110
"Матрица компетенций из разбора"
https://t.me/c/2290576342/105
"А ты Senior?"
https://t.me/c/2290576342/99
"Как не упустить жирный офер в Авито"
https://t.me/c/2290576342/70
P.S. В разборах мы смотрели на middle+ инженеров и на их примере провели карьерный разбор
-----
Решил немного карьерой разнообразить канальчик - а то все про алгосы да про алгосы
Если хочешь дальше видеть посты про карьеру, то бахни 🌭
Тот самый собес, к которому рекрутер говорит "не готовься", но который на самом деле определяет:
- твой грейд
- ЗП
- команду...
Давай по порядку. Есть такие секции собеседований в BigTech:
- Скрининг (иногда скипают) — около 30 минут
- Платформа (проверяют знание языка) — 60 минут
- Алгоритмы — 60 минут
- System Design (для senior)
- Fit-собес
Fit-собес — это финальное интервью с твоим будущим руководителем, который как раз принимает финальное решение: интересно ли ему брать тебя в команду или нет.
а, да — именно Fit-собес, а не технические.
Если ты плохо прошёл технику — это твой ограничитель,
а если хорошо — это ещё не гарант Senior-грейда.
Живой пример — Авито.
Полно ребят, которые прошли все секции на Senior,
но в итоге получили Middle+, потому что не готовились к Fit-собесу...
На fit задают такие вопросы, как:
- Расскажи о себе (в профессиональном контексте)
- Расскажи о самой сложной технической задаче
- Как устроены процессы в команде?
- Как ты решаешь задачи?
- ...
Вопросы могут звучать странно, особенно если ты не понимаешь, на что они нацелены.
Пример хорошего ответа на вопрос "Расскажи о себе":
"Сейчас работаю в компании XYZ — она занимается B2B-решениями в аналитике и предоставляет SaaS-продукты.
Наша команда из шести человек разрабатывает AB-платформу для проведения A/B-тестов внутри всей компании.
Я занимаю роль Feature Lead-а и отвечаю за функциональность двух сервисов.
Первый — админка. Её основные пользователи — аналитики. Главная сложность — поддержание eventual consistency модели с соседними сервисами XYZ и ZYC.
Второй — сплитовалка, которая занимается распределением трафика. Здесь основной фокус — на performance и оптимизации.
Хочу рассказать об интересной челендж-задаче, которую решал для этого сервиса: ..."
Что здесь хорошо:
1. Кратко обозначено, чем занимается компания
2. Чётко описаны команда, роль и зона ответственности
3. Есть контекст по сервисам и взаимодействию с другими частями системы
Рассказывание занимает буквально 30 секунд, но уже создаёт прозрачное понимание, чем ты занимаешься.
Чем выше грейд собеседующего — тем больше он ценит точность формулировок. Поэтому стоит подготовиться заранее.
А теперь мега-фишка!
Найм — это всегда про доверие.
Если лид верит, что ты справишься с задачами — он готов выбивать тебе лучшие условия.
Если нет — то нет.
И вызвать это доверие очень просто:
- Подготовь структурированный рассказ
- Сделай презентацию к своему рассказу (так почти никто не делает!)
- Вместо вопросов вроде "А какая у вас версия Python?" спроси:
— какие планы на квартал или год
— какие ожидания от тебя как от кандидата
— каков основной фокус продукта
Так ты покажешь, что не просто технически подкован, но и умеешь принимать продуктовые решения.
Тех, кто может молча писать код, — пруд пруди.
А вот твоё конкурентное преимущество в 2025 году — это развитые soft skills.
Всё, что я перечислил выше, — это практические навыки, которые выделяют тебя на фоне остальных и дают стабильность даже в турбулентные времена.
Для ребят из сообщества algocode.io я уже провёл три эфира (суммарно более 6 часов), где детально разобрали все на реальных примерах + есть отдельно по Авито.
Если ты уже в сообществе — обязательно посмотри запись:
"Готов к BigTech"
https://t.me/c/2290576342/110
"Матрица компетенций из разбора"
https://t.me/c/2290576342/105
"А ты Senior?"
https://t.me/c/2290576342/99
"Как не упустить жирный офер в Авито"
https://t.me/c/2290576342/70
P.S. В разборах мы смотрели на middle+ инженеров и на их примере провели карьерный разбор
-----
Решил немного карьерой разнообразить канальчик - а то все про алгосы да про алгосы
Если хочешь дальше видеть посты про карьеру, то бахни 🌭
🌭67❤🔥3
Что не так с деревьями?
В чём вообще суть любой алгоритмической задачи? Найти оптимальное решение, которое будет эффективно работать на больших данных.
И это правило везде одно: решил не оптимально с точки зрения Big O — НА ВЫХОД!
Но почему-то это правило обошло деревья стороной...
Окей, окей — вот условие задачи прямо с собеса:
Дан корень правильного бинарного дерева поиска и число k. Нужно вернуть k-й наименьший элемент в дереве (отсчёт начинается с 1).
Бинарное дерево — значит, у каждой вершины не более двух детей.
Дерево поиска — значит, все элементы в левом поддереве меньше текущего, а в правом — больше.
Короче, вот пример дерева — и всё сразу станет ясно:
Пусть k = 3. Тогда третий наименьший элемент — это 3, именно её и нужно вернуть по условию.
Чтобы решать задачи на деревья, нужно знать три обхода: preorder, inorder, postorder.
Они позволяют обойти все вершины дерева в определённом порядке.
Для примера выше:
Заметил? inorder выдал отсортированный порядок — и это не совпадение!
Если дерево — правильное бинарное дерево поиска, то inorder всегда выдаёт отсортированную последовательность.
Реализация inorder-обхода:
Простое решение задачи:
1. Запускаем inorder и получаем отсортированный список.
2. Возвращаем k-й элемент (с индексом k - 1).
Оценка: время — O(n), память — O(n).
Но! Такое решение на собеседовании часто не принимают. Слишком много дополнительной памяти — хочется оптимальнее.
Какое решение ждут: нужно прямо во время обхода считать, какой элемент мы посещаем, и если он k-й — вернуть его сразу, не сохраняя все значения вершин дерева.
Оценка: время — O(n), память — O(n).
WTF? Почему такие же оценки, если вроде оптимизировали?
Пусть k = 1, а дерево выглядит вот так — «бамбук» с уклоном влево:
Видишь? Нам всё равно придётся спуститься в самый низ, чтобы достать единицу — самый минимальный элемент.
А память откуда O(n)? Из-за рекурсии, брат! Каждый рекурсивный вызов занимает место в стеке.
В худшем случае это O(h), где h — высота дерева, а если дерево вытянутое, то просто h = n.
P.S. продолжение через минуты
В чём вообще суть любой алгоритмической задачи? Найти оптимальное решение, которое будет эффективно работать на больших данных.
И это правило везде одно: решил не оптимально с точки зрения Big O — НА ВЫХОД!
Но почему-то это правило обошло деревья стороной...
Окей, окей — вот условие задачи прямо с собеса:
Дан корень правильного бинарного дерева поиска и число k. Нужно вернуть k-й наименьший элемент в дереве (отсчёт начинается с 1).
Бинарное дерево — значит, у каждой вершины не более двух детей.
Дерево поиска — значит, все элементы в левом поддереве меньше текущего, а в правом — больше.
Короче, вот пример дерева — и всё сразу станет ясно:
4
/ \
2 6
/ \ / \
1 3 5 7
Пусть k = 3. Тогда третий наименьший элемент — это 3, именно её и нужно вернуть по условию.
Чтобы решать задачи на деревья, нужно знать три обхода: preorder, inorder, postorder.
Они позволяют обойти все вершины дерева в определённом порядке.
Для примера выше:
preorder: 4, 2, 1, 3, 6, 5, 7
inorder: 1, 2, 3, 4, 5, 6, 7
postorder: 1, 3, 2, 5, 7, 6, 4
Заметил? inorder выдал отсортированный порядок — и это не совпадение!
Если дерево — правильное бинарное дерево поиска, то inorder всегда выдаёт отсортированную последовательность.
Реализация inorder-обхода:
from typing import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def traversal(node: Optional[TreeNode], result: List[int]) -> None:
if node is None:
return
traversal(node.left, result)
result.append(node.val)
traversal(node.right, result)
def inorder_traversal(root: Optional[TreeNode]) -> List[int]:
result = []
traversal(root, result)
return result
Простое решение задачи:
1. Запускаем inorder и получаем отсортированный список.
2. Возвращаем k-й элемент (с индексом k - 1).
Оценка: время — O(n), память — O(n).
Но! Такое решение на собеседовании часто не принимают. Слишком много дополнительной памяти — хочется оптимальнее.
Какое решение ждут: нужно прямо во время обхода считать, какой элемент мы посещаем, и если он k-й — вернуть его сразу, не сохраняя все значения вершин дерева.
from typing import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def smallest_bst_element(root: TreeNode, k: int) -> int:
def inorder(node: TreeNode) -> int:
if node is None:
return None
result = inorder(node.left)
if result is not None:
return result
nonlocal k
k -= 1
if k == 0:
return node.val
return inorder(node.right)
return inorder(root)
Оценка: время — O(n), память — O(n).
WTF? Почему такие же оценки, если вроде оптимизировали?
Пусть k = 1, а дерево выглядит вот так — «бамбук» с уклоном влево:
4
/
3
/
2
/
1
Видишь? Нам всё равно придётся спуститься в самый низ, чтобы достать единицу — самый минимальный элемент.
А память откуда O(n)? Из-за рекурсии, брат! Каждый рекурсивный вызов занимает место в стеке.
В худшем случае это O(h), где h — высота дерева, а если дерево вытянутое, то просто h = n.
P.S. продолжение через минуты
🌭5🍓2
Что не так с деревьями?
🤙🤙🤙 Продолжение поста выше
📌 Много букв, но ты справишься!
---------
А теперь, когда ты всё это прочитал, самый прикол!
Это решение всё ещё не самое оптимальное. Дело в том, что есть обход Морриса (Morris Traversal). Такой обход не использует рекурсию и стек, поэтому решение получается O(n) по времени и O(1) по памяти.
С ним решение выглядит так:
Юху! Решили оптимально!
Но вот интервьюер вряд ли такое оценит...
Во-первых, есть риск, что он не знает про такие оптимальные подходы и просто посчитает решение некорректным
Во-вторых — ну оно реально жёсткое, и легко накосячить на мелочах
В общем, рекурсия в деревьях для решения задачи — это база. Да, не оптимально по памяти в худшем случае, но это база!
Где такое возможно еще??? А вот почти нигде - деревья тут отличились. В остальных темах надо оптимально решать...
Всем достаточно рекурсивного обхода 🙂
P.S. Если встретимся на собесе и ты расскажешь про обход Морриса и напишешь без ошибок — вторую задачу не дам: сразу апрув
Бахни 🌭 если зашел формат лонгрида! Если наберем 80+ сосисонов, то буду чаще в таком формате посты делать
🤙🤙🤙 Продолжение поста выше
📌 Много букв, но ты справишься!
---------
А теперь, когда ты всё это прочитал, самый прикол!
Это решение всё ещё не самое оптимальное. Дело в том, что есть обход Морриса (Morris Traversal). Такой обход не использует рекурсию и стек, поэтому решение получается O(n) по времени и O(1) по памяти.
С ним решение выглядит так:
from typing import *
from algocodelib import TreeNode
def smallest_bst_element(root: TreeNode, k: int) -> int:
curr = root
while curr:
if curr.left is None:
# посещаем узел
k -= 1
if k == 0:
return curr.val
curr = curr.right
else:
# ищем inorder-предшественника (правыйmost узел в левом поддереве)
pred = curr.left
while pred.right and pred.right is not curr:
pred = pred.right
if pred.right is None:
# создаём временную ссылку
pred.right = curr
curr = curr.left
else:
# убираем ссылку и посещаем узел
pred.right = None
k -= 1
if k == 0:
return curr.val
curr = curr.right
return -1 # если k больше, чем количество узлов
Юху! Решили оптимально!
Но вот интервьюер вряд ли такое оценит...
Во-первых, есть риск, что он не знает про такие оптимальные подходы и просто посчитает решение некорректным
Во-вторых — ну оно реально жёсткое, и легко накосячить на мелочах
В общем, рекурсия в деревьях для решения задачи — это база. Да, не оптимально по памяти в худшем случае, но это база!
Где такое возможно еще??? А вот почти нигде - деревья тут отличились. В остальных темах надо оптимально решать...
Всем достаточно рекурсивного обхода 🙂
P.S. Если встретимся на собесе и ты расскажешь про обход Морриса и напишешь без ошибок — вторую задачу не дам: сразу апрув
Бахни 🌭 если зашел формат лонгрида! Если наберем 80+ сосисонов, то буду чаще в таком формате посты делать
🌭105
А Озон-то не так прост!
Вообще, мало где дают задачки на системы счисления — так что Озон тут выделяется.
Недавно попалась вот такая задачка:
Дан номер колонки в Excel. Нужно назвать её порядковый номер.
Примеры:
Чтобы решать такую задачку без проблем, нужно знать операцию ord и уметь ей пользоваться.
ord — это функция, которая возвращает ASCII-код символа.
Например:
Да, без этого можно обойтись, но это база, как говорится.
Таким образом, мы можем сопоставить каждой букве её номер:
Бинго!
Первая часть решения позади — прямо как первый уровень в игре, где ты наконец понял, как устроен мир.
Теперь можно воспринимать строку так:
Откуда взялось 26?
У нас всего 26 различных символов. Если бы алфавит был только A B C, то умножали бы на 3...
Осталось только собрать всё вместе:
ВАЖНО!
Ожидают решение по памяти за O(1), так что составлять массив из чисел, а потом считать результат — не вариант (это было нужно только для объяснения).
В боевом решении всё должно быть оптимально.
Вообще, формула:
— это классика. Она будет часто встречаться, так что смело запоминай.
Решить задачку можно у нас на algocode.io как и другие задачи Озона:
https://algocode.io/courses/algo-big-tech/problem/int-from-excel-column
или на leetcode:
https://leetcode.com/problems/excel-sheet-column-title/description/
Вообще, мало где дают задачки на системы счисления — так что Озон тут выделяется.
Недавно попалась вот такая задачка:
Дан номер колонки в Excel. Нужно назвать её порядковый номер.
Примеры:
A -> 1
B -> 2
...
Z -> 26
AA -> 27
AB -> 28
Чтобы решать такую задачку без проблем, нужно знать операцию ord и уметь ей пользоваться.
ord — это функция, которая возвращает ASCII-код символа.
Например:
ord('A') = 65
ord('B') = 66
...
ord('Z') = 90
Да, без этого можно обойтись, но это база, как говорится.
Таким образом, мы можем сопоставить каждой букве её номер:
'A' -> ord('A') - ord('A') + 1 = 1
'B' -> ord('B') - ord('A') + 1 = 2
...
'Z' -> ord('Z') - ord('A') + 1 = 26
Бинго!
Первая часть решения позади — прямо как первый уровень в игре, где ты наконец понял, как устроен мир.
Теперь можно воспринимать строку так:
'AB' → [1, 2] → 1 * 26 + 2 = 28
'ABCD' → [1, 2, 3, 4] → 1 * 26³ + 2 * 26² + 3 * 26 + 4
Откуда взялось 26?
У нас всего 26 различных символов. Если бы алфавит был только A B C, то умножали бы на 3...
Осталось только собрать всё вместе:
from typing import *
# Время: O(n)
# Память: O(1)
def int_from_excel_column(column: str) -> int:
result = 0
for ch in column:
val = ord(ch) - ord('A') + 1
result = result * 26 + val
return result
ВАЖНО!
Ожидают решение по памяти за O(1), так что составлять массив из чисел, а потом считать результат — не вариант (это было нужно только для объяснения).
В боевом решении всё должно быть оптимально.
Вообще, формула:
result = result * 26 + val
— это классика. Она будет часто встречаться, так что смело запоминай.
Решить задачку можно у нас на algocode.io как и другие задачи Озона:
https://algocode.io/courses/algo-big-tech/problem/int-from-excel-column
или на leetcode:
https://leetcode.com/problems/excel-sheet-column-title/description/
❤🔥21🌭7
Что спросить у СТО, чтобы тебя наняли на высокий грейд?
Проходя собесы, я начал 1.5 года назад активно общаться с СТО на финальной секции
Получается, уже не просто маслёнок...
Как правило, это серьёзные дяди — и разговорить их было не всегда просто
Я прям видел отвращение в лицах после вопросов:
- «А какая версия Go у вас в проектах?»
- «А есть компенсация обедов?»
Просто разрыв живота 99-го уровня — как вспомню своё общение с СТО полтора года назад...
Главное правило общения с лидом и СТО, которое я вынес, чтобы вопросы не вызывали отвращения:
Не спрашивай то, на что может ответить рекрутер или то, что уже написано в вакансии. Потом у рекрутера уточнишь, если тебе важно.
А теперь важно определить цель вопросов:
Для себя с понял: у каждого вопроса должна быть цель, а не просто повыделываться типа умный
Например, для себя я понял:
- Хочу работать в отделе, через который проходят деньги, и который нужен бизнесу. Чтобы я был ценным сотрудником компании, чтобы вокруг были сильные сокомандники, чтобы был возможен ебейший карьерный рост
- Хочу сильного лида, который не зассыт отстоять большую премию своей команде и имеет свой вижен на развитие продукта. Чтобы его не трясло, как банный лист, от каждого нового необдуманного требования продактов
- Хочу работать в богатой компании или там, где знаком с владельцем бизнеса. Всё просто: если компания уже богатая, значит, там дофига людей, с кем можно познакомиться и перенять опыт. Если мелкая — то я хочу вносить импакт на уровне всей компании, а для этого нужно общаться с собственником
И теперь у меня есть простой чеклист
Встречаюсь с командами → задаю свои вопросы → если не матчимся хотя бы по 1 вопросу, то перехожу к следующей команде.
И знаете что?
99% fit-собесов я просто скипаю, потому что я не подхожу команде или она мне...
У меня нет задачи нравиться всем. Я хочу самый пиздатый матч, который только возможен.
Чтобы компания, которая меня нанимала, заработала на мне Х10, а лучше — Х100
Потому что в таком случае и я без денег не останусь, и компании будет капец как выгодно
WIN-WIN
Я не хочу быть посредственным!
Просто не хочу.
Так что вот мои вопросы:
- Какие цели у юнита на год, и у команды, куда меня рассматриваете, в частности?
- Какую роль продукт оказывает на бизнес и является ли ключевым?
- Какие ожидания у бизнеса от продукта? На какие метрики смотрит бизнес?
- Чем отличаетесь от конкурентов / планируете отличаться и кто они?
- Какие направления развиваете: B2B/B2C/B2G, и какие по ним планы?
- Довольны ли вы сейчас работой команды, куда меня нанимают, или есть критические поинты для улучшения?
----
В общем, я отказался от вопросов про ЯП 😂
Ну мне реально стало не особо интересно.Больше хочется про продукт узнать — его экономику и важность.
Этот чеклист точно не для тех, кто ищет первую работу.
Но зато тот 1%, в который попадает матч, выкатывает очень приятные офферына 600+ кэсов.
А какие вопросы на финалах задаёшь ты? Интересно будет глянуть комменты
P.S. экспериментирую с форматами постов так что бахни 🌭 если зашло
Проходя собесы, я начал 1.5 года назад активно общаться с СТО на финальной секции
Получается, уже не просто маслёнок...
Как правило, это серьёзные дяди — и разговорить их было не всегда просто
Я прям видел отвращение в лицах после вопросов:
- «А какая версия Go у вас в проектах?»
- «А есть компенсация обедов?»
Просто разрыв живота 99-го уровня — как вспомню своё общение с СТО полтора года назад...
Главное правило общения с лидом и СТО, которое я вынес, чтобы вопросы не вызывали отвращения:
А теперь важно определить цель вопросов:
Для себя с понял: у каждого вопроса должна быть цель, а не просто повыделываться типа умный
Например, для себя я понял:
- Хочу работать в отделе, через который проходят деньги, и который нужен бизнесу. Чтобы я был ценным сотрудником компании, чтобы вокруг были сильные сокомандники, чтобы был возможен ебейший карьерный рост
- Хочу сильного лида, который не зассыт отстоять большую премию своей команде и имеет свой вижен на развитие продукта. Чтобы его не трясло, как банный лист, от каждого нового необдуманного требования продактов
- Хочу работать в богатой компании или там, где знаком с владельцем бизнеса. Всё просто: если компания уже богатая, значит, там дофига людей, с кем можно познакомиться и перенять опыт. Если мелкая — то я хочу вносить импакт на уровне всей компании, а для этого нужно общаться с собственником
И теперь у меня есть простой чеклист
Встречаюсь с командами → задаю свои вопросы → если не матчимся хотя бы по 1 вопросу, то перехожу к следующей команде.
И знаете что?
99% fit-собесов я просто скипаю, потому что я не подхожу команде или она мне...
У меня нет задачи нравиться всем. Я хочу самый пиздатый матч, который только возможен.
Чтобы компания, которая меня нанимала, заработала на мне Х10, а лучше — Х100
Потому что в таком случае и я без денег не останусь, и компании будет капец как выгодно
WIN-WIN
Я не хочу быть посредственным!
Просто не хочу.
Так что вот мои вопросы:
- Какие цели у юнита на год, и у команды, куда меня рассматриваете, в частности?
- Какую роль продукт оказывает на бизнес и является ли ключевым?
- Какие ожидания у бизнеса от продукта? На какие метрики смотрит бизнес?
- Чем отличаетесь от конкурентов / планируете отличаться и кто они?
- Какие направления развиваете: B2B/B2C/B2G, и какие по ним планы?
- Довольны ли вы сейчас работой команды, куда меня нанимают, или есть критические поинты для улучшения?
----
В общем, я отказался от вопросов про ЯП 😂
Ну мне реально стало не особо интересно.
Этот чеклист точно не для тех, кто ищет первую работу.
Но зато тот 1%, в который попадает матч, выкатывает очень приятные офферы
А какие вопросы на финалах задаёшь ты? Интересно будет глянуть комменты
P.S. экспериментирую с форматами постов так что бахни 🌭 если зашло
🌭88❤🔥6🍓2
Стартует запись на курс по графам!
Курс пройдет с 25 ноября по 9 декабря
- Программа из тем
- Про домашки
- Про проверку домашек
- Как попасть на курс
- ...
https://telegra.ph/Kurs-Grafy-s-0-do-PRO-11-05
Число мест для live-участия ограничего!
Для тех, кто решится на онлайн - советую подавать заявку как можно раньше,
потому что уже начали анализировать заявки
P.S. обязательно буду делиться с вами ключевыми инсайдами по ходу курса, чтобы все могли получить пользу
Курс пройдет с 25 ноября по 9 декабря
- Программа из тем
- Про домашки
- Про проверку домашек
- Как попасть на курс
- ...
https://telegra.ph/Kurs-Grafy-s-0-do-PRO-11-05
Число мест для live-участия ограничего!
Для тех, кто решится на онлайн - советую подавать заявку как можно раньше,
потому что уже начали анализировать заявки
P.S. обязательно буду делиться с вами ключевыми инсайдами по ходу курса, чтобы все могли получить пользу
❤🔥3🌭2