Если вы родились в 80-х или 90-х, то наверняка слышали о
Snake. То есть, скорее всего, вы потратили
безумное количество времени на своём Nokia 3310, выращивая огромную змею на мелком экранчике. Что ещё мы помним о телефонах Nokia?
Их неразряжающийся аккумулятор, правда? Как такой «примитивный» телефон выдерживал долгие часы игры в «Змейку» без разрядки аккумулятора?
Короткий (и неполный) ответ: всё дело в методе
скользящего окна.
Мы бы с радостью написали целую статью о
Snake, но в этом посте мы всё-таки рассмотрим менее зрелищный, но тем не менее очень важный метод, и ответим на вопросы типа:
- Почему мы и другие программисты считаем его фундаментальным алгоритмом?
- Почему он так часто используется на технических собеседованиях?
- Как он использовался в Snake и других «реальных» областях применения?
- На какие самые популярные вопросы собеседований можно (лучше) ответить с помощью метода скользящего окна?
Если вы готовитесь к собеседованию, читаете статью из интереса, или хотите узнать что-то новое, то продолжайте читать. При этом вы можете спокойно пропускать лишнее и переходить к самым интересным разделам.
NB: Если вас волнует только
«Змейка» (и мы вас вполне понимаем), то можете перейти к самому концу поста.