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

Классическая задача из сборника Владимира Арнольда

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

Расстояние между городами A и B — 40 км. Два велосипедиста одновременно выехали навстречу друг другу со скоростями 10 и 15 км/ч. Вместе с первым вылетела муха со скоростью 100 км/ч. Она летает от одного велосипедиста к другому, мгновенно разворачиваясь при каждой встрече, пока велосипедисты не встретятся.

Сколько километров пролетит муха?

Решение

Велосипедисты встретятся через 40 / (10 + 15) = 1,6 часа. Всё это время муха летит со скоростью 100 км/ч. Её путь — 160 км.

Подробный разбор, включая ещё один способ решения через сумму бесконечной геометрической прогрессии, ищите в канале «Зачем мне эта математика?». Там регулярно публикуют задачи различной сложности и обсуждают решение в комментариях.

Реклама. ООО «Яндекс». ИНН 7736207543.
erid:CQH36pWzJqVJCAGJnb47qnJa4neudJUJ7iTgmHpT17shxG

Чёрная пятница от Поступашек!

Товарищи, хотите получить оффер в бигтех, перейти на более высокую позицию или увеличить зарплату? Мы открыли распродажу всех карьерных курсов Поступашек, которые помогут достичь этих целей — записывайся 📌

Скидки действуют только до 15 ноября включительно! Все курсы и актуальные цены можно посмотреть на сайте.

🔊Обращаем внимание на новую линейку курсов по ML System Design, A/B-тестам, Deep Learning и Soft Skills.
Цена на них всего 6 950 ₽ за курс!

Только на новой линейке тебя ждут:

➡️ Практика на реальных собесах и отборах. Сборник вопросов с собесов и разборы контестов в Яндекс, Т-Банк, Ozon и другие компании, мок-интервью и возможность получить рефералку в бигтех
➡️ 6 недель карьерного сопровождения после курса. Поможем разобраться с откликами, подготовиться к собеседованиям и исправить ошибки, которые мешают получить оффер
➡️ Менторское сопровождение для лучших выпускников. Дополнительная поддержка на собеседованиях для тех, кто сдаст все ДЗ, сделает пет-проект и будет ходить на семинары
➡️ Поддержка после трудоустройства. Не оставим один на один с рабочими задачами и вопросами во время испытательного срока
➡️ Гарантия оффера с зарплатой от 150 000 ₽ в месяц или возврат денег, если не получишь оффер
А если сомневаешься, стоит ли учиться с нами, почитай отзывы наших учеников

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

⭐️Для записи и вопрос — пиши менеджеру⭐️

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

Дан строковый массив words и бинарный массив groups, оба длины n.
Подпоследовательность words называется чередующейся, если для любых двух соседних строк в этой последовательности соответствующие элементы в groups (по тем же индексам) различаются (то есть не может быть двух подряд идущих 0 или двух подряд идущих 1).

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

Обратите внимание, что элементы в words различны.

Пример 1:
Input: words = ["e","a","b"], groups = [0,0,1]
Output: ["e","b"]
Explanation: Подпоследовательность ["e", "b"] подходит, так как groups[0] != groups[2]. Другая подходящая подпоследовательность - это ["a", "b"], так как groups[1] != groups[2]. Можно продемонстрировать, что длина самой длинной подпоследовательности индексов, удовлетворяющей условию, равна 2.

Пример 2:
Input: words = ["a","b","c","d"], groups = [1,0,1,1]
Output: ["a","b","c"]
Explanation: Подпоследовательность ["a", "b", "c"] подходит, так как groups[0] != groups[1] и groups[1] != groups[2]. Другая подходящая подпоследовательность - ["a", "b", "d"], так как groups[0] != groups[1] и groups[1] != groups[3]. Можно продемонстрировать, что длина самой длинной подпоследовательности индексов, удовлетворяющей условию, равна 3.

Ограничения:
1 <= n == words.length == groups.length <= 100
1 <= words[i].length <= 10
groups[i] равно либо 0, либо 1.
words состоит из различных строк.
words[i] состоит из строчных английских букв.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Ещё одна разминочная задачка.

Используем жадный алгоритм:
Берём первый эл-т массива words в результирующий массив, это всегда оптимально, так как:
- Если оптимальная подпоследовательность начиналась бы с более позднего эл-та этой же группы, его можно было бы заменить на words[0] без потери длины.
- Если же подпоследовательность начиналась бы с другой группы, добавление words[0] в начало сделало бы её ещё длиннее.
Таким образом, потенциальные точки смены группы не пропускаются.
Подпоследовательность продляется, только когда группа меняется (с 0 на 1 или с 1 на 0). Значит, если алгоритм будет "жадно" брать эл-т в момент смены группы, будут взяты все возможные эл-ты (каждая смена группы, соответственно, даёт максимум один эл-т) => построена самая длинная чередующаяся подпоследовательность (1 + кол-во смен группы в исходном массиве).

Создаём массив res, состоящий из words[0].
Проходим по словам и соответствующим им группам:
- если текущая группа groups[i] не равна предыдущей (эквивалентно: не равна группе последнего взятого эл-та), произошла смена группы: добавляем слово под этим же индексом в res.
Возвращаем результирующий массив.

Сложность
O(n) - по времени (проходим по массиву words длиной n)
O(n) - по памяти (для хранения res)

Код
class Solution:
def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:
res = [words[0]]

for i in range(1, len(words)):
if groups[i] != groups[i - 1]:
res.append(words[i])

return res

@algoses

Товарищи, Поступашкам нужны контент мейкеры в основной канал по алгоритмам, мл, аналитике и другим дисциплинам. Если вы творческая личность, интересующейся аналитикой (или другим), вам нравится писать посты/ придумывать идеи для контента, то обязательно пишите @vice22821. Оплата сдельная, ориентировочно за один пост от 2 тыс до 15 тыс рублей.

Обязательно делитесь с ребятами, которым это может быть интересно.