Тренировки по алгоритмам 5.0 Собеседование по алгоритмам в прямом эфире + его разбор

• Рудольф, руководитель кандидат генерации в рекламе Яндекса, проводит пробное интервью с Димой Пугачевым, стажером.  

• Цель: показать процесс алгоритмических собеседований и обсудить детали с Михаилом Густокашиным, директором центра студенческой олимпиады ФКН.  

• Интервью будет включать две задачи, на которые отводится 40 минут.  

• Рудольф объясняет формат собеседования: обсуждение задачи, проговаривание алгоритма, написание кода.  

• Важно не тратить время на написание лишнего кода и обсуждать все возникающие вопросы.  

• Дима уже знаком с форматом, но Рудольф повторяет его для ясности.  

• Задача: найти пару элементов массива, сумма которых ближе всего к целевому значению.  

• Обсуждение условий: массив может быть пустым или содержать один элемент.  

• Решение: перебрать все пары элементов, но это неэффективно.  

• Предложение использовать алгоритм двух указателей для сортировки массива.  

• Описание алгоритма: перебирать меньший элемент и находить правильный правый элемент.  

• Оценка сложности: линейное время и отсутствие дополнительной памяти.  

• Обсуждение использования ссылок для оптимизации памяти.  

• Решение: использовать ссылки для предотвращения лишнего копирования.  

• Подготовка начального ответа и сортировка массива.  

• Определение изначального ответа: сумма первых двух элементов.  

• Введение переменной для хранения разницы между текущим ответом и целевым значением.  

• Начало цикла для перебора меньшего элемента массива.  

• Обсуждение указателя на правый элемент.  

• Указание на необходимость сдвига правого элемента.  

• Проверка условия для сдвига правого элемента.  

• Сравнение текущего ответа с возможным улучшением при сдвиге правого элемента.  

• Обновление текущего ответа при улучшении.  

• Возвращение обновленного ответа.  

• Предложение проверить алгоритм на тестовых кейсах.  

• Добавление проверки на равенство левого и правого элементов.  

• Исправление условия для предотвращения двойного учета элементов.  

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

• Исправление примера, где массив содержит повторяющиеся элементы.  

• Проверка на отрицательные числа и их влияние на решение.  

• Обсуждение возможных проблем с отрицательными числами.  

• Проверка безопасности алгоритма с учетом отрицательных чисел.  

• Предложение написать дополнительные тесты для проверки.  

• Обсуждение проблемы с массивом, где сумма элементов равна 4.  

• Пример с массивом 1, 2, 2, где сумма должна быть 4, но условие "меньше или равно" не выполняется.  

• Предложение изменить условие, чтобы избежать проблем с повторяющимися элементами.  

• Обсуждение необходимости оптимизации кода для предотвращения ошибок.  

• Предложение использовать команду "макс" для проверки условий.  

• Уточнение, что проблема возникает только при наличии повторяющихся элементов.  

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

• Предложение сдвигать правый указатель до тех пор, пока он не станет больше левого плюс один.  

• Уточнение, что это устраняет необходимость в дополнительном условии.  

• Обсуждение микрооптимизации кода и переход к следующей задаче.  

• Введение новой задачи: определить, сколько минут в течение суток работают все кассы одновременно.  

• Обсуждение расписания работы касс и их типов.  

• Уточнение, что кассы могут работать круглосуточно или в полуинтервале.  

• Предложение перебирать часы и проверять, сколько касс открыто.  

• Обсуждение сложности решения: перебирать все кассы для каждого часа.  

• Уточнение, что круглосуточные кассы не интересны.  

• Предложение разбить кассы на две группы для удобства обработки.  

• Обсуждение возможности использования массива для хранения информации о кассах.  

• Уточнение, что массив должен быть размера 24 для хранения информации о каждом часе.  

• Предложение редактировать массив на месте для оптимизации памяти.  

• Обсуждение ввода массива пар интов и вывода одного числа.  

• Уточнение, что сортировать массив не нужно.  

• Предложение использовать отдельную переменную для хранения количества касс.  

• Обсуждение проблем с точностью при учете секунд.  

• Уточнение, что для учета секунд потребуется массив размером 86,400.  

• Предложение альтернативных подходов для решения задачи.  

• Обсуждение техники сканирующей прямой для обработки событий.  

• Создание массива событий, где каждое событие - это открытие или закрытие кассы.  

• Сортировка событий по времени для упрощения обработки.  

• Обсуждение более простого варианта реализации.  

• Введение переменной для обновления количества открытых и закрытых касс.  

• Различие между дневными и ночными кассами.  

• Игнорирование круглосуточных касс при обработке.  

• Разделение касс на дневные и ночные.  

• Учет изменений количества касс в зависимости от времени открытия и закрытия.  

• Запись всех обновлений и подсчет текущего количества открытых касс.  

• Перебор часов и учет изменений количества касс.  

• Проверка работы алгоритма на примере сэмпла.  

• Обсуждение крайних случаев, таких как все кассы закрыты или открыты.  

• Проверка корректности работы алгоритма при различных условиях.  

• Обсуждение возможных проблем с производительностью при использовании минут или секунд.  

• Проверка функции на пустой вектор.  

• Обсуждение ситуации, когда на вокзале нет касс.  

• Решение считать, что все кассы открыты, если вектор пуст.  

• Завершение обсуждения задач.  

• Благодарность стажерам за помощь.  

• Представление Михаила Густокашина, директора центра студенческих олимпиад ФНК.  

• Обсуждение пройденной секции и её связи с тренировками.  

• Страх перед публичными выступлениями и необходимость тренировок.  

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

• Трудности в публичных выступлениях и необходимость тренировок.  

• Практика на собеседованиях помогает справляться с волнением.  

• Тренировка умения объяснять задачи и алгоритмы.  

• Практика на собеседованиях и объяснение задач одногруппникам.  

• Важность тренировки умения объяснять задачи.  

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

• Сложности в запуске решений и необходимость ручного тестирования.  

• Важность правильного определения сложности алгоритмов.  

• Ошибки при определении сложности и их последствия.  

• Важность тестирования и заложения времени на тестирование.  

• Практика создания тестовых кейсов заранее.  

• Рекомендации по подготовке к секции и тестированию.  

• Обсуждение предложений по улучшению задач.  

• Использование бинпо и других подходов для решения задач.  

• Важность обсуждения различных решений и подходов.  

• Тайминг и этапы собеседования по алгоритмам.  

• Решение двух задач за час.  

• Важность отсутствия ошибок и опечаток в коде.  

• Рекомендации по использованию переменных и избеганию опечаток.  

• Текущее собеседование прошло успешно, две задачи решены за выделенное время.  

• Проверяющий не запускает код, а ограничивается текстовым редактором.  

• В процессе написания кода проверяющий записывает хронологию и ошибки.  

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

• Кандидат должен сам проверять свой код на тест-кейсах.  

• Простые функции можно протестировать в уме.  

• Две задачи должны быть полностью решены за час.  

• Ошибки, не замеченные проверяющим, учитываются, но имеют меньший вес.  

• Задачки должны быть решены до конца, даже если не все ошибки найдены.  

• Две задачи должны быть решены и достаточно хорошо оптимизированы.  

• Обсуждение алгоритма перед написанием кода помогает в оптимизации.  

• Микро-оптимизации, такие как чистота кода, имеют незначительный вес.  

• В Яндексе много вакансий, где можно работать с алгоритмами.  

• Начинающие стажеры могут работать с алгоритмами в бэкенд-разработке или EMR.  

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

• Решения проверяются визуально, без запуска кода.  

• Шутки и анекдоты приветствуются, но не должны мешать решению задач.  

• Важно поддерживать баланс между шутками и решением задач.  

• Если задача знакома, можно озвучить оптимальное решение.  

• Если задача была на прошлых собеседованиях, лучше предупредить.  

• Использование заготовок не допускается, решение должно быть реализовано заново.  

• Сложность задач на собеседованиях и стажировках схожа.  

• Тренировки помогают отработать стандартные подходы.  

• Волнение может усложнить решение задач, поэтому задачи на собеседованиях менее сложные.  

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

• В прошлом собеседования часто проводились очно, и использование блокнота было нормой.  

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

• Тренировки помогают подготовиться к собеседованиям.  

• Михаил Густокашин и Рудольф провели собеседование.  

• Приглашение на стажировки и благодарность за участие.