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

Имеется n пользователей, каждому из них соответствует список email-ов (всего m email-ов). Например:
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, значит это один и тот же пользователь.

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

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

Решение:

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

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

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

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

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

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

Например, запускаем ДФС с вершины user1 и посещаем вершины user2, user4, xxx@ya.ru, foo@gmail.com, lol@mail.ru, ups@pisem.net. В качестве ответа вы берете любого юзера и все почты, которые успели посетить. Дальше запускаете ДФС от непосещенной вершины (это вершина user3) и запускаете ДФС.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача: Дается массив целых и уникальных чисел, ваша задача сжать этот массив, например был у вас массив
-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).

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

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

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

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

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


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

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

Для двух массивов целых чисел длины 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).

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

@algoses

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

Умеете ли решать следующую задачу?
Дается массив целых чисел '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 из литкода, отсортировать массив который вам дают и применить метод двух указателей.

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

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

У Пети был массив целых чисел, состоящий из уникальных элементов и отсортированный по возрастанию. Его друг Вася, когда увидел массив, начал завидовать Пете и решил циклически сдвинуть исходный массив на 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

Задача с 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

Задача с МЛ секции Яндекс (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

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

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

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

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

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

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

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

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

Пусть 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

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

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

@postypashki_old

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

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

@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<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

Задача с зарубежной компании.
Дается матрица размера 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