Загрузка…
Загрузка…
data / middle / tech_screening
Формат
online
Стадия
tech_screening
Когда
within_quarter
Длительность
—
01
Код
Сгенерируйте матрицу 5 на 5, состоящую из различных чисел (числа не должны повторяться).
Разминочная задача; по словам автора, многие пытаются сделать что-то рандомное, хотя достаточно простого очевидного решения. Задача, видимо, на отсев тех, кто переусложняет.
02
Код
Дана строка. Найдите в ней подстроку максимальной длины, все символы которой уникальны (например, для строки с повторяющимся символом 'c' ответом будет максимальная подстрока без повторов).
Аналог задачи 'Longest Substring Without Repeating Characters'. Наивное решение за O(n^2) двумя циклами не подходило — требовалось оптимальное за O(n) одним проходом с указателем и хеш-таблицами (словарь для индексов + множество для встреченных символов). Интервьюер подсказал сложность оптимального алгоритма, после чего кандидат решил задачу. На решение ушло около часа. Кандидат также обсудил с интервьюером, как можно было заранее предположить сложность O(n), не зная алгоритма.
Заметки
Транскрипт — видео блогера о прохождении алгоритмического лайвкодинг-собеседования в ВК на позицию, связанную с data science. Автор отмечает, что не ожидал секции по алгоритмам и предполагает, что ВК перенял процесс у Яндекса (про собеседование в Яндекс у автора есть отдельное видео, вопросы из него в этом тексте не приводятся). По итогам секции задачи решены, но исход процесса не сообщается.
Подготовка
Автор советует: не сдаваться сразу, даже если не знаешь решение — накидывать идеи и варианты вслух (за неверные предложения баллы не снимают, а за полное отсутствие решения — да). Большинство алгоритмических задач (кроме графов) решаются двумя техниками: указатели и хеш-таблицы (словари и множества). Сложность алгоритма — сильная подсказка к подходу: O(log n) — думать про бинарный поиск, O(n) — один проход по массиву с указателями, O(n log n) — цикл с бинарным поиском внутри. Если на вход приходит строка/массив и нужно что-то найти — часто решается одним проходом или динамическим программированием.
Стиль интервьюера
Добрый, спокойный интервьюер; кандидату понравилось проходить собеседование. Давал подсказки — в частности, подсказал сложность оптимального алгоритма, что помогло выйти на решение. Доброжелательно отреагировал на решение ('в целом решил — молодец').