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

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

Хотите учить алгоритмы, но не знаете Python? Товарищи, алгоритмы сами по себе не самые простые. А если параллельно с решением задачи приходится гуглить, как написать цикл for, подготовка превращается в отдельный вид страдания 😔 Поэтому запускаем бесплатный открытый курс «Python для алгоритмов». С 14 по 19 июля разберём базу Python, которая нужна именно для решения алгоритмических задач. Почему Python? Именно его чаще всего выбирают для решения задач на алгоритмических собеседованиях и технических отборах. У языка простой синтаксис, поэтому на собесе можно сосредоточиться на решении задачи, а не на борьбе с кодом. За 6 дней разберём условия, циклы, функции, строки и основные структуры данных. Научимся читать код, работать с вводом и выводом и переводить уже придуманное решение задачи на Python. Задача курса — построить фундамент, с которым вы сможете полноценно начать изучать алгоритмы и структуры данных. Курс подойдёт, если вы: ➡️ никогда раньше не программировали ➡️ когда-то учили Python, но забыли базовый синтаксис ➡️ планируете проходить отборы на стажировки, в ШАД, Академию аналитиков Авито и другие школы 🏆А самых сильных участников ждёт отдельный бонус. Лучшим подарим полный курс по алгоритмам 📌Ссылка на курс в нашем боте - @Postupashkianalitycsbot Первые материалы уже выложены!

Задача с собеседования в Josh Technology Group Дан массив целых чисел temperatures, представляющий ежедневные значения температуры. Верните массив answer, где answer[i] - это количество дней, которое нужно подождать после i-ого, чтобы наступил день с более высокой температурой. Если нет будущего дня, для которого это возможно, вместо этого сохраните answer[i] == 0. Пример 1: Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0] Пример 2: Input: temperatures = [30,40,50,60] Output: [1,1,1,0] Пример 3: Input: temperatures = [30,60,90] Output: [1,1,0] Ограничения: 1 <= temperatures.length <= 10⁵ 30 <= temperatures[i] <= 100 НАШ ЧАТ АЛГОРИТМИСТОВ Решение При наивном решении мы бы итерировались по массиву для каждого дня в поисках более тёплого c асимптотикой O(n²). Но мы видим паттерн - поиск ближайшего большего/меньшего эл-та, поэтому используем монотонный стек (стек, элементы которого хранятся в строго возрастающем или строго убывающем порядке). В данном случае стек будет монотонно убывающим. При добавлении нового эл-та алгоритм будет сравнивать его с вершиной стека: - Пока текущий эл-т больше верхнего эл-та стека (stack[-1][0]): достаём верхний элемент, вычисляем ответ для него (через разницу между индексами текущего эл-та и эл-та из стека) и удаляем эл-т из стека. Кладём текущий эл-т в стек. Разберём более подробно: Создаём: - стек для хранения пар (температура, индекс) в монотонно убывающем порядке; - массив answer длиной n, равной длине входящего массива. Заполняем его нулями. Итерируемся по массиву температур: Пока стек не пуст и в нём есть дни холоднее текущего: - достаём значение и индекс более холодного дня, удаляя его из стека; - вычисляем разницу между индексом текущего дня и индексом более холодного дня - таким образом, узнаем кол-во дней, которые должны пройти между ними. Записываем разницу в массив answer по индексу более холодного дня (answer[stack_i]). После выхода из цикла while или непопадания в него: добавляем текущий день в стек для последующего сравнения с другими значениями. В конце возвращаем заполненный массив answer. Сложность O(n) - по времени (каждый эл-т добавляется в стек только 1 раз и может быть удалён только 1 раз) O(n) - по памяти (в худшем случае в стек придётся добавить все элементы входного массива длиной n) Код class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: n = len(temperatures) stack = [] answer = [0] * n for i, temp in enumerate(temperatures): while stack and stack[-1][0] < temp: stack_temp, stack_i = stack.pop() answer[stack_i] = i - stack_i stack.append((temp, i)) return answer @algoses

Задача с собеседования в eBay Дан массив nums, состоящий из различных целых чисел. Верните все возможные перестановки этого массива. Вы можете вернуть ответ в любом порядке. Пример 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Пример 2: Input: nums = [0,1] Output: [[0,1],[1,0]] Пример 3: Input: nums = [1] Output: [[1]] Ограничения: 1 <= nums.length <= 6 -10 <= nums[i] <= 10 Все числа в nums уникальны. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Так как необходимо вернуть все возможные перестановки элементов массива, используем backtracking - алгоритм поиска с возвратом. Суть алгоритма: на каждом шаге добавляем элемент и строим полную правильную перестановку, после её сохранения последовательно возвращаемся по стеку вызовов до последней точки выбора и исследуем другие ветки из этой точки. Создаём два списка: res - для хранения найденных корректных перестановок; permutation - временный список для "собирания" текущей перестановки. Чтобы оптимизировать отслеживание уже использованных эл-тов, создаём множество used (проверка наличия эл-та за O(1) вместо O(n) при поиске по списку). Запускаем рекурсивную функцию backtrack(): Базовый случай: если длина текущей перестановки достигла n (длина массива nums), значит: мы использовали все эл-ты -> перестановка готова -> сохраняем копию текущей перестановки в res (копия нужна, чтобы последующие изменения не затронули уже сохранённый ответ) и завершаем текущий вызов рекурсии, откатываясь назад. Рекурсивное ветвление: перебираем все возможные эл-ты, которые можно добавить следующими. Для каждого допустимого выбора (эл-та, которого ещё нет в текущей перестановке): - добавляем значение в used ("помечаем" эл-т как использованный) и permutation (добавляет эл-т в текущую перестановку); - вызываем рекурсию для выбора следующего значения; - удаляем последнее добавленное значение из permutation (для возврата к развилке и исследованию другой ветки перестановки) и used (для возможности использования эл-та в других ветках). Функция завершается, когда полностью исследовано дерево возможных перестановок. Для этой задачи существует альтернативное решение через перестановки элементов в исходном массиве (in-place swapping). Делитесь им в комментариях! Сложность O(n*n!) - по времени (так как существует n! перестановок для массива размера n, каждая из них копируется в список за O(n)) O(n) - по памяти (стек рекурсии глубиной n, множество used размера n и список permutation размера n) Код class Solution: def permute(self, nums: List[int]) -> List[List[int]]: n = len(nums) res, permutation = [], [] used = set() def backtrack(): if len(permutation) == n: res.append(permutation[:]) return for i in nums: if i not in used: used.add(i) permutation.append(i) backtrack() permutation.pop() used.remove(i) backtrack() return res @algoses

В новом ролике обсудим современное рабство: стоит ли идти в айти галеры ради первого опыта работы на примере Астона! Осторожно, факты вас шокируют! Смотрим! Смотрим! https://www.youtube.com/watch?v=y7QwkvxSzbc