Факапы

Алгособес в Яндекс

Вот и закончился мой второй технический собес в Яндекс на позицию продуктового аналитика. Про первый можно прочитать тут.

Для аналитиков секция с алгоритмами считается упрощенной: нужно решить лишь 1 задачу за 30 минут. После небольшого знакомства с интервьюером, мы сразу приступили к делу.

Задача: Есть 2 строки. Написать функцию, которая возвращает True, если из одной строки можно получить другую за не более чем одно изменение (вставка символа/удаление символа/замена символа), и False в обратном случае.

Да-да, задача на редакционное расстояние. На собесе сказал про алгоритм Левейнштейна, но было очевидно, что O(n^2) здесь будет слишком долго. В итоге написал за O(n), но с доп памятью. Интервьюер попросил сделать без нее. Немного повозился, по итогу как раз уложился в полчаса. Результатов еще нет, но, надеюсь, что все будет ок 🙏

Делитесь своими идеями решения задачи в комментариях 👇

#продуктовая_аналитика