🚂 Разбор задачи про бесконечный поезд Даже если вы уже знаете решение этой распространенной на собесах задачи, я на 95% уверен, что вы знаете популярное, но неоптимальное решение. Хотите удивить интервьюера оптимальным решением? Тогда давайте разбираться. Звучит задача так: __Представьте себе замкнутую по окружности железную дорогу. По ней едет поезд, последний вагон которого скреплён с первым так, что внутри можно свободно перемещаться между вагонами. Вы оказались в одном случайном вагоне и ваша задача — подсчитать их общее количество. В каждом вагоне можно включать или выключать свет, но начальное положение переключателей случайное и заранее неизвестно. Все вагоны внутри выглядят строго одинаково, окна закрыты так, что невозможно посмотреть наружу, движение поезда равномерное. Помечать вагоны как-либо, кроме включения или выключения света, нельзя. Количество вагонов конечно (не верьте заголовку). Как посчитать количество вагонов?__ Если видите задачу впервые, то попробуйте сначала решить ее сами. А популярный алгоритм решения заключается в следующем: Пусть в стартовом вагоне включен свет (иначе решаем от обратного): 1. Идём от стартового вагона в одном направлении и считаем шаги, пока не попадём в вагон со включённым светом. 2. В этом вагоне выключаем свет. 3. Возвращаемся назад ровно на столько шагов, сколько прошли вперёд. 4. Проверяем свет в стартовом вагоне. Если он выключен, значит мы случайно погасили именно стартовый вагон, и пройденное число шагов – это и есть число вагонов. Если включён, повторяем процесс. По этой ссылке можно найти мой шортс с визуальным объяснением решения. Но у такого решения есть нюанс. Если подойти к этой задаче не как к логической, а как к алгоритмической, то алгоритмическая сложность решения в худшем случае будет ~O(n^2) 🤯. Есть много схожих решений с микрооптимизациями, но порядок сложности они не меняют. Можно ли решить задачу за линейную O(n) сложность? Сначала также подумайте сами. А идея решения такая: 1. Включаем свет в стартовом вагоне. 2. Начинаем ходить влево и вправо на отрезки длиной 1, 2, 4, 8, 16, 2^N вагонов. При каждом проходе во всех вагонах слева от стартового включаем свет, а во всех вагонах справа от стартового – выключаем. В какой-то момент отрезки слева и справа пересекутся: мы окажемся в вагоне, где ожидался уже включенный или выключенный свет, а в реальности окажется наоборот. Это значит, что круг вагонов замкнулся в этой точке, и мы нашли точное число вагонов. В комментариях к посту прикрепил визуальный пример. Итоговое решение имеет линейную сложность. Вуаля ⭐️ Продолжаю разбирать популярные задачи с собеседований? Тогда поддержи рубрику огоньком под этим постом 🔥 #задачиссобеседований