Эту Несложную Задачу НЕВОЗМОЖНО Решить — Собеседование в Apple

Разбираем задачу, которую дали моему знакомому на собеседовании в Apple на позицию Software Developer. При этом найти решение самому заранее не зная ответ, как мне кажется, невозможно.
Причем задача звучит очень просто, а решение пишется буквально в несколько строк кода.

Токен - LdtCKJPt2

---
Дисклеймер:
Изначальная задача, которую дали моему знакомому, была немного другой, но решалась с помощью этого же алгоритма.

[rafailmuhamedshin]

А на работе в это время: "Сделайте пожалуйста эту кнопку БОЛЬШЕ"

[TheSome]

Это не для работников задачка, а для любителей алгоритмов. Я считаю, что многие собеседующие путают, нужен ли им сотрудник, который фанатеет по самым разным необычным алгоритмам и хитрожопым решениям, или им нужен простой усидчивый и усердный сотрудник, который не будет просирать дедлайны.

[roemujw]

Про доказательство второй части.

Ключевой момент -- понять, что время первой встречи М нацело делится на длину цикла С.
Почему? Медленный указатель за время M сделает M шагов, быстрый -- 2*M.
Но по предположению они должны встретиться, поэтому быстрый указатель сначала дойдёт до шага M (естествено, зайдя в цикл), а за оставшееся время навернёт ЦЕЛОЕ число кругов внутри этого цикла. Если число нецелое -- встретиться не получится.
Таким образом:
2*M = M + alpha*C
M = alpha*C
Ну а дальше просто. Возвращаем первый указатель в начало, вторым продолжаем с места встречи М, но уже с единичной скоростью. Я утверждаю, что через M шагов они снова встретятся. Первый указатель дойдёт до точки M, а второй, начав с неё, просто прокрутится целое число раз внутри цикла, ибо M = alpha*C.
Нас интересует точка начала цикла X. Т.к. наши указатели встретились, при этом двигаясь с одинаковой и единичной скоростью, то от точки начала цикла X до точки M они шли вместе. Поэтому точка первой встречи на втором прогоне и есть X.

[SargsyanAndranik]

Вы не поверите, но в моём первом собеседовании (в 2013) именно эту задачу спросили, я решил так, как в первой части видео, а другое решение они просто объяснили и всё :)

[parmetra]

Очень интересные видео с разбором задач и алгоритмов. Ждём ролики как можно чаще!

[bb]

решил эту задачу за 1 проход по списку и не выделяя памяти) но с одной оговоркой (в условиях не было: что список перестанет быть списком) проходим по нодам, и проверяем на что ссылается нода, если next == null, то конец списка, если next == nextNode, то переходим на эту ноду, а в текущей ноде next сетим на себя) теперь первая нода которая ссылается на саму себя и будет вершиной цикла, сложность О от Н, выделяем памяти 0, все условия выполнены

[llxwtnv]

История этого алгоритма берёт начало из задачи на собесе в гугле о том как найти цикл в замкнутом списке.И в 90ые годы один чело придумал (чем удивил) алгос с обходом двумя указателями, которые встретятся рано или поздно. Т.е. то, что было ВАУ тогда сейчас хотят чтобы все знали (нафига?!) по дефолту.

[HideDJeker]

В 2014 году купил первую книгу по программированию - работа мечты для программиста (дж. Монган), данная задача была описана вроде самой первой, и решение там через быстрый и медленный указатель. На самом деле задачи с хитрыми алгоритмами даются людьми которые даже не знают что она как то хитро решаются).

[yohan]

Блин, вот зачем знать столько алгоритмов? Есть классические, а дальше надо уметь думать и составлять свои. Я считаю, что основная цель собеседования - это проверить, способен ли "думать" собеседуемый

[vashwind]

С ходу придумался такой вариант, помимо массива узлов, которые уже обходили:
При обходе списка указатель получает значение следующего узла, при этом полю next предыдущего присваиваем заведомо неправильное значение, к примеру -1, и далее переходим к следующему узлу и так далее.
В конце концов мы приходим к узлу, поле next которого содержит null - значит нет цикла, либо -1, значит это узел начала цикла.
Да, при этом мы портим список, но в условии задачи его сохранение не звучало. ))

[nnevsky]

Я как-то раз ходил на техническое собеседование в банк. По факту собрали группу человек 6 в компьютерном классе, и дали задачу создать простого биржевого робота (что это такое мы без понятия). Время было ограничено одним часом, из которого первые 20 минут ушли на обсуждение, начинать было нельзя, даже если ты начал понимать что от тебя хотят. За оставшиеся 40 минут задачу не решил никто, даже хотя бы неправильно! А я для себя сделал вывод - что даже если пройду испытание работать здесь не буду!

[SAlexanderV]

С самого начала понял, что суть задачи именно в О(1) памяти, но так и не допер, как это сделать. Посмотрел видео, и понял, что надо иметь воображение, чтобы решить такую задачу: это как два гонщика на треке, у которых скорости отличаются в 2 раза, они будут встречаться (один опережает второго) когда остаток от деления разности пройденных путей на длину круга будет равен нулю, что произойдет не сразу, и.к. может быть линейный участок в начале, но рано или поздно произойдет. И как только это произойдет, разность делится на длину без остатка - в конце пройденного круга, т е. в начале нового. Красивое решение, жаль не хватило выдержки и захотелось подсмотреть))

[blasckad]

Проблема этого алгоритма в том что он как бы простой, но доказать что он работает не так то просто(действительно даже после объяснения кто то смог доказать что оно действительно так, судя по тому что автор не привел это доказательство, оно видимо довольно сложное), и даже если что то подобное тебе пришло в голову, ты задумаешься а действительно ли эти два указателя когда нибудь встретятся или если потом снова начать с первого элемента, придем ли мы придем в начало цикла во всех случаях, а за пол часа, когда ты еще не уверен что в принципе этот путь верный, это сделать нереально

[stivnov]

Я где-то читал, что с момента постановки задачи в 50х и до описания алгоритма Робертом Флойдом в 67 году прошло 12 лет. Более того, этот алгоритм только первая часть решения. Так что я сильно сомневаюсь, что такие вещи можно решить на интервью, только знать.

[MoDErahNLynx]

Примерно за 10 минут придумал решение за О(n^2):
1. Бежим по списку, разворачивая все ребра через которые проходим и считая, сколько вершин прошли, если уперлись в FIRST, то полученное число - оценка сверху кол-ва вершин в списке, если не уперлись в FIRST, но в null, то циклов нет.
2. Один указатель ставим на FIRST, вторым указателем бежим от первого вперед на количество шагов, равное полученной в пункте 1 оценке, если встретили первый указатель, то это начало цикла, если нет - смещаем первый указатель на 1 вершину вперед и снова бежим от него вторым указателем, повторяем до нахождения начала цикла.
3. Если нужно восстановить список к исходному виду, то просто еще раз прогоняем пункт 1.


Подумал еще 10 минут и придумал за О(n), не совпадающее с тем, что в видео:
1. Бежим одним указателелем (назовем его PILOT) от FIRST вперед, и считаем, сколько вершин прошли. Второй указатель (назовем его STONE) указывает на FIRST, и переносится на PILOT каждый раз, когда счетчик шагов PILOT равен 2^n (т.е. 2, 4, 8, 16, ...), так же при переносе STONE, запоминаем значение счетчика. На каждом шаге PILOT, проверяем, достиг ли он null, если да - циклов нет, иначе проверяем совпадает ли он со STONE, если нет, бежим дальше, если да, то цикл есть, и его длина равна разнице значения счетчика вершин, пройденных PILOT, и значения счетчика при последнем переносе STONE.
2. Опять бежим PILOT от FIRST вперед, и сзади за ним, на расстоянии длины цикла, найденной в пункте 1, синхронно бежим STONE, при каждом шаге проверяем, совпадает ли PILOT и STONE, как только совпали - они указывают на начало цикла.


Так что задачка точно не из тех, где есть строго одно решение, указанное в видео, которое неочевидно в силу нетривиальности доказательства того, что второй шаг этого решения приведет к встрече указателей в начале цикла.

[gika]

Забавно
Когда автор рассказывал решения, то я негодовал от такого "специфичного" подхода, и был приятно удивлен, что Александр так же смутился
Возможно для интервью в FAANG действительно нужно знать подобные подходы, но мне кажется можно упустить достаточно годного специалиста, только потому что он не знает такого специфичного решения. А как мне кажется его можно только знать

[vadimrumyantsev]

Зачем так сложно? Достаточно менять номер вершины на отрицательный при проходе по списку. Как наткнулись на отрицательный - это начало цикла. На втором проходе поменять минус на плюс. По-моему, Кнут или Дейкстра что-то подобное разбирал.

Это, кстати, эффективней предложенного алгоритма на несколько кругов по циклу.

[BlackDuckM]

Отличная задача! Но чтобы на нее попасть не обязательно идти в Apple. Мне такую же задачу задали на собеседовании в Avito. Причем на мобильного разработчика (которым как мы знаем алгоритмы не нужны 😁)
В общем задачу я не решил, но собес все равно прошел.
Спасибо за видео

[jogaraven]

Не знал решения, я бы просто стал красить вершины любым способом - нужен лишь один бит. Его можно взять из конца или начала указателя (т.к. в реальности указатели выравнены больше чем на 1) или из неиспользуемой части диапазона индекса (например делая их отрицательными). Ну и вернуть все вторым проходом в исходное состояние.

[alexg]

Самому придумать решение сложно. Хотя тот, кто уже готовится к собесам (читай, решает/изучает алгоритмы), скорее всего знает про технику двух указателей, и конкретно про их разновидность, когда один указатель - Заяц (быстрый), а второй - Черепаха (медленный). Задачка ооочень известная.