Алгоритмы - Собеседования, Олимпиады, ШАД

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

Дан массив целых чисел 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

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

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

Даны два массива 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

Задача из собеседования в 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<int> &a, vector<int> &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

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

Стажировка в Т-банке - самая крупная стажировка после Яндекса по количеству мест. В целом решает не сколько баллы за экзамены, сколько "ваш социальный рейтинг", анкета — подробней смотрим здесь. После контестов зовут на собес: он дикая халява, если хоть немного пробовали вкатиться в специальность.

@postypashki_old

Задача с фронтенд Яндекс.

Вы находитесь на левой верхней клетке шахматной доски и хотите добраться до правой нижней. У вас есть возможность двигаться вправо, вниз и по диагонали вниз. При этом запрещено три раза подряд перемещаться по клеткам одного цвета.

Сколько существует путей, чтобы попасть из левой верхней клетки в правую нижнюю?

Решение:
Заметим, что при движении по диагонали вниз мы всегда попадаем на клетки одинакового цвета. Следовательно, мы не можем двигаться по диагонали более одного раза подряд.

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

Пусть dp[i][j][0] обозначает количество способов добраться до позиции (i, j), при этом последнее движение было вправо или вниз. А dp[i][j][1] — количество способов, когда последнее движение было по диагонали.

В таком случае в позицию (i, j, 0) мы можем попасть из следующих позиций:

(i-1, j, 0); (i-1, j, 1);
(i, j-1, 0); (i, j-1, 1).

А на позицию (i, j, 1) мы можем попасть только из (i-1, j-1, 0).

Теперь, когда мы понимаем все переходы и состояния динамического программирования, ответом будет сумма dp[n-1][n-1][0] и dp[n-1][n-1][1].
Код в комментариях:


Эта задача была на контесте яндекса. Больше разбора для тех кто взял курсы.

@algoses

Товарищи, делюсь с вами каналом по ML и DS Борис Опять, от ML инженера в ebay. Борис на свое канале делиться просто бомбическим контентом, например:

- Методичка по поиску работы в ML/DS и IT в целом
- Минимальные знания Software Engineering для Data Scientist
- Вспоминания о своих джуновских годах
- Реализация алгоритма BM25, алгоритм поиска из 80х который работает лучше чем нейросети для RAG

Строим рекомендательную систему фильмов на Kaggle

Вы когда-нибудь хотели сделать свою собственную систему рекомендаций фильмов? 🎬

Приходите на бесплатный вебинар, где Савелий Батурин, Senior ML-Engineer и преподаватель курса по ML школы Simulative в прямом эфире покажет как построить рекомендательную систему фильмов на Kaggle.

Что будем делать на вебинаре:
• Разберем имеющиеся данные фильмов с их оценками
• Проведем предобработку данных
• Построим рекомендательную систему на основе машинного обучения
•Проведем расчет и анализ метрик на основе результатов работы модели

🕗Встречаемся 21 января 19:00 по мск

Вебинар будет интересен как новичкам, так и уже опытным специалистам

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

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

Дан набор интервалов, представляющий из себя массив пар чисел: начало и конец интервала

intervals[i] = [start_i, end_i]

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

Пример

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Решение:
Метод сканирующей прямой
Во вспомогательном массиве сохраним индексы и тип события (интервал открылся 1, закрылся -1) и отсортируем
Далее пройдемся по всем событиям в порядке индексов и будем поддерживать счетчик количества интервалов, которые покрывают текущую точку. Если в какой-то момент счетчик становится 0, то добавляем в ответ новый интервал и идем дальше. Если ненулевой, то ничего добавлять не нужно

static bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first != b.first)
return a.first < b.first;
return a.second > b.second;
}

vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = (int)intervals.size();
vector<pair<int, int>> ev;
for (int i = 0; i < n; ++i) {
ev.emplace_back(intervals[i][0], 1);
ev.emplace_back(intervals[i][1], -1);
}
sort(ev.begin(), ev.end(), cmp);
vector<vector<int>> res;
int cnt = 0, first = -1;
for (auto event : ev) {
int ind = event.first, type = event.second;
cnt += type;
if (cnt == 0) {
res.push_back({first, ind});
first = -1;
} else if (first == -1)
first = ind;
}
return res;
}

@algoses

Кстати, пост выше был от наших друзей из Start Career in DS
Они пишут про развитие в анализе данных, делятся подборками материалов, задач и делают квизы по DS/ML.

Что интересного можно ещё почитать у них:
- Базовая теория по DL, которую должен знать каждый
- ML-System Design: справочник материалов для подготовки
- LangСhain - библиотека, расширяющая возможности LLM

Подписывайтесь на них, канал топ!

Собрали для вас курсы степика, которые могу пригодиться начинающим и продолжающим) Есть как бесплатные так и платные, но доступные по цене

🐍 Python
Поколение Python - первый курс из линейки по изучению питона с нуля с множеством задач для тренировки написания кода
Добрый, добрый Python - курс для начинающих и для тех, кто уже знаком с Python, но хотел бы повысить/проверить свой уровень
Программирование на Python - вводный курс по питону от Института биоинформатики
Python: основы и применение - курс по питону для продолжающих, тоже от Института биоинформатики


📊 SQL
Интерактивный тренажер по SQL - практика написания SQL-запросов с минимумом теории, сложность возрастает по мере прохождения курса
SQL База - основы SQL от Left Join
Основы SQL - обучение SQL с нуля на примере MySQL
Продвинутый SQL - сложные запросы, транзакции, тригеры и оконных функций в MySQL


⚛️ ML/DL
Deep Learning (семестр 1, осень 2024) и Deep Learning (семестр 2, осень 2024): бесплатный двухсеместровый курс по глубокому обучению от МФТИ
Машинное Обучение в Python - требуется только базовое знание Python, математика добавляется постепенно, поэтому курс подойдет для начинающих
Добрый, добрый ИИ от Сергея Балакирева - первые шаги в ML, нужны знания математики и Python
Нейронные сети и обработка текста - для тех, кто уже имеет базу в ML и хочет научиться применять нейронные сети для решения задач NLP


➕ Math
Математика для всех от Савватеева - курс поможет разобраться в математической логике и механизмах работы математики
Ликбез по дискретной математике - обзорный курс по дискретной математике
Линейная алгебра - краткое изложение основ линейной алгебры
Теория вероятностей - базовыме понятия теории вероятностей, много примеров и задач
Основы статистики от Карпова - база в статистике, уже неоднократно писали про этот курс в канале
Добрая теория вероятностей от Балакирева - школьная база по теории вероятности

Ждём ваших ❤️ и 🔥! Делитесь в комментариях какие курсы проходили вы и можете порекомендовать 🧑‍🏫

Задача с МЛ секции Яндекс (2025)

Да, даже на мл секции спросят хотя бы одну задачу на алгоритмы. Еще больше инсайдов будет на курсе по алгоритмам. Всех жду, товарищи!

Задача:
Дан отсортированный по неубыванию список целых чисел a, индекс элемента index и целое число k.
Необходимо вернуть в любом порядке k чисел из списка, которые являются ближайшими по значению к элементу a[index].

Ограничения:
- Размер списка 1 <= N <= 10^6 ;
- Элементы списка: -10^9 <= a[i] <= 10^9 ;
- Число 0 < k <= N ;
- Индекс элемента 0 <= index < N .
- Среди двух одинаково отдалённых элементов выбирается больший

find_k_closest(a=[2, 3, 5, 7, 11], index=3, k=2) -> [5, 7]
find_k_closest(a=[11, 12, 15, 15, 24], index=1, k=3) -> [11, 12, 15]
find_k_closest(a=[2, 3, 5, 7, 11], index=2, k=2) -> [5, 7]

Решение:
Так как массив отсортирован, в ответ попадут несколько элементов слева от index и сколько-то элементов правее от index.

В ответ обязательно попадет a[index], так как расстояние ноль. Дальше смотрим на соседей index (справа и слева), кто ближе, того и добавляем в ответ, и сдвигаем указатель.

Будьте осторожны с выходом за пределы массива.

def find_k_closest(a: list[int], index: int, k: int) -> list:
left_ptr = index - 1
right_ptr = index + 1
k_closest = [a[index]]
while len(k_closest) != k:
if left_ptr < 0 or ((right_ptr < len(a)) and (abs(a[index] - a[right_ptr]) <= abs(a[index] - a[left_ptr]))):
k_closest.append(a[right_ptr])
right_ptr += 1
elif left_ptr >= 0:
k_closest.append(a[left_ptr])
left_ptr -= 1

return k_closest

Скорость посчитайте сами, жду ответов в комментариях😉

@algoses

Поступашки открывают набор на лучшие курсы по самой доступной цене 🎓

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

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

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

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

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

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

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

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

Задача с Google.
Довольно простая задача от гугла. На самом деле задачи там сложнее чем в Яндексе, наверное эта задача попалась в первом отборе.

Задача:
Даются две строки s, t. Вернуть True, если можно сделать строку t равной s.
Вам разрешается не более одного раза выбрать подотрезок [l, r] сделать циклический сдвиг подстроки t[l. r].
Важно: Решить без дополнительной памяти.

Пример:
s = 'addeffge'
t = 'adeffdge'
Выбираем подотрезок [2, 5] и делаем циклический сдвиг вправо.

Решение:
Пройдемся слева направо по строке t. Найдем самую левую позицию l, что t[l] != s[l], а также найдем максимальную позицию r, что t[r] != s[r].
Если таких позиций нет то ответ True.
Если l=r то ответ False.

Иначе у нас два варианта, циклически сдвинуть подотрезок влево или вправо. Мы сделаем и тот и другой вариант и проверим совпали ты строки. Главное помнить не использовать дополнительную память.


Время работы алгоритма O(len(t))

@algoses

📚 Поднимаем ставки, мы запустили еще 1 крупнейший розыгрыш для вас

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

Условия просты:

• подписаться на t.me/sqlhub
• подписаться на http://t.me/postypashki_old

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

— MySQL по максимуму. 4-е издание
— Книга по ООП в Python от David Ham
— Python для сложных задач: наука о данных. 2-е межд. изд.
— Скрапинг веб-сайтов с помощью Python | Митчелл Райан
— Прикладные структуры данных и алгоритмы. Прокачиваем навыки | Джей Венгроу
— Обработка данных на Python. Data Wrangling и Data Quality

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

• подписаться на t.me/sqlhub
• подписаться на http://t.me/postypashki_old

#Конкурс #новыгод

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

У Пети был массив целых чисел, состоящий из уникальных элементов и отсортированный по возрастанию. Его друг Вася, когда увидел массив, начал завидовать Пете и решил циклически сдвинуть исходный массив на k позиций. Другими словами, изначальный массив nums теперь имеет вид

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

Дан массив nums (уже сдвинутый) и число target. Нужно за O(logN) найти индекс числа target в nums, или вернуть -1, если его нет.

Решение
Применим два бинарных поиска

Сначала найдем величину сдвига k: это достаточно просто сделать, сравниваем средний элемент с самым правым. Если средний больше, то точка сдвига находится правее, иначе левее и таким образом найдем k
Далее применим также бинарный поиск на всем массиве для нахождения индекса target.
Теперь, когда мы знаем наш сдвиг k, нам просто нужно изменить наше среднее значение следующим образом: currm = (m + k) % N. И задача решена

Два бинарных поиска: O(2logN) = O(logN)

@algoses

📚 Новогодние праздники продолжаются и пришло время провести крутой розыгрыш.

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

Условия просты:

• подписаться на Pythonl
• подписаться на Поступашки

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

— System Design. Машинное обучение. Подготовка к сложному интервью | Сюй Алекс
— Алгебра, топология, дифференциальное исчисление и теория оптимизации для компьютерных наук и машинного обучения
— Глубокое обучение Курвилль Аарон, Гудфеллоу Ян
— Как быть успешным в Data Science.
— Все, что нужно, чтобы понимать математику в одном толстом конспекте

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

• подписаться на Pythonl
• подписаться на Поступашки

#Конкурс

Задача с собеседования в Тинькофф.

Умеете ли решать следующую задачу?
Дается массив целых чисел 'a', найти два индекса 0 <=l<r<n, что a[l] + a[r] == target.
Думаю многие знают эту задачу, называется Two Sum. Эта задача очень часто встречалась в Яндексе.

Так вот люди в Тинькофф поменяли эту задачу:
Дается отсортированный массив целых чисел 'a', найти два индекса 0 <=l<r<n, что a[l] + a[r] == target.
Решить нужно за O(n) и без дополнительной памяти.

Решение:
-Сначала вспомним как решать с доп памятью:
Заведем хеш-таблицу has. Пройдемся циклом по массиву 'a'. Пусть мы на позиции i, нам хотелось бы найти такой j, что j < i и a[i] + a[j] == target. Мы могли бы в хеш-таблице узнать встречали ли число a[j], равным target-a[i].

Заметим, что мы вообще не использовали факт отсортированности массива.
Пусть j=0, найдем максимальный i, что a[j] + a[i] <= target. В таком случае для j=0, лучшая пара это i. Если a[i] + a[j] = target, то супер мы нашли ответ.

Пусть j=1, найдем максимальный i, что a[j] + a[i] <= target. Как думаешь i, для j=1 может быть больше чем i для j=0?
Конечно нет, а это означает мы можем применить метод двух указателей.

j будет всегда идти слева направо, а i справа налево. Как только находим сумму равная target выходим из цикла. Этот метод сработал число из за отсортированности массива.

Для практики вы можете взять задачу Two Sum из литкода, отсортировать массив который вам дают и применить метод двух указателей.

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

Почему кандидаты не смогли пройти алгособес в 2024 году

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

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

Почему важно погуглить/спросить какие задачи попадались на алгособесе?
Дело в том, что в компаниях задачи повторяются и собесы проводят обычные сотрудники, которые не любят сильно напрягаться. Возьмем для примера тот же ШАД, люди которые несколько раз пытались поступить подтвердят, что задачи на алгособесе повторяются. Смешно было когда одна и таже задач попалась два года подряд одному и тому же кадидату.

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

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

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

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

Мок интервью
Думаю это прям жизненно и многие подтвердят, что определенную задачу на литкоде вы спокойно решали дома, а на собесе эту же задачу не смогли решить?
У меня лично друг с рейтингом ~1900 на кф завалил алгособес.

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

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

Стратегия
Пассивное обучение распространенная ошибка кандидатов. Они обычно говорят ДА Я ВОТ ДАЖЕ В АВТОБУСЕ РЕШАЮ ЗАДАЧИ. Ребята, если вы хотите эффективно учиться, вы должны выделять себе определенное время, в котором вы целенаправленно будете решать задачи. Ваш мозг должен напрягаться в это время и тем самым вы учитесь решать задачи.
Пассивное обучение плохо себя показывает на собесе, когда нужно быстро рассказать решение и написать код.

Я понимаю, что это все очевидные вещи, но эту базу многие забывают. Надеюсь в 2025 году все, кто поставит огонек 🔥 посту, пройдут алгособес!

@algoses

Разбираем тестовое задание на позицию Junior Аналитика в Яндекс.

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

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

Что будет на вебинаре:
🟠С помощью Python решим рутинные задачи - разархивировать файлы, прочитать большой json и т.д.
🟠С помощью Pandas проанализируем поисковые запросы Яндекс.Картинок
🟠С помощью Plotly построим интерактивные графики и сделаем выводы
🟠Найдем статистически значимую разницу в поведении пользователей на разных устройствах

Вебинар проведет Андрон Алексанян, CEO Simulative

🎁Обязательно приходите смотреть вебинар в прямом эфире - в лайве будут дарить подарки, которые сильно бустанут старт карьеры в аналитике!

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

▎Как успешно изучать математический анализ?

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


▎Теоретические материалы (все книги тут)

1) Курс С. В. Шапошникова  (тут)
   Чтение на мехмате, в котором все темы и доказательства выбраны с умом. Отличный выбор для начинающих.

2) Математический анализ В. А. Зорича 
   Стандартный учебник для мехматян. Несмотря на то, что он немного устарел, содержит множество интересных примеров и задач.

3) Контрпримеры в анализе Б. Гелбаума, Дж. Олмстеда 
   Сборник стандартных приемов и ответы на ключевые вопросы в анализе, которые помогут понять, почему некоторые условия важны.

4) Курс математического анализа Л. Д. Кудрявцева 
   Простой и понятный материал, который отлично подходит для студентов физтеха.

5) Основы математического анализа и Курс дифференциального и интегрального исчисления Г. М. Фихтенгольца 
   Доступный язык изложения, который будет понятен даже школьникам.

▎Задачи для практики

1) Сборник задач и упражнения по математическому анализу Б. П. Демидовича 
   Классический задачник, хотя и без примеров решения. Довольно устаревшая вещица, но базирует

2) Математический анализ в задачах и упражнениях И. А. Виноградова и другие 
   Труд с множеством примеров решения задач и краткой теоретической сводкой.

3) Сборник задач по математическому анализу Л. Д. Кудрявцева и другие 
   Дополнение для практики, хотя и менее объемный, чем предыдущий сборник.

4) Problems.ru 
   Сайт с простыми задачами, полезный для начинающих.

5) Интегралы и Ряды А. П. Солодова 
   Методичка с задачами и решениями, частично основанная на Демидовиче.


▎Где найти разборы задач

1) Семинары с ФПМИ А. А. Скубачевского
   Качественный материал с разбором типичных задач, однако не все темы охвачены.

2) Семинары преподавателей МГУ 
   Полезные семинары с детальным объяснением важных тем.

3) Семинары преподавателей физтеха 
   Отличные разборы, которые углубят ваши знания.


Если у вас есть свои любимые материалы, не стесняйтесь делиться ими в комментариях!

🔥 Это база с 1900 вопросами с собеседований по анализу данных, машинному обучению, sql. Фишка в том, что вопросы разбирают эксперты, которые сами проводят собесы и дают примеры правильных ответов. Вы легко получите оффер, изучив популярные вопросы.

Новая задача Яндекса.

Для двух массивов целых чисел длины N, для всех K от 1 до N, посчитать количество общих чисел на префиксах длины K.
Числа в пределах массива могут повторяться, пересечение считается без учета кратности.
Пример
a = [1, 1, 2, 3]
b = [2, 1, 3, 1]

k = 1 ответ 0
k = 2 ответ 1
k = 3 ответ 2
k = 4 ответ 3

Решение:
У тебя есть решение за O(n), но твое решение требует использование две хеш-таблицы (хеш-сета) то к сожалению твое решение не примут.

Нужно завести одну хеш-таблицу, назовем has.
Ключом хеш-таблицы будет число из массивов, а значение будет принимать три значения.
0-если число встречается ТОЛЬКО в первом массиве
1-если число встречается ТОЛЬКО во втором массиве
2-если число встречается одновременно в первом и во втором массиве.

Пройдемся циклом с k = 1 до k=n.
-Если a[k] есть в has и has[a[k]] = 1 то увеличим ответ и сделаем has[a[k]]=2.
-Если has[a[k]] не равен 2 то делаем has[a[k]] = 0
-Если b[k] есть в has и has[a[k]] = 0 то увеличим ответ и сделаем has[a[k]]=2
-Если has[b[k]] не равен 2 то делаем has[b[k]] = 1

Если не понятны выше четыре условия то просто подумайте, а как бы обновляли хеш-таблицу имея новые числа a[k], b[k].

(Эту задачу можно решить разными способами, самое главное использовать один хеш)
Решение O(n).

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

🧠 Machine Learning — авторский канал, где собрана вся база по ИИ и машинному обучению.

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

В 2025 году ИИ выйдет на совершенно новый уровень тот, кто не успеет за прогрессом - отстанет, а кто разберется - сорвет куш.

Стоит подписаться: t.me/ai_machinelearning_big_data

Вы замечали, что на собеседованиях часто встречаются задачи, связанные с подстроками и подпоследовательностями? Даже если проанализировать все задачи в этом канале, то можно увидеть, что более половины из них посвящены подстрокам.

Было бы логично научиться решать такие задачи, чтобы лучше справляться с собеседованиями. Однако возникает вопрос: где найти подходящий материал для подготовки?

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

С удовольствием поделюсь с вами 30 заданиями на подотрезки/подпоследовательности, которые помогут вам подготовиться к собесу.
https://docs.google.com/spreadsheets/d/1FZONKfiZZcNMxz22XX_hHxSd6pnrYnFw_js6_G9ueBA/edit?gid=0#gid=0


Если вы хотите получить больше задач по разным темам и структурированную подготовку к собеседованию, то вам стоит обратиться к ментору https://t.me/algoses/17. Он поможет вам легко подготовиться к предстоящему испытанию.

Задача Яндекса.
Достаточно старая задача, но сейчас стала набирать обороты.

Задача: Дается массив целых и уникальных чисел, ваша задача сжать этот массив, например был у вас массив
-3, -10, 1, -2, 2, 3, 5
то после сжатия ваш массив превращается в
[-10], [-3, -2], [1, 3], [5].
(Я думаю на примере можно понять что просят сделать)
Вывод может быть необязательно в отсортированном виде, то есть вывод
[-3, -2], [1, 3], [-10], [5] тоже считается корректным.

Решение: (если подумал отсортировать массив то лучше посмотреть разбор)


Конечно легче всего массив отсортировать и дальше двумя указателями решить. Такой алгоритм будет работать за n*logn. Такое решение не примут на собесе.

И вот как решать за O(n).
Пройдемся по массиву и запишем их всех в словарь. То есть ключом будет элемент в массиве, а значением 1.

Теперь будем делать следующий алгоритм пока словарь не станет пустым.

Пусть зафиксировали ключ key. Мы как и в двух указателей будем искать такие максимальные r, l, что все числа [key-l, key+r] есть в словаре. Опять таки l, r ищутся очень просто. Вы делаете l=r=0, дальше смотрите есть ли в словаре ключ key+r, если есть то увеличиваете r, иначе останавливаетесь, аналогично для l.
Числа которые нашли стоит удалить из словаря и повторить алгоритм заново.

Время работы алгоритмы O(n).

Если наберет много реакций сегодня выложу код.

Вот и разбор собеседования в ШАД 2024 года! Обязательно делимся со всеми друзьями, которые собираются поступать в ШАД или топовую магистратуру.

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

Коммунизм уже наступил, товарищи!

Всем нашим ученикам мы стремимся дать качественное и доступное образование. На семинарах с каждым учеником общаемся по очереди, только полноценное общение. Помогаем им составить резюме, даем личные рекомендации, предлагаем интересные вакансии, проводим пробные собеседования. А главное все ребята, которые реально готовы вкладываться, первыми выполнять дз и слушать наши рекомендации как выпускница нашего прошлого курса по подготовке к ШАД, могут УЧИТЬСЯ У НАС АБСОЛЮТНО БЕСПЛАТНО!

[ Записаться на курсы ]

Честный обзор стажировки в Яндексе (Бэкенд C++ 2024)

У выпускников наших курсов стажировка уже подошла к концу, рассказываем все как есть.

Моя стажировка проходила в команде, которая занималась разработкой приложений для такси.

До выхода на работу с вами связывается начальник и спрашивает какой ноутбук хотите Mac/Windows/Linux, а также сколько дюймов. Я сказал мак и желательно самый большой, мне его и дали. Характеристики ноута были очень даже хорошими.

В первый день работы дают подарки: футболка, портфель, бутылка, и возможно более мелкие подарочки.
Честно скажу бутылка очень плохая, состав ужасный, и в целом дешевый.
А вот портфель реально хороший, у меня на них фетиш, и этот реально топовый жеребец.
Футболка как футболка, красивая с прикольными надписями.

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

Яндекс в этом плане организован, и мне эта сторона понравилась.

Процесс работы:
-Есть гибрид - и это очень радует.
-Большинство команд начинают работу после 11:00, так что можете обсудить с начальником во сколько вам удобно, главное быть в митингах.
-Задачи для вас будут даваться рандомно. У каждой команды есть пак задач, и задач на самом деле много, вам просто будут давать из этого пака какую-то задачу.
- Большинство технологий написано Яндексом и нет в открытом доступе, так что вам придется разбираться в документации которая написано несколькими людьми.
- Местами прям виден неоптимизированный код с точки зрения алгоритмов. Например данные записаны в вектор и при поиске приходится проходиться по вектору, хотя можно было бы использовать map. Если у вас возникнет мотивация переписать код, то вам придется менять код во многих файлах, да еще чтобы ничего не упало..... Короче никто за это не берется. Скорее всего эти участки кода не критичны.
-Часто придется писать тесты, чтобы убедиться правильно ли работает код. Я лично разобрался за месяц, то как именно работают тесты).
-Переработки есть. У меня лично было пару раз.
-Знания языка С++ прям сильно вам помогать не будут (именно в такси, думаю и во многих других направлениях). Куда сильнее помогут навыки работы с API, Базами данных, логированием, STQ, и тд.

Плюсы в Яндексе:
-Хороший офис, компенсации еды (примерно 10-12 долларов в день)
-Гибрид
-Сфокусированы на своей задаче, в маленьких компаниях обычно приходиться заниматься всем, а тут вы в своей области работаете. (это может быть и минусом, но для меня это плюс)
-Свободный график
-Если смотреть на общую картину то коллектив весьма хороший. Много умных ребят, много девушек, много стажеров, много позитивных людей.
-В Яндексе очень много курсов, которые вы можете приобрести бесплатно или со скидкой. Например английский можно получить по 50% скидки. Лекции ШАДа по любому направлению можно смотреть (но доступа к домашкам нет, надо этот вопрос отдельно решать)
-Каждый год можно собеситься и поднимать зп.
-Когда непонятные баги с их гитом, то можно обратиться в отдельный сервис за помощью, они будут помогать. Насколько знаю это большая проблема в других компаниях. Люди месяцами пытаются решить конфликты в гите.
-Стажировка сильно расширяет кругозор в плане технологий и работы бэкенда. Даже если вы уйдете из Яндекса, ваш опыт поможет найти работу.

Минусы в Яндексе:
-Переработки есть
-Прям сильного погружения в С++ в команде такси не ждите, я думал буду писать хардовый код на плюсах, а на самом деле изменял уже написаный код + дописывал.
-Малейшие изменения кода приведет к конфликтами с большим количеством файлов, придется в каждом файле исправлять код, да и в целом процесс выкатки в тестинг, а потом в прод очень долгий.

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

Хочешь поступить в ШАД или магистратуру, затащить олимпиаду или сессию? Или просто мечтаешь стать крутым специалистом, тащить собесы, но не хватает фундамента?

Тогда специально для тебя Поступашки объявляют акцию до 7 декабря! Любой курс можно приобрести со скидкой в 25% всего за 6375 р (меньше 60$)!

Инфляция растет бешенными темпами, лучшая инвестиция — ваше образование, товарищи, ведь оно не потеряет ценность никогда! Успейте выгодно вложить свои деньги, пока они не сгорели. Сейчас для покупки доступно четыре курса:

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

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

На семинарах с каждым учеником общаются по очереди, полноценное общение как здесь (никаких дурацких чатов, преподаватель лично выслушивает твои решения). Ежедневная связь, пробные собесы, экзамены, персональные рекомендации, инсайды и домашнее задание с проверкой, код ревью и с разбором от преподавателя, который отвечает даже после завершения курса! Все будет еще круче, чем на всех прошлый курсах (отзывы тут). Все для того, чтобы поступить в ШАД/ топовую магу уже летом или мы вернем потраченные деньги!

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

Вот и интервью с настоящим гением! У нас в гостях Антон Садовничий, всероссник и межнарник. Антон знаком с В. В. Путиным, заканчивает ФМПИ МФТИ. Поговорим про секреты такой продуктивности, поговорим про его путь в науке и в карьере, и узнаем что именно в конце концов выбрал Антон! Получилось очень интересно и познавательно, товарищи.

Смотрим! Смотрим!
https://www.youtube.com/watch?v=totKwx9i_tU

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

Имеется n пользователей, каждому из них соответствует список email-ов (всего m email-ов). Например:
user1 -> [email protected], [email protected], [email protected]
user2 -> [email protected], [email protected]
user3 -> [email protected], [email protected]
user4 -> [email protected], [email protected]
user5 -> [email protected]

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

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

В указанном примере ответ на задачу будет следующий:
user1 -> [email protected], [email protected], [email protected], [email protected], [email protected]
user3 -> [email protected], [email protected]

Решение:

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

Подумаем про графы. Было бы хорошо выделить юзеров отдельно и множество почт отдельно.

Давайте визуально нарисуем слева вершины, которые соответствуют юзерам. В нашем примере их 5.

А справа выпишем множество различных почт.

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

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

Например, запускаем ДФС с вершины user1 и посещаем вершины user2, user4, [email protected], [email protected], [email protected], [email protected]. В качестве ответа вы берете любого юзера и все почты, которые успели посетить. Дальше запускаете ДФС от непосещенной вершины (это вершина user3) и запускаете ДФС.

Единственное вам нужно пронумеровать вершины. Вы можете завести словарь куда будете писать номер вершины которому соответствует строка. Например
'user1' - 0,
'user2' - 1,
'[email protected] - 2'
.......
То есть каждой строке дать число. Зачем мы это делаем???
Попробуйте построить граф на строках и написать дфс, думаю веселье такое себе. Так что пишем словарь который будет строки переводить в числа. Также полезно создать еще один словарь, который будет по индексу вершины узнавать что за строка. Например из примера выше для индекса 2 соответствует строка [email protected].

Асимптотика линейная.

Буду благодарен, если напишите код.

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

Хочешь поступить в ШАД или магистратуру, затащить олимпиаду? Или просто мечтаешь стать крутым специалистом, тащить собесы, но не хватает фундамента? Тогда тебе к нам!

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

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

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

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

Цена 7500р за курс, до 14 ноября, далее повышение цены до 8500р. Если покупали наши курсы ранее, то цена 7000р. Если же покупали аналогичный курс, но хотите больше новых задач и материалов, то новый курс (материал полностью обновлен и расширен) обойдется вам всего за 5000 р!

Даты: начала курса 17.11

Как купить: приобрести курс и задать вопросы можно по данному адресу: @menshe_treh

Еще курсы серии:
➡️ линейная алгебра старт 10.11
➡️ алгоритмы старт 10.11
➡️ теория вероятностей старт 02.11

Отбор на стажировку в Яндекс в самом разгаре! Специально для вас пригласили Эву Эльфи пройти знаменитое алгоритмическое собеседование в Яндекс с подробным фидбэком, разбором ошибок и советами от Тимура, который сам провел десяток таких собеседований.

Смотрим! https://www.youtube.com/watch?v=O8a6orLfSj0

Стажировка в Т-банк на аналитика в самом разгаре! Для участия нужно решить контест до 13 ноября, его задания уже в нашей БОТАЛКЕ, там же можно обсудить задания вместе в админом, а решения есть на нашем ютубе (задания не поменялись)

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

@matesha_shad

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

Задача сейчас набирает обороты, и так вам дается бинарное дерево (с прописанной структурой вершин). В каждой вершине стоит одна буква из [a, z].

Две вершины считаются равными если множество букв в под деревьях совпадают. (Важно, именно как множество совпадает)

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

Решение:

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

Создадим словарь, где в качестве ключа будем передавать лист (вектор) размера 26, а значением будут две вершины(на самом деле можно и одну)

Суть словаря следующая:
Вектор будет размера 26, где на позициях будут стоять 1 если такая буква есть и 0 иначе.
Таким образом две вершины равны если их эти вектора равны.
А значением будет две вершины у которых самое максимальное количество детей. То есть значения - это pair <Node, Node> ваша задача туда поставить две вершины с максимальным колиеством детей.

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

Псевдокод в комментариях:

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

Хочешь поступить в ШАД или магистратуру, затащить олимпиаду? Или просто мечтаешь стать крутым специалистом, тащить собесы, но не хватает фундамента? Тогда тебе к нам!

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

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

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

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

Цена 7500р за курс, до 7 ноября, далее повышение цены до 8500р. Если покупали наши курсы ранее, то цена 7000р. Если же покупали аналогичный курс, но хотите больше новых задач и материалов, то новый курс (материал полностью обновлен и расширен) обойдется вам всего за 5000 р!

Даты: начала курса 10.11

Как купить: приобрести курс и задать вопросы можно по данному адресу: @menshe_treh

Еще курсы серии:
➡️ алгоритмы старт 10.11
➡️ математический анализ старт 17.11
➡️ теория вероятностей старт 03.11

Стартовала регистрация на «Технокубок»!

Победа или призовое место дает бенефиты при поступлении в вуз: зачисление без экзаменов или 100 баллов за ЕГЭ по информатике. А еще участники соревнования смогут пообщаться с представителями МФТИ, МГТУ имени Н. Э. Баумана и экспертами VK на офлайн-площадках в финале.

Для участия важно знать математику и информатику, а также уметь программировать на С, С++, Java, С#, Python, Kotlin или Go. Подготовиться можно с помощью курса «Старт в олимпиадном программировании» от VK Education. Отборочные раунды пройдут уже 17 ноября, 8 и 22 декабря.

Всем участникам удачи!

Как подготовиться к олимпиаде?

Пройдите бесплатный курс подготовки к ВСоШ по математике от Т-Образования. Усиленная подготовка к олимпиаде в формате лекций и практических заданий по каждой теме от опытных преподавателей. Доступ к курсу останется навсегда — можно вернуться к подготовке в любой момент.

Запишитесь на курс от Т-Образования за пару минут.

Курс по алгоритмам стартует уже в это вокресение (еще можно записаться)! Как материал для подготовки записаны вот такие вводные уроки, где разбираем всю необходимую теорию на конкретных примерах, задачах из того же самого ШАД. Такие вводные уроки дополняют и расширяют материал каждого занятия в 2 раза. Ведь Поступашки реально хотят научить ребят, дать им качественное образование, а не просто взять деньги и послать куда подальше!!

Набор на стажировку в VK проходит прямо сейчас, товарищи! Поэтому сегодня специально для вас пообщались с Иваном Нагайко, он пришел в компанию еще стажером, а вырос техлидом😎 Обсудили все секреты и лайфхаки Ивана, получилось очень интересно и полезно!

Смотрим! Смотрим! https://www.youtube.com/watch?v=eNwVeCNfZu0

Новый профиль «Промышленное программирование» ждёт учеников 9-11 классов. А мы знаем как минимум три причины, чтобы принять участие:

💻 Задания взяты буквально «с полей» — их подготовили эксперты Яндекса, опираясь на реальный опыт;
💻 Возможность почувствовать себя настоящим разработчиком и ещё ближе познакомиться с профессией мечты;
💻 Шанс получить бесценную практику и знакомства, прокачать скиллы в программировании.

Бонусы участникам:

📍Бонусы при поступлении в ведущие вузы на IT-программы;
📍Практическую подготовку к профессии;
📍Подарки от Яндекс для победителей и призёров олимпиады;
📍Опыт решения IT-кейсов: от проектирования веб-серверов до создания пользовательских интерфейсов.

Вот, что надо сделать, чтобы стать участником направления «Промышленное программирование»:

✔️ Учиться в 9-11-м классе;
✔️ Интересоваться информатикой и программированием;
✔️ Зарегистрироваться на «Высшую пробу» не позднее 14:00 мск 5 ноября.
 
Скорее переходите на сайт: https://clck.ru/3DzvKH и узнавайте подробности!

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

Хочешь поступить в ШАД или магистратуру, затащить олимпиаду? Или просто мечтаешь стать крутым специалистом, тащить собесы, контесты компаний как Яндекс, Тинькофф, ВК или даже MANGA, HFT, но не хватает фундамента? Тогда тебе к нам!

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

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

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

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

Цена 7500р за курс, до 31 октября, далее повышение цены до 8500р. Если покупали наши курсы ранее, то цена 7000р. Если же покупали аналогичный курс, но хотите больше новых задач и материалов, то новый курс (материал полностью обновлен и расширен) обойдется вам всего за 5000 р!

Даты: начало курса 03.11

Как купить: приобрести курс и задать вопросы можно по данному адресу: @menshe_treh

Еще курсы серии:
➡️ теория вероятностей старт 02.11 (начало занятий)
➡️ линейная алгебра старт 10.11
➡️ математический анализ старт 17.11

Intern week offer от Яндекса в самом разгаре! Для участия нужно решить контест до 4 ноября, его задания уже в нашей БОТАЛКЕ, там же можно обсудить задания вместе в админом.

Напомню, что в случае неудачного прохождения секций фриз на полгода сохраняется! Преимущество нынешнего week offer лишь в ускоренном прохождение отбора: меньше риск, что HR вдруг уйдет в отпуск и забудет вас передать коллеге, да и намного меньше шансов, что у вас у самого что-то случится(сессия, бросит девушка) и придется отложить прохождение отбора! Кстати задания контеста несложные, студенты наших курсов справляются с ними за 300 наносек😎😎

@algoses

Полный цикл отбора в HFT (компания Teza)

Товарищи, понравилась ваша реакция под прошлым постом, потому специально для вас попросил выпускника наших курсов рассказать про отбор в одну из самых популярных компаний HFT, в которую вполне реально попасть из РФ.
Далее представлен слегка отредактированный текст нашего выпускника.

Три года назад окончил мехмат МГУ. Во время учебы занимался спортивным программированием (но не так успешно). После университета пошел разработчиком. Успел поработать на Python и C++. В какой-то день я решил поменять свою жизнь (расстался с девушкой) и искал то, что будет интересно для меня, и наткнулся на HFT. Чуть-чуть поизучав, я понял, что это то, что нужно. Высокие нагрузки на работе, применение математики, С++, алгоритмов, хорошая зарплата.

Начал копать HFT компании и нашел немало, но, к сожалению, я не проходил скрининг резюме. Позже наткнулся на HR в Linkedin, которая работала в ереванском Teza. Она посмотрела мое резюме и дала пару советов, как улучшить. Так что ребятам, которые планируют в будущем подаваться в HFT компании, да и не только туда, советую поработать над своим CV.

Она предложила мне пройти собеседования на SOFTWARE DEVELOPER в QUANTITATIVE команду. В целом это не то, что я хотел, но решил попробовать раз уж квантом на тот момент пока никуда не взяли.

Пока подавался в компании, я параллельно готовился по линейной алгебре, теории вероятности и по алгоритмам.
По алгоритмам я попросил Тимура подготовить меня, брал у него менторство и три месяца плотно решали много задач.
По математике также готовился по курсам Поступашек (кстати в это воскресение уже стартует теор вер).

Всего было три этапа.

Первый этап
Скинули ссылку hackerrank, в котором были две задачи. Обе задачи были на алгоритмы, и надо было решить на время. У них был свой практоринг.
Задача 1: дается два массива чисел, проверить, правда ли одна является подпоследовательностью другой.
Задача 2: на плоскости даются n городов (просто точки). Дальше даются q запросов. Каждый запрос — это точка (x, y), ваша задача — найти ближайший город к (x, y), но чтобы у них хотя бы одна координата была равна. Кстати, подобные задачи с решениями постоянно выкладываются здесь, товарищи.

Решил эти две задачи и пригласили на следующий этап.

Второй этап
Собеседование в котором была только математика. Ниже я перечислю вопросы, которые помню.
-Чему равен ранг x*x^t где x - вектор столбец.
-Найти все собственные значения для x*x^t
-Какие могут быть характеристические корни у матрицы A, если A^4 = A^2.

-Бросают кубик, посчитать мат ожидания и дисперсию числа выпавших чисел.
-Бросают два n гранных кубика, какова вероятность что суммарно выпадет k очков.
-Были теоретические вопросы по распределениям, много спрашивали про нормальное распределение.

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

Пригласили на третий собес:

Третий этап
Уже по кодингку и хард скилам.
-Начался разговор с баз данных, какие использовал, что делал. Использовал ли Postgres.
-Airflow, Hadoop
-Был ли опыт в ML
-На мое удивление дали задачку на numpy)
-По большей части спрашивали Python и С++.
В целом по языкам программирования вопросы были не сложные, стандартные. Может из-за того, что у меня был опыт работы.
Спрашивали про выделения памяти, про шаблоны, версии С++, ООП на питон и на плюсах. Не было ничего сверхъестественного.
Подчеркиваю, я не собесился на кванта. У квантов достаточно жесткий собес по плюсам.
В целом третий этап собеса будет несложным для человека, который имел опыт работы на С++ и python.

Предложили оффер и релокацию, но к этому моменту меня позвали в другое место с более лучшими условиями. А куда именно узнаете в следующем посте, товарищи. Давайте соберем 700 огоньков, чтобы понимать: тема для вас интересна и ее нужно продолжать.

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

Хочешь поступить в ШАД или магистратуру, затащить олимпиаду? Или просто мечтаешь стать крутым специалистом, тащить собесы, но не хватает фундамента? Тогда тебе к нам!

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

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

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

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

Цена 7500р за курс, до 25 октября, далее повышение цены до 8500р. Если покупали наши курсы ранее, то цена 7000р. Если же покупали аналогичный курс, но хотите больше новых задач и материалов, то новый курс (материал полностью обновлен и расширен) обойдется вам всего за 5000 р!

Даты: начало курса 27.10

Как купить: приобрести курс и задать вопросы можно по данному адресу: @menshe_treh

Еще курсы серии:
➡️ алгоритмы старт 03.11
➡️ линейная алгебра старт 10.11
➡️ математический анализ старт 17.11

Задача с компании HFT (немогу сказать с какой именно)
Вам дается n строк, где число n четное. Ваша задача найти наибольшее число k, такое что существует способ разделения строк на пары, что в каждой паре хотя бы k первых символов совпадает.
Например:
4
abcd
abbb
efaa
efcd
ответ 2.

Решение:
Самое простое что приходит в голову это забинарить число k, дальше записать в словарь первые k букв всех слов, дальше посмотреть что значения всех ключей в нашей хеш-таблице четное число. Такое решение работает за O(N * logK), где N - сумма длин всех строк, K - максимальная длина строки.

Попросят решить задачу за O(N)
Чтобы решить задачу за линию вам понадобиться знания по структуре БОР. Если вы не знает что такое БОР то приходити на наши курсы мы вас всему научим.

И так давайте запишем все слова в БОР - это займет у нас O(N) времени. Давайте потом пройдемся по бору и обходом dfs и выпишем все значения в терминальных вершинках бора в векторв vt.

Зачем мы так сделали ????
Посмотрите внимательные на строки которые находятся на позициях vt[i] и vt[i-1] (i-четное) вы можете заметить, что для строкм на позиции vt[i-1] лучше всего подходит строка на позиции vt[i], осталные все строки имеют общий префикс меньшей длины.
Так получается чисто из за обхода БОРа с помощью dfs. Если детальнее хотите понять этот момент то приглашаю вас на курсы.

И так вот у вас есть вектор vt, вы просто проходитесь по четным i и смотрите наибольший общий префикс для строк на позиции vt[i] и vt[i-1] обновляете ответ через минимум по всем таким общим префиксам.
Решение за O(N).

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

Поступашки открывают набор на лучшие курсы по самой доступной цене 🎓

Хочешь поступить в ШАД или магистратуру, затащить олимпиаду? Или просто мечтаешь стать крутым специалистом, тащить собесы, но не хватает фундамента? Тогда тебе к нам! Сейчас для записи доступно четыре курса:

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

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

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

На семинарах с каждым учеником общаются по очереди, полноценное общение как здесь (никаких дурацких чатов, преподаватель лично выслушивает твои решения). Ежедневная связь, пробные собесы, экзамены, персональные рекомендации, инсайды и домашнее задание с проверкой, код ревью и с разбором от преподавателя, который отвечает даже после завершения курса! Все будет еще круче, чем на всех прошлый курсах (отзывы тут). Все для того, чтобы поступить в ШАД/ топовую магу уже летом или мы вернем потраченные деньги!

Цена 8500р за курс, до 15 октября скидка -10%. Если покупали наши курсы ранее, то цена 7000р. Если же покупали аналогичный курс, но хотите больше новых задач и материалов, то новый курс (материал полностью обновлен и расширен) обойдется вам всего за 5000 р!

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

Задача Яндекса/Шада.
Задача набирает обороты, рекомендую обратить на нее внимания всем кто готовится к собеседованию.

Дается два массива a, и b. Найти количество подотрезков в массиве а, что в этих подотрезках существуют подпоследовательности равные массиву b.

Решение:
Условия задачи сложнее чем решение. Не пытайтесь придумать решение быстрее чем за квадрат

Решим за квадрат: Переберем левую границу отрезка l, 0<=l<=n-1. Стартуем с этой позиции циклом i, поддерживая сколько первых элементов смогли собрать из массива b.
Пусть собрали cnt, тогда мы увеличиваем счетчик, если a[i]=b[cnt]. Как только собрали cnt=b.size, для фиксированного l, в качестве правой границы отрезка подойдут i, i+1, …, b.size-1. Мы можем просто в ответ прибавить b.size-i.

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

👾 Готовимся к ВсОШ по информатике на онлайн-сборах от Яндекса

Яндекс запустил онлайн-сборы для подготовки школьников к олимпиаде по информатике (ВсОШ). Не упустите возможность – это последний шанс записаться на интенсивную подготовку с опытными преподавателями из Кружка по олимпиадному программированию от Яндекса.

🧐Что вас ждет: бесплатные лекции и разборы олимпиадных заданий, которые пройдут бесплатно с 14 по 21 октября

🤓Что вам необходимо для участия: знание синтаксиса одного из языков программирования. Рабочие языки сборов: Python (школьный и муниципальный этапы) и C++ (региональный и финальный этапы)

👉🏻Зарегистрироваться до 14 октября и найти все необходимые материалы для подготовки можно на сайте.

🎉Присоединяйтесь и готовьтесь к победам вместе с Яндексом!

Вот и новый ролик вместе с Михаилом Абрамовичем! Разбираем миленькую задачку (решить в силах даже дошкольник) из собеседования в ШАД последнего набора и объясняем, почему ШАД - это лютая база и как туда поступить.

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

Вот и интервью с настоящей легендой! У нас в гостях ДиМашина, поступивший на физтех со 127 баллами ЕГЭ. Почему именно физтех? Какие учебные лафхаки работают? Почему нравится бить людей? Ну и прямо на ваших экранах, товарищи, Дмитрий поступит в ШАД!

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

Задача Яндекса.
За последние два месяца эта задача попадалась много раз.

Дается массив из 0 и 1.
Гарантируется что есть хотя бы один ноль и одна единица. Найти такую позицию нуля, что ближайшее расстояние до единицы максимальная.

Решение:

Во первых поймем, что между двумя единицами нужно выбрать позицию посередине.
…1,0,0,0,0,0,1,…..
Значит мы можем идти слева направо, хранить в переменной last последнюю позицию единицы. Если мы сейчас стоим в позиции i и в этой позиции единица, тогда мы пытаемся поставить единицу в позицию (i+last)/2, расстояния до ближайшей единицы равно min( (i+last)/2-last, i- (i+last)/2)
обновляем ответ если это расстояние больше чем нынешний ответ.

Остается случай, когда последовательность начинается с нуля или заканчивается нулем.

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

Вот и разбор программирования на стажировку в Тинькофф! Обязательно делимся с друзьями. Очень понравилась ваша активность по прошлому видосу, товарищи, поэтому ждём 9 тыс просмотров на ютуб ролике и выкладываем разбор контеста на стажировку в Яндекс.

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

ШОК! Админ надел платье, туфельки и пошел в офис Т-банка записывать свой тикток...

Распространяем: https://youtube.com/shorts/99VxC8WiaCo

Задача с Тинькофф.

Назовем число хорошим, если число является составным, а количество делителей простое число.
Найти количество хороших чисел на диапазоне [l, r] 1<=l<=r<=10^14.

Решение:
Заметим, что число n называется хорошим, если n=p^a
Где p-простое число и a>1.

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

Стоит обратить внимания, что a+1 должно быть простым числом.

Отсюда следует что p<=10^7. Так как a>1.
С помощью решето Эратосфена найдем все простые числа на отрезке [1, 1е7]
Переберем каждое простое число - так мы зафиксируем ‘p’. Осталось найти все такие ‘a’, что

l<=p^a<=r
a>1
a+1=простое число

Если вы будете перебирать ‘a’ в цикле (или раз за разом умножать переменную на p) то у вас будет переполнение типа и получите WA. Например возьмем p=1e7 когда будете возводить в третью степень произойдет переполнение. Да вы могли остановиться заранее и не возводить в степень, но как это понять ?

Нужно поступить иначе, давайте найдем максимальную степень b, что
p^b<=r, для этого мы просто будем делить r на p пока не станет равным нулю, от количество делений мы можем найти b.

Аналогично найдем максимальную степень d, что
p^d<=l-1.

Получаем, что нас интересует в качестве степень ‘a’ все простые числа на [d+1, b]. Благо этот отрезок очень маленький и можно честно перебрать там, проверяю что число простое используя посчитанную решето.

Т-банк открыл контест на стажировку осень-зима. Задания уже лежат тут, там же их можно обсудить вместе с админом. И конечно разбор нового контеста будет на наших курсах, так что присмотритесь к ним.

Стажировка в Т-банке - самая крупная стажировка после Яндекса по количеству мест. В целом решает не сколько баллы за экзамены, сколько "ваш социальный рейтинг", анкета — подробней смотрим здесь. После контестов зовут на собес: он дикая халява, если хоть немного пробовали вкатиться в специальность.

Готовиться в ШАД стало ещё проще: специально для вас подготовили разбор экзамена 2024 года! Смотрим, решаем и голосуем за публикацию на Хабре, если хотите больше таких статей!

https://habr.com/ru/articles/841858/

Задача Яндекса.
Новая задача в Яндексе, которая уже попалась 5 моим знакомым. Советую, если в скором времени собираетесь в Яндекс, разобрать эту задачу.

Вот сама задача
Если вкратце то дается набор точек на плоскости и спрашивается, правда ли существует линия параллельная оси 'y', которая симметрично отражает данные точки.

Решение также по ссылке можно увидеть.

Вопросы, которые задают на собеседование:

1) Вот вы поняли что координата прямой через которую делается отражения имеет координату (minX + maxX) / 2, но почему этого деления нету в коде ?

Тут два варианта, либо вам придется писать деление на два в вашем коде и работать с double (может дробями) либо не делить.... Но если вы решаете не делить то надо объяснить почему.
А ответ следующий, если прямая через которую делаем отражение имеет координату s, тогда точка (x, y) отразится в точку (2*s-x, y).
Заметим что мы s умножаем на два!!!
Так что мы могли бы взять s = (minX + maxX) и говорить что точка отражается на позицию (s-x, y).

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

2) В Яндексе скорее всего попросят учитывать повторы, то есть если две точки лежат на позиции [-1, 1] и одна точка на позиции [1, 1] то ответ False, так как одна точка останется без пары. Вам придется использовать хеш-таблицу вместо set чтобы учесть такой кейс.

Тут у нас началась регистрация на Всероссийскую олимпиаду по искусственному интеллекту для школьников 8–11-х классов

В соревнованиях будет три этапа: отборочный, основной и финальный. Все они пройдут на технологической платформе для онлайн-соревнований, IT-чемпионатов и олимпиад — All Cups от компании VK, которая выступает партнером олимпиады.

50 финалистов в ноябре встретятся очно и смогут посетить экскурсии в ведущие IT-компании, принять участие в мастер-классах и встретиться с экспертами – исследователями данных, разработчиками технологий ИИ и руководителями ИИ-направлений из Ассоциации «Альянс в сфере искусственного интеллекта».

Зарегистрироваться можно до 6 октября.

Яндекс собирается выделить ещё больше мест в ШАД, а значит попасть туда станет ещё проще. Лучше начинать потихоньку-понемногу готовиться уже сейчас. Вместе с МА разбираем примерчик из собеса прошлого набора, чтобы вы оценили свои силы!

Смотрим! Решаем! https://youtu.be/DxfV8JdqQlo

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

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

Тогда специально для тебя в честь начала учебного Поступашки объявляют акцию до 14 сентября! Любые два курса из шести можно приобрести оптом всего за 9 тыс рублей а любые три курса из шести можно приобрести оптом всего за 14 тыс рублей:

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

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

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

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

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

Яндекс обновил контест на стажировку осень-зима. Задания уже лежат тут, там же можно их обсудить вместе с админами. И конечно разбор нового контеста будет на наших курсах, так что присмотритесь к ним.

Стажировка в Яндексе - самая крупная стажировка из всех, больше всего мест и их точно хватит на всех. Весьма прозрачный отбор, о котором писали здесь. Для успешного прохождения на собесы обычно достаточно решить 2/3 заданий, а в прошлый раз только половину.

Также не забываем посмотреть полный цикл собесов в Яндекс наших учеников:
Бэкенд
Аналитика
Машинное обучение

Задача Яндекса.
В последние дни все чаще встречается задача:
Дается массив из целых чисел длины n > 1. Вы должны вернуть минимальное произведение, которое можно получить из двух чисел массива. (позиции чисел должны быть уникальны)

Решение:
Конечно нужно решать за линию.
Пусть max1, max2 - два максимальных числа из массива, при этом max1 >= max2.
Пусть min1, min2 - два минимальных числа из массива, при том min1 <= min2.

Если min1 <= 0 и max1 >= 0 то ответом будет min1 * max1

Иначе мы получаем два варианта:
1) Все элементы положительные, в таком случае нужно вернуть min1 * min2
2) Все элементы отрицательные, в таком случае вернем max1 * max2

Именно так лаконично рассмотреть случае.

Частые ошибки:
Не умение находить два максимальных/два минимальных числа за один проход циклом за линию.
Запутаться со случаями, когда в массиве нет отрицательного/положительного числа, но есть ноль.

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

Вот и non-tech-программа в IT для школьников! dreamlab — это бесплатная лаборатория, где ученики 8-11 классов могут попробовать себя в digital-направлениях: от тестирования и управления проектами до исследований и дизайна.

Годовая программа включает в себя лекции и мастер-классы по управлению и развитию цифровых проектов, пользовательскому опыту, продвижению и дизайну цифровых продуктов, коммуникациям и гибким навыкам. Участники будут работать над кейсами VK — классная возможность на практике познакомиться с реальными задачами. Формат смешанный — можно онлайн или офлайн. По окончании выпускники соберут портфолио и получат сертификаты. Это хороший старт для тех, кто хочет связать свое будущее с технологиями. Для участия необходимо оставить заявку до 20 сентября.

Вот и разбор аналитики на стажировку в Яндекс! Обязательно делимся с друзьями. Ждём 5 тыс просмотров на ютуб ролике и выкладываем МЛ. Советую поторопиться: контест вот-вот обновят.

Смотрим! Смотрим! https://www.youtube.com/watch?v=k4C9aWR6YJ4

Эти пет проекты должен сделать каждый ML специалист

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

1. Кредитный скоринг
Стоит ли давать кредит— довольно популярная задача и отличный выбор для новчиков, чтобы самостоятельно проделать все этапы. Сначала берем любой датасет на kaggle по запросу Credit Scoring. Проводим EDA, генерируем гипотезы, фичи, готовим данные для модели и делаем бейзлайн: логистическая регрессия. Затем уже можно попробовать случайный лес, градиентный бустинг, KNN или еще что по вкусу— сравниваем метрики. И на последок не забываем проанализировать результаты и культурно презентовать. Можно провести АВ тест на смой первой модели.
Все варианты решения и реализации можно найти в интернетах: GitHub, Хабр. Очень полезным будет посмотреть всякие выступления на конференциях по этой теме для вдохновения, да и это очень поможет на мл кейсах.

2. Наивный Байесовский классификатор (НБК)
Для конкретики будем классифицировать письма на спам. Опять же обработаем данные: удаляем числа, знаки препинания, стоп-слова, стемминги, лемматизацию.
Объединяем все методы предварительной обработки и создаём словарь слов и счётчик каждого слова в наборе данных для обучения:
1. Вычисляем вероятность для каждого слова в тексте и отфильтровываем слова со значением вероятности меньше порогового. Такие слова будут нерелевантными.
2. Для каждого слова в словаре создаём вероятность, что это слово окажется в спаме. Определяем условную вероятность для использования её в НБК.
3. Вычисляем прогнозируемый результат с помощью условных вероятностей.
НБК реализовать не сложно. Куда интересней погрузиться во всю теорию, которая за этим стоит, в вероятностные модели. К тому же, кейс фильтрации спама и подобного часто встречается на собесах.

3. MLOps
Можно наладить какой-то минимальный прод для проектов: например телеграм бот или FastAPI. Можно еще автоматизировать пайплайн с помощь AirFlow и попробовать запустить инфраструктуру не только локально, но и облаке. Конечно нужно будет поизучать Docker, Cuber, Hadoop, Spark, HDFS, Kafka. Но на самом деле ничего трудного— после нашего курса дата инженер будете делать такие вещи по щелчку пальцев.

4. Ранжирование и матчинг
Для начала лучше пробежаться глазами по статье и посмотреть, что пишут в интернетах. Можно выделить три подхода к задаче: поточечный, попарный, списочный. Советую начать с первого как самого простого. Для конкретики будем предсказать оценку релевантности для запросов тестового датасета. Здесь можно кстати поучиться парсить web-страниц и собирать сырые данные, размечать их с помощью какого-нибудь Яндекс-Толока. Делаем регрессию, а затем Random Forest Regressor, XGBoost, lightGBM, CatBoost.
Совсем продвинутые могут попробовать языковые модели в духе FastText, Word2Vec, DSSM и более сложные: BERT, можно даже попробовать архитектуру трансформеров.

5. Рекомендашки
Очень популярный кейс на собесах. Для начала лучше пробежаться глазами по этому разделу и посмотреть, что пишут в интернетах. Затем начинаем реализовывать самое простое как бейзлайн, например, content-based рекомендации, KNN. Дальше можно попробовать факторизации матрицы рейтингов по svd разложению или по более эффективной als архитектуре и функции ошибок bpr. Затем можно попробовать W2V подход, чтобы использовать последовательность взаимодействий пользователя для построения рекомендации следующего предмета.
Для знатоков DL можно попробовать DSSM, SasRec/Bert4Rec, MultVAE, Merlin или графовые нейронки: GCN-подобные архитектуры.
Также стоит попробовать обучение с подкреплением: многоруких бандитов.
Ну и конечно рекомендательные системы можно попробовать рассмотреть как задачу ранжирования.

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

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

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

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

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

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

Цена 7000р за курс, при покупке на одного человека. Если берете наши курсы впервые, то только сегодня (13.08 по мск) скидка 20% на курс инженер данных (скидки не суммируется)
Если покупали наши курсы ранее, то теперь на курс инженер данных цена 6000 р.

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