Инсайды с собеседования в Авито. Алгоритмическая секция.

• Автор делится опытом прохождения собеседования в Авито.  

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

• Подписка на телеграм-канал автора для получения дополнительной информации.  

• На алгоритмическом этапе в Авито всего четыре задачи.  

• На собеседовании нужно решить две из них.  

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

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

• На вход подаются два массива целых чисел.  

• Необходимо вернуть массив, представляющий сумму массивов.  

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

• Задача похожа на сложение в столбик.  

• Автор объясняет, как решать задачу, начиная с написания функции.  

• Функция должна возвращать массив.  

• Нахождение длины результирующего массива.  

• Выделение памяти под новый массив.  

• Задача требует учета переносов.  

• Объявление переменной переноса.  

• Итерация по элементам массивов и сложение.  

• Проверка выхода за рамки массивов.  

• Учет переносов и корректное представление чисел.  

• Использование остатка от деления на десять для корректного представления чисел.  

• Тестирование функции на примерах.  

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

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

• Необходимо написать функцию, которая принимает массив чисел и число и возвращает индексы элементов, сумма которых равна целевому числу.  

• Примеры: 2 + 15 = 17, 2 + 7 = 9, 3 + 2 = 5, 2 + 4 = 6.  

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

• Написать функцию, которая принимает массив и целевое число и возвращает массив индексов.  

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

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

• Написать тест-кейсы для проверки работы функции.  

• Решение работает, но не оптимально по времени и памяти.  

• Время выполнения: O n^2, память: O n.  

• Использовать хэш-таблицу для запоминания индексов элементов массива.  

• На каждой итерации проверять, есть ли текущее слагаемое в хэш-таблице.  

• Если есть, вернуть индексы слагаемых, иначе запомнить текущее слагаемое и его индекс.  

• Время выполнения: O n, память: O n.  

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

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

• Разобраны две задачи из четырех возможных.  

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