Задача с собеседования в Яндекс

Дана прямоугольная матрица, заполненная нулями и единицами. Единицы это земля, нули это вода. Из каждой ячейки, заполненной 1, можно попасть в другую ячейку с 1, если каждая из их координат отличается не более, чем на единицу, т.е. каждая ячейка имеет до 8 соседей

Требуется найти количество таких "островов" в матрице

Решение:

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

Так как теперь их посчитать? Запускаем дфс из каждой единичной ячейки, если до этого она не посещалась, дфс обходит все вершинки из острова, отмечает их посещенными и увеличивает счетчик компонент связности, вот и всё.
Решение за O(NM)

@algoses

Поступашки объявляют набор на курс по АВ тестам!

Мечтаешь стать крутым аналитиком или дата сайентистом и с легкостью тащить собесы, но тебе не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании такой, как Яндекс, ВК, Сбер, Авито или Тинькофф? Тогда тебе к нам!

Курс заточен под практику, вся теория будет разобрана на конкретных задачах и кейсах, которые встречаются на работе и собесах. На курсах вас ждут пет проекты и мини проекты, которые пойдут в ваше портфолио, разбор реальных тестовых заданий бигтехов, разбор майского контеста на стажировку в Т-банк, разбор реальных технических вопросов с собесов!

Курс стартует 04.05 и длится 5 недель, каждую неделю по 2 урока, более 40 часов материалов с последующим доступом к записям и ДЗ с проверкой! На семинарах общаются с каждым учеником (можете посмотреть на то, как проходят семинары вот здесь ). Ежедневная связь, сильное окружение, помощь в составлении анкеты, резюме, пробные собесы, контесты, персональные рекомендации, инсайды и домашнее задание с проверкой, код ревью с разбором от преподавателя! Все будет еще круче, чем на всех прошлых курсах (отзывы тут).

Программа и Подробности.

📊 Цена очень низкая! Всего 8'500 рублей за курс

Для вопросов и покупок пишем администратору.

Задача с собеседования в Яндекс

Для заданной строки найти длину наибольшей подстроки без повторяющихся символов.
Например:
abcabcbbddee -> 3 (abc)
bbbbb -> 1 (b)
pwwkew -> 3 (wke)

Решить желательно за линию

Решение:

Решение сложнее O(N) - плохо
С двумя проходами по строке - нормально
С одним проходом по строке - хорошо

Для каждой позиции будем находить самую длинную подстроку, заканчивающуюся в данной позиции. Если мы нашли ответ для позиции i (обозначим за P[i]) - легко посчитать ответ для позиции i + 1: для этого надо найти самое правое вхождение символа S[i+1] в префиксе S[1...i] и взять максимум из найденной позиции и P[i].
Если символов мало, то последнее вхождение каждого символа можно поддерживать в массиве, иначе его стоит хранить в hash_map (это важно уточнить у собеседующего)
Решение за O(N)

Также не забываем в реализации проверить
1) Работу на пустой строке и строке из одного символа
2) Ответ для любой непустой строки хотя бы 1

@algoses

Методы обнаружения выбросов (Часть 1)

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

📌 Z-оценка

Метод Z-Score определяет выбросы, измеряя отклонение точки данных от среднего значения в единицах стандартного отклонения. Если Z-Score
(Z = (x - mean) / sd, где x - точка данных, mean - среднее значение, sd - стандартное отклонение)
точки оказывается значительно выше или ниже нуля, это означает, что она сильно отличается от большинства данных и может считаться выбросом. Этот метод особенно эффективен для данных с нормальным распределением, где основная масса значений сосредоточена вокруг среднего.

📌 Interquartile Range (IQR)

Посчитаем разницу между первым и третьим квантилем (то есть возьмём средние 50% данных и разницу между максимальным и минимальным) - это значение называется IQR, а теперь рассчитаем нижнюю и верхнюю границы
(Q1 - 1.5 * IQR, Q3 + 1.5 * IQR)
коэффициент можно брать на своё усмотрение. Все данные, которые не попадут в эти границы - выбросы. Этот метод является более устойчивым к экстремальным значениям.

📌 Критерий Граббса

Важно, что этот критерий требует нормальность, поэтому предварительно нужно проверить (например с помощью Шапиро-Уилка), также этот критерий предназначен для обнаружения одного выброса. Затем считаем статистику Граббса:
G = max(|x_i - X_mean|) / sd
X_mean - среднее значение, sd - среднее отклонение
Выбираем уровень значимости и сравниваем с критическим значением, аппроксимационную формулу можно в вики глянуть, если полученное значение больше критического, то точка является выбросом.

@ProdAnalysis

Финальная распродажа в честь ДОДов ШАДа! Объявляем скидку в 65% до 14.04! Любой курс серии можно приобрести всего за 20’000 7'000 рублей:

➡️ алгоритмы
➡️ теория вероятностей
➡️ линейная алгебра
➡️ математический анализ

Для вопросов и покупок пишем администратору.

Торопитесь! Количество мест на каждый курс ограничено.

Финальная распродажа в честь ДОДов ШАДа! Объявляем скидку в 65% до 14.04! Любой курс серии можно приобрести всего за 20’000 6'000 рублей:

➡️ алгоритмы
➡️ теория вероятностей
➡️ линейная алгебра
➡️ математический анализ

Для вопросов и покупок пишем администратору.

Торопитесь! Количество мест на каждый курс ограничено.

⚡️ Python теперь в Telegram!

Ребята сделали крутейший канал, где на простых картинках и понятном языке обучают Python, делятся полезными фишками и инструментами

Подписывайтесь: @PythonPortal

Задача с собеседования в Яндекс

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

Примеры:
In: /foo/bar//bax/asdf/quux/..
Out: /foo/bar/bax/asdf

In: a/../../b
Out: ../b

In: /a/../../b
Out: /b

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

def normalize(path: str) -> str:
if not path:
return "."

is_absolute = path.startswith('/')
parts = []

for part in path.split('/'):
if part == '' or part == '.':
continue
elif part == '..':
if parts and parts[-1] != '..':
parts.pop()
else:
if not is_absolute:
parts.append(part)
else:
parts.append(part)

normalized_path = '/'.join(parts)

if is_absolute:
normalized_path = '/' + normalized_path

if not normalized_path:
return '/' if is_absolute else '.'

return normalized_path

Асимптотика O(N)

@algoses

⌨️ А ты знаешь, что сейчас ИТ-компаниям не нужны джуниоры?

Большинство выпускников российских вузов мечтают начать работу в ИТ в качестве джуна. Но им трудно попасть в хорошие ИТ-компании, потому что их квалификации не хватает. Даже умным ребятам требуется несколько лет, чтобы научиться по-настоящему хорошо программировать.

✅ Есть вуз, где крепкими джуниорами становятся уже на втором курсе. Это Институт iSpring – ИТ-вуз нового типа, созданный глобальной ИТ-компанией iSpring.

Учебная программа в Институте основана на лучших традициях инженерной школы и передовом опыте создания первоклассных продуктов для глобального ИТ-рынка. Преподаватели из ведущих ИТ-компаний!

⚡️ Фундаментальность и максимальное количество практики на парах позволит тебе работать над реальными проектами уже после первого курса

Наши студенты за 4 года учёбы становятся настоящими профессионалами, которые самостоятельно могут создавать топовые ИТ-продукты.

❗️Хочешь узнать, как у нас всё организовано? Приходи на Погружение в программирование. Напишешь игру на JavaScript под руководством наставников-студентов нашего Института. У тебя всё получится, даже если ты ни разу не программировал.

Решайся!

ЗАПИСАТЬСЯ НА ПОГРУЖЕНИЕ

Когда: 19-20 апреля
Где: Йошкар-Ола, офис ИТ-компании iSpring
Цена: 1980 ₽

Реклама АНО ВО «РУМТ»
ИНН 1215144727
erid: 2SDnjeMX1c8

⌨️ А ты знаешь, что сейчас ИТ-компаниям не нужны джуниоры?

Большинство выпускников российских вузов мечтают начать работу в ИТ в качестве джуна. Но им трудно попасть в хорошие ИТ-компании, потому что их квалификации не хватает. Даже умным ребятам требуется несколько лет, чтобы научиться по-настоящему хорошо программировать.

✅ Есть вуз, где крепкими джуниорами становятся уже на втором курсе. Это Институт iSpring – ИТ-вуз нового типа, созданный глобальной ИТ-компанией iSpring.

Учебная программа в Институте основана на лучших традициях инженерной школы и передовом опыте создания первоклассных продуктов для глобального ИТ-рынка. Преподаватели из ведущих ИТ-компаний!

⚡️ Фундаментальность и максимальное количество практики на парах позволит тебе работать над реальными проектами уже после первого курса

Наши студенты за 4 года учёбы становятся настоящими профессионалами, которые самостоятельно могут создавать топовые ИТ-продукты.

❗️Хочешь узнать, как у нас всё организовано? Приходи на Погружение в программирование. Напишешь игру на JavaScript под руководством наставников-студентов нашего Института. У тебя всё получится, даже если ты ни разу не программировал.

Решайся!

ЗАПИСАТЬСЯ НА ПОГРУЖЕНИЕ

Когда: 19-20 апреля
Где: Йошкар-Ола, офис ИТ-компании iSpring
Цена: 1980 ₽

Реклама АНО ВО «РУМТ»
ИНН 1215144727
erid: 2SDnjeMX1c8

Задача с собеседования в Яндекс

Имеется n пользователей, каждому из них соответствует список e-mail-ов (всего m). Например:

user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru
user2 -> foo@gmail.com, ups@pisem.net
user3 -> xyz@pisem.net, vasya@pupkin.com
user4 -> ups@pisem.net, aaa@bbb.ru
user5 -> xyz@pisem.net

Считается, что если у двух пользователей общий email, значит, это один и тот же пользователь.

Требуется реализовать алгоритм, выполняющий слияние пользователей. На выходе должен быть список пользователей с их e-mail-ами (такой же как на входе). В качестве имени можно брать любое из исходных имен. Список e-mail-ов должен содержать уникальные e-mail-ы. Параметры n и m произвольные.

В указанном примере ответ будет такой
user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru, ups@pisem.net, aaa@bbb.ru
user3 -> xyz@pisem.net, vasya@pupkin.com

Нужно решение с линейной асимптотикой

Решение:
Довольно стандартная задача
Построим граф на пользователях такой, что два пользователя лежат в одной компоненте связности тогда и только тогда, когда они должны быть объединены в одного пользователя. Для этого используем хеш-мапу: для каждого e-mail-а список пользователей.
Соединим последовательно цепочкой этих пользователей друг с другом в графе. Граф будет иметь размер порядка O(n + m). После этого найдем в графе компоненты связности и восстановим по ним ответ на задачу

Итоговая асимптотика O(n + m)

@algoses

VK и МФТИ запускают магистратуру «Искусственный интеллект и социальные медиа». Предусмотрено 15 бюджетных мест.

Обучение на программе начнется уже в сентябре 2025 года. Магистратуре для тех, кто хочет развивать карьеру ML- или NLP-инженера, дата-аналитика, разработчика рекомендательных систем и поисковых технологий.

Студентов ждет обучение на прикладных задачах под руководством экспертов департамента AI VK. Среди дисциплин — анализ и обработка больших данных, задачи и модели NLP, генеративные языковые и визуальные модели, глубокое обучение, лингвистические основы создания корпусов. 

👉🏻Подробнее о магистратуре тут.

Специально для подготовки к поступлению VK Education открыла набор на бесплатную подготовительную программу — участники могут повысить шансы на поступление и протестировать обучение на магистратуре. Заявки на неё принимаются до 27 апреля.

@algoses 

Задача с HFT компании.

Задача встретилась у одного ученика на собеседование в HFT.
Сразу скажу, задача сложнее, чем Яндекс-задачи.

Дается массив целых чисел a и число k.
Значения подмасива [l, r] будем считать как (r-l+1)*min(a[l], a[l+1], ..., a[r]).
(То есть значения подмасива - это длина массива на минимальное число из подотрезка)

Вы имеете право рассматривать подотрезок [l, r] если l <= k <= r (напомню k дали в инпуте). Найти максимальное значение.

Решение:
Давайте переберем позицию i, и предположим это минимальный элемент какого-то подотрезка.
То есть мы говорим что a[i] минимальное число на каком-то подотрезке [L, R], где L <= k <= R и L <= i <= R.

Значит значения этого подотрезка это a[i] * (R - L + 1). Какие L, R нужно брать для зафиксированного i?
Вам нужно найти минимальный L, и максимальный R что в подотрезке [L, R] число a[i] минимальное.

Если мы для каждой позиции i будем знать L, R то мы сможем найти ответ. Ответ просто max(a[i] * (R[i] - L[i] + 1)), при условии что
L[i] <= k <= R[i].

Теперь поговорим, как же все-таки эти отрезки находить для каждой позиции i.

Эти отрезки мы можем посчитать монотонными стеками. Сначала пройдем слева направо, храня возрастающий монотонный стек.

Когда мы пытаемся добавить число a[i] в стек, мы удаляем сколько-то элементов, замечу, что для этих удаляемых позиций правая граница будет как раз таки i.

То есть мы, когда удаляем число из стека, мы понимаем, что для удаляемого элемента правый отрезок — это i.

Аналогично пройдемся справа налево и посчитаем левые границы.

Решение O(n). Если на собесе решали не за линию то засчитывали фейл.


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

@algoses

Задача с HFT компании.

Хотите после летней сессии отправиться с друзьями на музыкальный фестиваль в Сочи? Тогда самое время зарегистрироваться в «Здоровой Олимпиаде» 😎

В этом году «Пятёрочка» запускает первую бесплатную онлайн-олимпиаду для студентов, которая проверит знания по теме здорового образа жизни и правильного питания. Участвовать могут учащиеся колледжей, техникумов, училищ и вузов.

От тебя нужна лишь регистрация на платформе и 45 минут на прохождение Олимпиады в любой день с 3 по 9 апреля.

Все финалисты и победители получат сертификаты, книги и цифровые подарки. А среди вузов и учреждений СПО разыграем супер-призы. Самый активный вуз получит грант на участие в музыкальном фестивале в Сочи, а самый-самый среди колледжей, училищ или техникумов — 1 000 000 рублей 🎉

Время чекнуть свою ЗОЖ-грамотность и поучаствовать в розыгрыше подарков.

Клик, чтобы присоединиться!

🎁 Книг и курсов много не бывает! Дарим доступ к курсам и лучшим книгам!

Мы разыграем еще 3 места на наших курсах и коллекцию очень полезных книг для подготовки к собеседованию.

Условия участия максимально простые:

🔸 подписаться на @vistehno
🔸 подписаться на @postypashki_old

Победители рандомно получат доступы к курсам или одну из этих великолепных книг:

— Математика для Data Science. Управляем данными с помощью линейной алгебры, теории вероятностей и статистики
— Python БОЛЬШАЯ КНИГА ПРИМЕРОВ
— Книга Kaggle. Машинное обучение и анализ данных
— Руководство по созданию систем машинного обучения: от основ до мощных инструментов
— Наука о данных. Базовый курс | Келлехер Джон Д.
— Математика для Data Science
— Разберись в Data Science. Как освоить науку о данных
— Грокаем алгоритмы искусcтвенного интеллекта

Итоги подведем 22 апреля в 22:00 при помощи бота, который рандомно выберет победителя. Удачи ❤️

🎁 Книг и курсов много не бывает! Дарим доступ к курсам и лучшим книгам!

Мы разыграем еще 3 места на наших курсах и коллекцию очень полезных книг для подготовки к собеседованию.

Условия участия максимально простые:

🔸 подписаться на @vistehno
🔸 подписаться на @postypashki_old

Победители рандомно получат доступы к курсам или одну из этих великолепных книг:

— Математика для Data Science. Управляем данными с помощью линейной алгебры, теории вероятностей и статистики
— Python БОЛЬШАЯ КНИГА ПРИМЕРОВ
— Книга Kaggle. Машинное обучение и анализ данных
— Руководство по созданию систем машинного обучения: от основ до мощных инструментов
— Наука о данных. Базовый курс | Келлехер Джон Д.
— Математика для Data Science
— Разберись в Data Science. Как освоить науку о данных
— Грокаем алгоритмы искусcтвенного интеллекта

Итоги подведем 22 апреля в 22:00 при помощи бота, который рандомно выберет победителя. Удачи ❤️

Задача с собеседования в Яндекс

Дан некоторый алфавит и строка. Необходимо найти в строке панграмму минимальной длины, где панграмма - это такая подстрока исходной строки, в которую входят все буквы из алфавита (но необязательно только они).

Пример:
A = {a, b, c}
s = "dfagabkaceb"
Ответом могут быть строки "bkac" и "aceb"

Решение:
Халявные два указателя буквально подарят тебе оффер
Будем двигать правый указатель, расширяя подстроку, пока не включим все символы из алфавита. Как только все символы оказались в окне, будем двигать левый указатель, обновляя ответ и сохраняя все необходимые символы.
Обязательно надо проверить, что панграмма с концом в конце исходной строки также рассматривается.
Асимптотика O(N)

В целом, можно предложить алгоритм без сдвига начала строки за O(NS), что тоже прокатит
Типичные ошибки:
1) Не обработать ненахождение панграммы в принципе
2) Неправильно похендлить алфавит длиной один
3) Ненахождение ответа в конце текста

@algoses

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

25 июня на сцене Live Арена в Москве уже во второй раз пройдет Young Con — масштабный фестиваль для всех, кто любит технологии и хочет начать работать в IT. В этот раз фестиваль откроет двери для 8 тысяч человек, и впервые — не только для студентов и начинающих спецов, но и для школьников 9-11 классов, которые смогут посетить зоны технических вузов. Еще в программе воркшопы, лекции, квесты, нетворкинг и финал баттла вузов по программированию. В общем, будет время как поучиться, так и отдохнуть.

В Летних школах стало еще больше направлений — их уже 7. Теперь можно попасть на интенсивы не только для фронтендеров, бэкендеров, мобильных разработчиков, аналитиков и менеджеров, но и инженеров по тестированию и DevOps/SRE.

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

На Young&&Yandex уже можно узнать подробнее про все проекты и подать заявку.

@algoses

⚡️Решаем тестовое задание в Магнит Tech на позицию аналитика данных в прямом эфире

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

Эти навыки приходят с опытом нарешивания боевых задач и тестовых, одно из которых мы разберем на бесплатном вебинаре с Павлом Беляевым - руководителем группы дата-аналитиков в компании Яндекс eLama.

Что мы будем делать на вебинаре:
🟠познакомимся с тестовым заданием одной из крупнейших ритейл-сетей «Магнит»;
🟠с помощью SQL потренируемся искать нужное в товарном ассортименте;
🟠с помощью Python научимся определять слова-палиндромы.

А ещё — увидим тестовое задание по SQL eLama, безотказно работавшее 6 лет. В нем есть важный нюанс, на котором многие сыпались!

🕗 Встречаемся 25 марта 18:30 по МСК

😶Зарегистрироваться на бесплатный вебинар

Задача с Яндекса.

Наконец то встретилась новая задача, которая к тому же есть на литкоде.

Дается массив a. Вы стоите на самой левой позиции и хотите попасть на самую последнюю позицию.
Когда вы стоите на позиции i, вы можете прыгнуть максимум на a[i] позиций вперед.
Вернуть true если можно с левого края попасть на правый край.

Пример
3, 1, 2, 0, 0, 4.
Ответ false.

Решение:
От i той позиции мы можем прыгнуть на любую позицию из [i, a[i]+i]. Будем воспринимать это как отрезок.
Тогда у нас получается n отрезков. Они между собой как то пересекаются.

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

Вам надо слить отрезки и убедиться что в одном отрезки находится позиция 0 и позиция n-1.

Слить все отрезки мы можем за О(n), так как отрезки отсортированы по первому числу. (кстати задача про сливания отрезков это старая задача Яндекса)
Ссылка в комментариях.

@algoses

🎁 Дарим доступ к курсам и замечательную литературу для подготовки к собесу и !

На этот раз мы разыграем целых 3 места на наших курсах и коллекцию очень полезных книг для подготовки к собеседованию.

Условия участия максимально простые:

🔸 подписаться на Machine Learning
🔸 подписаться на Поступашки

Победители рандомно получат доступы к курсам или одну из этих великолепных книг:

— 40 алгоритмов, которые должен знать каждый программист на Python
— Машинное обучение. Подготовка к сложному интервью
— Путь инженера-программиста: развитие навыков для успешной карьеры
— Математика для Data Science
— Как быть успешным в Data Science.
— Грокаем алгоритмы искусcтвенного интеллекта

Итоги подведем 19 апреля в 19:00 при помощи бота, который рандомно выберет победителя. Всем удачи ❤️

Задача с собеседования в Яндекс

Дан список ненулевой длины, состоящий из направлений
L - left
R - right
D - down
U - up
Каждый элемент перемещает вас на 1 в заданном направлении.

Известно, что петли (возврат в уже посещенную точку) дают нулевое перемещение и являются пустой тратой времени. Нужно удалить из списка все петли и вернуть оптимизированный короткий маршрут, например:
[R, D, L, U, R] -> [R]
[R, D, L, R, U, U, R] -> [R, U, R]

Важно отметить, что цель не просто попасть в ту же самую конечную точку, но и придерживаться первоначального маршрута (не срезать по прямой):
[D, R, U] -> [D, R, U]

Вернуть нужно массив направлений.
Ограничения: O(N) по времени и памяти

Решение:

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

Решение по-лучше - есть хешсет (unordered_set) с посещенными координатами и список координат. Как только видим, что в хешсете что-то есть, отступаем по списку, пока не найдем ту самую координату, по пути очищая хешсет. Поиск в хешсете это O(1), поэтому получаем линию по времени и памяти. Просто и быстро, но мало кто догадывается на собесе

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

Третье хорошее решение - есть хешмапа и вектор посещенных точек. В хешмапе храним ласт индекс точки в векторе

Стоит сказать, что решения не уникальны - если идти с конца, можно получить другое решение

@algoses

🔥 Самые нужные каналы для Data Scientist, чтобы расти в доходе 💸

• Data Science | Вопросы собесов
• Data Science | Вакансии с удаленкой
• Data Science | Тесты

Подпишись, чтобы не потерять ☝️

Поступашки продолжают набор на курс по теории вероятностей и математической статистике!

Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на курс!

Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что вам реально понадобится! Хочешь подробностей? На нашам сайте можно найти программу и отзывы на каждый курс.

Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты!

📊 Цена очень доступная: 20’000 10'000 рублей за каждый курс с учетом скидки (до 16.03) доступна скидка в 50% при покупке любого курса). Далее базовая цена повышается до 20’000 рублей за курс.

Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!

Еще курсы серии:
➡️ алгоритмы старт 15.03
➡️ теория вероятностей старт 16.03
➡️ линейная алгебра старт 23.03
➡️ математический анализ старт 30.03

Задача с собеседования в Яндекс

Дано дерево:
struct Node {
Node *l, *r;
int value;
}

Требуется написать функцию, которая проверяет, является ли дерево симметричным

Решение:

Будем рекурсивно спускаться в детей и проверять у каждого узла наличие ребенка. Если у какого-то ребенка есть путь вниз, а у другого нет, то дерево не является симметричным. Также параллельно в спуске будем проверять симметричность значений value

bool isSymmetric(Node* root) {
return root == NULL ? true : isMirrored(root->l, root->r);
}

bool isMirrored(Node* a, Node* b) {
if (a == NULL && b == NULL)
return true;

if (a != NULL && b != NULL)
return a->value == b->value && isMirrored(a->l, b->r) && isMirrored(a->r, b->l);

return false;
}

@algoses

Разыгрываем курс

Кто решит первый Задачу 1, получит любой курс абсолютно бесплатно. Кто решит Задачу 2, получит 50% скидку на любой курс. Решения первой задачи кидайте в комментарии к посту, а решение второй задачи кидайте сюда @menshe_treh. Оформлять можно как удобно, главное чтобы было читаемо и аккуратно.

Задача 1
Пусть n ⩾ 2. Найдите наибольшее p, для которого неравенство
(x_1)^2 + (x_2)^2 + (x_3)^2 + ... +( x_n)^2 ⩾ p(x_1x_2 + x_2x_3 +x_3x_4 +···+x_{n−1}x_n)
выполняется при всех x_1, x_2 ,..., x_n.

Задача 2
При каких a_n, b_n многочлен a_nx^(n+1) + b_nx^(n) + 1 делится на (x−1)^2.

@matesha_shad

ПРАЗДНИЧНАЯ РАСПРОДАЖА! В честь 8 марта мы объявляем скидку на все курсы серии 50% до 9 марта включительно.

Дарите своим любимым не веники, а по-настоящему полезные вещи! Так же на курсах будет разбор контеста в ШАД 2025 года, а еще вернут потраченные деньги на курс, если первым сдадите все дз.

➡️ алгоритмы старт 08.03
➡️ теория вероятностей старт 16.03
➡️ линейная алгебра старт 23.03
➡️ математический анализ старт 30.03

📊 Цена: 20'000рублей 10’000 рублей за каждый курс с учетом скидки (до 9 марта в честь праздника) доступна скидка в 50% при покупке любого курса). Далее базовая цена повышается до 20’000 рублей за курс.

Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено

Задача с собеседования в Яндекс

Дана строка, нужно вывести для каждого символа в ней максимальное количество непрерывных повторений этого символа в строке
Например, для строки "aafbaaaaffc" ответом будет
a: 4
b: 1
c: 1
f: 2

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

def countSymbs(s):
d = {}
prev = ''
cnt = 1
for char in s:
if char == prev:
cnt += 1
else:
if prev and d.get(prev, 0) < count:
d[prev] = count
count = 1
prev = char

if prev and d.get(prev, 0) < count:
d[prev] = count

return d

assert countSymbs('aafbaaaaffc') == {'a': 4, 'b': 1, 'c': 1, 'f': 2}

@algoses

Ребята сделали крутейший канал про айти

Здесь сложные темы объясняют на простых картинках и понятном языке, а еще делятся полезными ресурсами и свежими новостями из мира IT

Подписывайтесь: @IT_Portal

Задача с собеседования в Яндекс

Дана строка (возможно, пустая), содержащая заглавные латинские буквы. Нужно написать функцию, которая сожмет эту строку следующим образом:

AAABCCCCCDD -> A3BC5D2

Ещё надо выдавать ошибку, если на вход приходит недопустимая строка.

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

Типичные ошибки:
1) забыл проверить наличие одного символа
2) забыл вывод последней группы
3) забыл сгенерировать ошибку

Тест-кейсы, которые обязательно будет прогонять проверяющий:
1) пустая строка
2) 1 символ или 2 разных символа
3) последовательность из 9 или более одинаковых символов
4) недопустимая строка

@algoses

Хотите научиться автоматизировать процессы обработки данных как в Бигтехе?

Чтобы проанализировать большой массив данных, его нужно обработать. Обычно это происходит в три этапа: извлечение, трансформация и загрузка (или ETL). Но чем больше становится данных, тем труднее управлять этим процессом вручную — автоматизировать его можно с помощью Airflow.

Чтобы научиться работать с Airflow, приходите на бесплатный вебинар, где Антон Шишков, опытный Software Engineer из бигтех-компании, — поделится с вами своими знаниями и лучшими практиками работы с Airflow на примере автоматизации сбора данных.

Что мы будем делать на вебинаре:
🟠 Познакомимся с Airflow: узнаем, как он может упростить работу и повысить эффективность;
🟠 Узнаем об операторах и сенсорах: как использовать для создания гибких и надежных конвейеров данных;
🟠 Напишем базовые и продвинутые DAG'и, чтобы вы могли применить их на практике;
🟠 Разберем, как использовать Docker, FastAPI, Postgres, Clickhouse и Minio для автоматизации ETL-процессов.

🕗Встречаемся 4 марта в 19:30 по мск

Зарегистрироваться на бесплатный вебинар

СКИДКИ, СКИДКИ, СКИДКИ!!

Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК?

Специально и исключительно для подписчиков нашего канала в честь начала весны Поступашки объявляют ФИНАЛЬНЫЕ скидки в 40% до 3 марта! Любой курс можно приобрести всего лишь за 5400 рублей:

➡️ аналитика
➡️ машинное обучение старт
➡️ машинное обучение хард
➡️ бэкенд разработка
➡️ фронтенд разработка
➡️ инженер данных

Программа и Подробности.

Для записи и всех вопросов пишем администратору: @menshe_treh

СКИДКИ, СКИДКИ, СКИДКИ!!

Мечтаешь стать крутым специалистом и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, Тинькофф или ВК?

Специально и исключительно для подписчиков нашего канала в честь начала весны Поступашки объявляют ФИНАЛЬНЫЕ скидки в 40% до 3 марта! Любой курс можно приобрести всего лишь за 5400 рублей:

➡️ аналитика
➡️ машинное обучение старт
➡️ машинное обучение хард
➡️ бэкенд разработка
➡️ фронтенд разработка
➡️ инженер данных

Программа и подробности.

Для записи и всех вопросов пишем администратору: @menshe_treh

Задача с собеседования в Яндекс

Точка равновесия массива
Дан массив целых чисел. Найдите в нем такой индекс, что сумма элементов слева от него равна сумме элементов справа от него.
Важно решить задачу за O(N) времени и за O(1) памяти.

Решение:
Предварительно посчитаем сумму всего массива
Потом пройдемся по массиву, поддерживая левую сумму, и будем сравнивать её с правой суммой (вся сумма - левая сумма - текущий элемент)

Удовлетворительным решением будет использование частичных левых и правых сумм (но это O(N) памяти)

Плохим решением будет вложенный цикл с подсчетом правых сумм на каждом шаге (уже не O(N) времени очев)

Метод должен корректно отрабатывать в крайних случаях (пустой массив, массив с одним элементов и пр.) и уметь возвращать факт отсутствия решения

@algoses

Старшеклассники, спешим на кейс-чемпионат DEADLINE!

Центральный университет приглашает учеников 10—11-х классов, которым интересны экономика, бизнес и ИТ. Здесь можно попробовать себя в реальных задачах от финтех-компаний. А еще — прокачать мышление, познакомиться с единомышленниками и получить шанс выиграть призы.

Вот что получат победители:
— Грант до 100% на обучение в Центральном университете;
— Ужин с профессорами Центрального университета и топ-менеджерами финтеха;
— Яндекс Станцию;
— Стильный мерч.

Участие в чемпионате полностью бесплатно.
Финал пройдет в Москве — в штаб-квартире Т-Банка. Здесь можно познакомиться с лидерами ИТ и бизнеса, а еще — презентовать идею своего проекта.

Ты в деле? Успей зарегистрироваться до 9 марта!

Реклама АО "Центральный университет", инн7743418023, erid: 2RanykawUL9

Новая задача Яндекса:
Дается массив целых чисел. Найти максимальный по длине подотрезок в котором сумма четная.
На самом деле эта задача очень похожа на старую задачу яндекса (задача 974. Subarray Sums Divisible by K на литкоде).
Решить без дополнительной памяти.

Решение:
Если бы можно было использовать доп память то посчитали префиксную сумму. В таком случае сумма на подотрезке четная если prefix_sum[r] - prefix_sum[l-1]) имеют одинаковую четность.

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

Давайте хранить две переменные:
first_odd_pos: позиция где в первый раз увидели нечетную сумму префикса
first_odd_pos: позиция где в первый раз увидели четную сумму префикса

идем слева направо по массиву циклом i и поддерживаем сумму (sum). Если сумма четная то пытаемся обновить i-first_odd_pos, иначе через i-first_odd_pos.
PS: Мы сохраняем только первое вхождение потоому-что хотим максимизировать подотрезок

Время работы O(n)

Код в комментариях

@algoses

Свершилось! Поступашки открывают набор на новую линейку математических курсов 🎓

Хочешь поступить в ШАД, Ai Masters, или ААА? А может ты мечтаешь тащить собесы и поступить в крутую магу, но тебе не хватает фундамента? Узнал себя? Тогда записывайся у администратора на любой из курсов:

➡️ алгоритмы старт 08.03
➡️ теория вероятностей старт 16.03
➡️ линейная алгебра старт 23.03
➡️ математический анализ старт 30.03

Наши курсы заточены на практику и конкретные задачи, вся теория будет разобрана на конкретных задачах и примерах, которые будут на экзаменах и на собесах. Ничего нудного и скучного! Изучаем только то, что вам реально понадобится! Хочешь подробностей? На нашам сайте можно найти программу и отзывы на каждый курс.

Помимо кучи авторских задач мы даем доступ к уникальной закрытой базе заданий ШАДа, разбор реального контеста в ШАД, разбор ВСЕХ задач с собеседований в ШАД, Ai Masters, ААА! Более того, вы получите эксклюзивные материалы для проверяющих с собесов, пробный экзамен, инсайды, персональные рекомендации, собес с подробной консультацией и дальнейшим сопровождением вплоть до поступления в место мечты!

📊 Цена очень доступная: 20'000рублей 9’000 рублей за каждый курс с учетом скидки (для подписчиков нашего ТГК до 26 февраля в честь старта продаж доступна скидка в 55% при покупке любого курса). Далее базовая цена повышается до 20’000 рублей за курс.

Для вопросов и покупок пишем администратору и не тянем с этим: на каждом курсе количество мест ограничено!

Поступашки продолжают набор на курс по машинному обучению хард!

Мечтаешь стать крутым дата сайнтистом и с легкость тащить собесы, но не хватает фундамента и практики на реальных проектах? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, ВК, Сбер или Тинькофф? Тогда тебе к нам!

Курс заточен под практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. На курсах вас ждут куча пет проектов такие как рекомендательная система, система поисковых подсказок, модель предсказания спроса и куча мини проектов, которые пойдут в портфолио. Поста не хватит, чтобы описать все, программа реально мощная. Также вас ждет разбор реальных тестовых заданий бигтехов, разбор актуального контеста на стажировку в Яндекс, список реальных технических вопрос с собесов и много других приятных бонусов как разбор всех задач с алгособесов Яндекса. А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании😎

Более того, ты сможешь получить ВСЕ ДЕНЬГИ потраченные на курс обратно, если первым решишь все домашние задание 😎😎

Курс длится 6 недель, каждую неделю по 2 урока, огромное количество дополнительного контента, более 40 часов контента с последующим доступом к записям и ДЗ с проверкой! На семинарах с каждым учеником общаются по очереди, полноценное общение как здесь. Ежедневная связь, сильное окружение, помощь по составлению анкеты, резюме, пробные собесы, контесты, персональные рекомендации, инсайды и домашнее задание с проверкой, код ревью и с разбором от преподавателя, который отвечает даже после завершения курса! Все будет еще круче, чем на всех прошлый курсах (отзывы тут). Все для того, чтобы получить топовый оффер уже весной или мы вернем потраченные деньги!

Программа и Подробности.

Цена 8000р, но только до 21.02 скидка 20% на мл хард и дата инженер.
Если проходили наши курсы ранее и готовы оставить о них видео отзыв, то цена 6500р.

Для записи и всех вопросов: @menshe_treh

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

Еще курсы серии, на которые идет набор:
➡️ инженер данных
➡️ аналитика
➡️ машинное обучение старт
➡️ машинное обучение хард
➡️ бэкенд разработка
➡️ фронтенд разработка
➡️ алгоритмы

Задача с собеседования в Яндекс

Дан массив целых чисел nums и целое число target. Нужно найти такую тройку чисел в массиве с различными индексами, что их сумма наиболее близка к target.
Вывести необходимо сумму трех чисел.

Пример
Ввод: nums = [-1,2,1,-4], target = 1
Вывод: 2         (-1 + 2 + 1 = 2)

Input: nums = [0,0,0], target = 1
Output: 0
Решение:
Пусть нужно найти тройку i, j, k (i != j != k), у которой nums[i] + nums[j] + nums[k] == target
Отсортируем массив, будем поддерживать наилучшую сумму и минимальную разницу между этой суммой и target
Переберем циклом указатель i, инициализируем j = i + 1, k = n - 1 и пока j < k каждый раз будем проверять:
- если текущая сумма равна target, то выводим ответ и заканчиваем
- если сумма меньше target, то двигаем j вправо
- иначе двигаем k влево
Сохраняем минимальную разницу, если она меньше, чем была, то сохраняем сумму

Асимптотика O(n^2)

@algoses

Поступашки продолжают набор на курс по бэкенд разработке!

Мечтаешь стать крутым разработчиком и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, ВК, Сбер или Тинькофф? Тогда тебе к нам!

Курс заточен под практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. На курсах вас ждут куча пет проектов такие как image processor, реплицированное key value хранилище и куча мини проектов, которые пойдут в портфолио. Программа реально мощная и фундаментальная, что отмечают наши выпускники. Также вас ждет разбор реальных тестовых заданий бигтехов, разбор актуального контеста на стажировку в Яндекс, список реальных технических вопрос с собесов и много других приятных бонусов как разбор всех задач с алгособесов Яндекса. А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании😎

Более того, ты сможешь получить ВСЕ ДЕНЬГИ потраченные на курс обратно, если первым решишь все домашние задание 😎😎

Курс длится 6 недель, каждую неделю по 2 урока, огромное количество дополнительного контента, более 40 часов уроков с последующим доступом к записям и ДЗ с проверкой! На семинарах с каждым учеником общаются по очереди, полноценное общение как здесь. Ежедневная связь, сильное окружение, помощь по составлению анкеты, резюме, пробные собесы, контесты, персональные рекомендации, инсайды и домашнее задание с проверкой, код ревью и с разбором от преподавателя, который отвечает даже после завершения курса! Все будет еще круче, чем на всех прошлый курсах (отзывы тут). Все для того, чтобы получить топовый оффер уже весной или мы вернем потраченные деньги!

Программа и Подробности.

Цена 8000р за курс по бэкенду. Если проходили наши курсы ранее и готовы оставить о них видео отзыв, то цена 6500р.

Для записи и всех вопросов: @menshe_treh

Еще курсы серии, на которые идет набор:
➡️ аналитика
➡️ машинное обучение старт
➡️ машинное обучение хард
➡️ бэкенд разработка
➡️ фронтенд разработка
➡️ инженер данных
➡️ алгоритмы

Поступашки продолжают набор на курс по бэкенд разработке!

Мечтаешь стать крутым разработчиком и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, ВК, Сбер или Тинькофф? Тогда тебе к нам!

Курс заточен под практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. На курсах вас ждут куча пет проектов такие как image processor, реплицированное key value хранилище и куча мини проектов, которые пойдут в портфолио. Программа реально мощная и фундаментальная, что отмечают наши выпускники. Также вас ждет разбор реальных тестовых заданий бигтехов, разбор актуального контеста на стажировку в Яндекс, список реальных технических вопрос с собесов и много других приятных бонусов как разбор всех задач с алгособесов Яндекса. А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании😎

Более того, ты сможешь получить ВСЕ ДЕНЬГИ потраченные на курс обратно, если первым решишь все домашние задание 😎😎

Курс длится 6 недель, каждую неделю по 2 урока, огромное количество дополнительного контента, более 40 часов уроков с последующим доступом к записям и ДЗ с проверкой! На семинарах с каждым учеником общаются по очереди, полноценное общение как здесь. Ежедневная связь, сильное окружение, помощь по составлению анкеты, резюме, пробные собесы, контесты, персональные рекомендации, инсайды и домашнее задание с проверкой, код ревью и с разбором от преподавателя, который отвечает даже после завершения курса! Все будет еще круче, чем на всех прошлый курсах (отзывы тут). Все для того, чтобы получить топовый оффер уже весной или мы вернем потраченные деньги!

Программа и Подробности.

Цена 8000р за курс по бэкенду. Если проходили наши курсы ранее и готовы оставить о них видео отзыв, то цена 6500р.

Для записи и всех вопросов: @menshe_treh

Еще курсы серии, на которые идет набор:
➡️ аналитика
➡️ машинное обучение старт
➡️ машинное обучение хард
➡️ бэкенд разработка
➡️ фронтенд разработка
➡️ инженер данных
➡️ алгоритмы

Задача с собеседования в Яндекс

Даны два массива A и B. Нужно найти минимум abs(A[i] - B[j])

Пример:
A = {0}, B = {1}
Ответ: 1

A = {10, 0, 2}, B = {5, 100, 12}
Ответ: 2
Нужно решение без дополнительной памяти.

Решение:
Отсортируем массивы, далее поставим указатель i на начало A, j на начало B.
Для текущего i будем двигать j вправо до тех пор, пока значение abs(A[i] - B[j]) будет уменьшаться.
Иначе сдвинем i вправо и повторим алгоритм.

Можно привести решение с lower-upper_bound, но это зачтут как минус. На собесе хотят увидеть параллельный проход

Также заметим, что если A = {INT_MAX}, B = {-1}, то ответ не поместится в int.

Решение из-за сортировки получается O(nlogn)
Если в условии массивы изначально отсортированы, то O(n)

@algoses

Вот и разбор программирования на стажировку в Т-банк! Обязательно делимся с друзьями. Ждем 5 тыс просмотров на ролике и выкладываем разбор математики! Кстати а разбор контеста на стажировку в Яндекс будет только на наших курсах.

Смотрим! Смотрим! https://youtu.be/G72BCifHF_Y

⚡️ Kali LInux — канал-гайд, который научит тебя хакингу и защите информации с нуля.

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

•Лучшие бесплатные курсы и книги по Этичному Хакингу и Информационной Безопасности.
• Полезный репозиторий с подборкой ресурсов по хакингу
• Где изучать Linux и хакинг. Бесплатные курсы
•Виртуальная машина Linux для #OSINT на базе Ubuntu.
•Целая папка полезных ресурсов для Хакеров
и многое другое

🔈 Подписывайся, это самый простой способ научиться хакингу: @linuxkalii

Поступашки продолжают набор на курс по фронтенд разработке!

Мечтаешь стать крутым разработчиком и с легкость тащить собесы, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, ВК, Сбер или Тинькофф? Тогда тебе к нам!

Курс заточен под практику, вся теория будет разобрана на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. На курсах вас ждут куча пет проектов такие как интернет магазин, сайт финансов, промо сайт с анимациями и куча мини проектов, которые пойдут в портфолио. Будем использовать React, JavaScript, HTML, CSS, Typescript, препроцессоры, инструменты сборки и тд (смортите программу курса). Также вас ждет разбор реальных тестовых заданий бигтехов, разбор актуального контеста на стажировку в Яндекс, список реальных технических вопрос с собесов и много других приятных бонусов как разбор всех задач с алгособесов Яндекса. А после прохождения курса тебя ждет пробный собес с подробной консультацией и сопровождением, рефералкой в Яндекс или в другие топовые компании😎

Более того, ты сможешь получить ВСЕ ДЕНЬГИ потраченные на курс обратно, если первым решишь все домашние задание 😎😎

Курс длится 6 недель, каждую неделю по 2 урока, огромное количество дополнительного контента, более 40 часов уроков с последующим доступом к записям и ДЗ с проверкой! На семинарах с каждым учеником общаются по очереди, полноценное общение как здесь. Ежедневная связь, сильное окружение, помощь по составлению анкеты, резюме, пробные собесы, контесты, персональные рекомендации, инсайды и домашнее задание с проверкой, код ревью и с разбором от преподавателя, который отвечает даже после завершения курса! Все будет еще круче, чем на всех прошлый курсах (отзывы тут). Все для того, чтобы получить топовый оффер уже весной или мы вернем потраченные деньги!

Программа и Подробности.

Цена 8000р за курс по фронтенду. Но только до 5 февраля (по мск, включительно) скидка 25% (скидки не суммируется).
Если проходили наши курсы ранее и готовы оставить о них видео отзыв, то цена 6500р.

Для записи и всех вопросов: @menshe_treh

Еще курсы серии, на которые идет набор:
➡️ аналитика
➡️ машинное обучение старт
➡️ машинное обучение хард
➡️ бэкенд разработка
➡️ фронтенд разработка
➡️ инженер данных
➡️ алгоритмы

Задача с зарубежной компании.
Дается матрица размера n*n. Вы стоите на верхней левой координате, и хотите попасть на правую нижнюю (то есть от (1, 1) в (n, n)).
На матрице стоят числа 0 или 1. За одну операцию можно перейти в соседнюю координату заплатив стоимость, равную значению на позиции.
За какую минимальную стоимость можно попасть в (n, n) от (1, 1)?

Пример:
n = 4
[0, 1, 0, 0]
[0, 0, 0, 0]
[0, 1, 1, 0]
[1, 1, 1, 0]
Ответ 0
Решение:

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

Тогда всего лишь нужно найти кратчайшие расстояния от одной вершины к другой. Подумали об алгоритме Дейкстры?
К сожалению, такое решение не приняли.

Нужно решить за O(n*n), можно ли решить с помощью BFS?
Вообще обычным BFS задачу решить не получится, так как BFS не учитывает вес ребер, а учитывает просто количество ребер, как мы видим минимальное количество ребер не всегда оптимальный путь.

Есть так называемый BFS 0-1, нам всего лишь нужно добавлять в начало очереди те вершины на ребре которых написано 0, и в конец очереди если на ребре стоит 1.
Таким образом BFS в первую очередь будет идти по ребру веса 0, а когда нет возможности то уже по весу 1.


Вопрос на подумать, а можно ли масштабировать такой алгоритм и перестать использовать Дейкстру?

@algoses

Стажировка в Т-банк заканчивается уже СЕГОДНЯ (30 января), разбор заданий мы уже выложили на соответствующих курсах!

Задания намного сложнее, чем в прошлые года, много мест, где можно ошибиться, а о1 выдает какую-то фигню.

Специально, чтобы поддержать наших товарищей объявляем акцию, любой курс можно приобрести всего лишь за 7000 рублей по промокоду "Т-банк"! Акция действует до 30 января по мск включительно:

➡️ аналитика
➡️ машинное обучение старт
➡️ машинное обучение хард
➡️ бэкенд разработка
➡️ фронтенд разработка
➡️ инженер данных
➡️ алгоритмы

Программа и Подробности.

Для записи и всех вопросов: @menshe_treh

Стажировка в Т-банк заканчивается уже завтра (30 января), разбор заданий мы уже выложили на соответствующих курсах!

Задания намного сложнее, чем в прошлые года, много мест, где можно ошибиться, а о1 выдает какую-то фигню.

Специально, чтобы поддержать наших товарищей объявляем акцию, любой курс можно приобрести всего лишь за 7000 рублей по промокоду "Т-банк"! Акция действует до 30 января по мск включительно:

➡️ аналитика
➡️ машинное обучение старт
➡️ машинное обучение хард
➡️ бэкенд разработка
➡️ фронтенд разработка
➡️ инженер данных
➡️ алгоритмы

Программа и Подробности.

Для записи и всех вопросов: @menshe_treh

Стажировка в Т Банк
(ML-инженер, зима-весна 2025)
Дедлайн: 30 января
тапай и проходи отбор
на прохождения теста даётся 20 минут🖤
Условия и ответы ниже👇

1. Какой вид имеет функция регрессии, формируемая классическим регрессионным деревом?

Линейной
Кусочно-постоянной
Кусочно-линейной
Полиномиальной

2. Выберите верные утверждения о числе решающих и терминальных вершин дерева решений

Число решающих вершин всегда меньше числа терминальных вершин
Число решающих вершин всегда больше числа терминальных вершин
Число решающих вершин равно числу терминальных вершин
Число терминальных вершин не больше числа решающих вершин

3. Зачем нужно проводить обрезку дерева?

Для повышения точности дерева на обучающей выборке
Для повышения обобщающих способностей дерева
Для увеличения однородности терминальных вершин
Для увеличения степени гладкости модельной функции регрессии или границ классов

4. Если для некоторого обучающего примера отношение вероятностей бинарного классификатора оказалось близким к 0, что это говорит о вероятности принадлежности этого примера к положительному классу?

Вероятность близка к 0
Вероятность близка к 1
Вероятность близка к 0.5
Ничего нельзя сказать о принадлежности

5. Мы обучаем дерево решений
При увеличении глубины дерева у модели

bias растёт, variance снижается
bias снижается, variance растёт
bias не изменяется, variance снижается
bias не изменяется, variance растёт
bias снижается, variance не изменяется
bias растёт, variance не изменяется

6. Что будет со значением roc-auc, если все предсказанные значения разделить на 2?

Увеличится на 2
Увеличится на 4
Уменьшится на 4
Не изменится

7. Что работает о быстрее на большом датасете k-Fold cv или LOO CV?

k-fold CV
LOO CV
Одинаково быстро
Одинаково медленно

8. В алгоритме бэггинга над решающими деревьями нужно брать

Большой глубины
Малой глубины

9. Для регрессии с MAE какая модель даст наименьшее значение лосса на обучающем датасете?

Ответ модели, которой является минимумом по таргету в обучающем датасете
Ответ по таргету, который является среднее по таргету в обучающем датасете
Ответ модели, который является медианой по таргету в обучающем датасете
Ответ модели, который является модой по таргету в обучающем датасете

10. Какую задачу решает логистическая регрессия?

Классификация
Регрессия
Кластеризация
Поиск аномалий

11. Пусть x- точка, лежащая на границе между классами, формируемыми логистической регрессией
Чему равно отношение шансов для этой точки?
0
1
0.5
Бесконечность

12. Значение логит-функции для некоторого примера оказалось равным 0
Что можно сказать о вероятности принадлежности этого примера к позитивному классу
logit(p)=sigma^(-1)(p)=ln(p/(1-p))

Равна 0
Равна 1
Равна 0.5
Ничего нельзя сказать

13. Чему равно отношение шансов для бинарного классификатора?

Отношению апостериорных вероятностей классов
Отношению априорных вероятностей классов
Отношению функций правдоподобия классов
Отношению линейных комбинаций признаков

14. Если мы хотим отобрать признаки нам стоит использовать L_1 или L_2 регуляризацию?

L_1
L_2
Любой из вариантов

15. Какова вероятность ошибки модели, являющейся голосованием трёх алгоритмов, ошибки которых 0.1 0.2 0.3 соответственно?

0.2
0.099
0.006
0.098

(считаем вероятность ошибки всех троих, затем только двоих из трёх: 1-го и 2-го, 2-го и 3-го, 1-го и 3-го ->вероятности суммируем)

P.s. помимо ML-part, обязательна к прохождению секция алгоритмов, не забудьте
Подготовка к ML


@zadachi_ds

Задача из собеседования в VMware

Даны два отсортированных массива nums1 и nums2 длиной n и m соответственно, необходимо найти их медиану.
Если n + m нечетное, то медианой будет элемент по середине, иначе это среднее двух элементов.

Пример:
nums1 = [1,3], nums2 = [2]
Ответ: 2.00000

nums1 = [1,2], nums2 = [3,4]
Ответ: 2.50000

Существуют решения за O((n + m)*log(n + m)), O(n + m) и O(log(n + m))
По-хорошему, нужно найти O(log(n + m))

Решение:
O((n + m) * log(n + m)) - очевидно
O(n + m) - сливаем два массива за линию (они же отсортированные) и находим медиану

Найдем за O(log(n + m))

Идея следующая: чтобы найти медиану двух массивов, нужно найти такие два элемента в двух массивах, чтобы все элементы слева от этих двух элементов были меньше каждого элемента справа. Это делается бинарным поиском.
Предположим, что первый массив меньше. Если первый массив больше, то поменяйте массивы местами, чтобы убедиться, что первый массив меньше.
В этом алгоритме мы в основном используем два набора, выполняя двоичный поиск в меньшем массиве. Пусть mid1 - это разбиение меньшего массива. Первый набор содержит элементы от 0 до (mid1 – 1) из меньшего массива и элементы mid2 = ((n + m + 1) / 2 – mid1) из большего массива, чтобы убедиться, что в первом наборе ровно (n+m+1)/2 элемента. Второй набор содержит оставшиеся половинки элементов.
Наша цель - найти точку в обоих массивах таким образом, чтобы все элементы в первом наборе были меньше, чем все элементы в элементах другого набора (набора, который содержит элементы с правой стороны).

double medianOf2(vector &a, vector &b) {
int n = a.size(), m = b.size();
if (n > m)
return medianOf2(b, a);

int lo = 0, hi = n;
while (lo <= hi) {
int mid1 = (lo + hi) / 2;
int mid2 = (n + m + 1) / 2 - mid1;

int l1 = (mid1 == 0 ? INT_MIN : a[mid1 - 1]);
int r1 = (mid1 == n ? INT_MAX : a[mid1]);

int l2 = (mid2 == 0 ? INT_MIN : b[mid2 - 1]);
int r2 = (mid2 == m ? INT_MAX : b[mid2]);

if (l1 <= r2 && l2 <= r1) {
if ((n + m) % 2 == 0)
return (max(l1, l2) + min(r1, r2)) / 2.0;
else
return max(l1, l2);
}
if (l1 > r2)
hi = mid1 - 1;
else
lo = mid1 + 1;
}
return 0;
}

@algoses

Стажировка в Авито (Аналитика)

Прикрепляю тестовое задание, давайте 500 шэров (поделиться с другом) и делаем разбор.
Еще больше тестовых заданий и инсайдов на нашем курсе по аналитике.

@zadachi_ds