Задача из Собеседования в Amazon за 5 минут

Разбираем небольшую задачку, которую спросили на собеседовании в Amazon. Такие задачи надо уметь решать за 10-15 минут, но без опыта решения подобных задач найти самое быстрое решение может быть не просто.

Задача на литкоде: https://leetcode.com/problems/search-...
Пост на литкоде: https://leetcode.com/discuss/intervie...

Дисклеймер:
И задача, и пост на литкоде находятся в открытом доступе. Я к посту никакого отношения не имею и не могу гарантировать его правдивость.