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

Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin

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

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

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

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

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

Спасибо за видео) Хотелось бы в дальнейшем увидеть какие-нибудь задачи с использованием графов)

Классно рассказал, спасибо огромное. Хочется побольше видео с такими разными примерами! Респект!👍

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

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

Отличное объяснение и решение, большое спасибо за ролик

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

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

спасибо большое за информацию

Решил начать литкодить недавно совсем, стал заниматься на основе leetcode beginner's guide. Там один из первых разделов как раз про связные списки. И там примерно сразу была эта задача. Ну и перед этим объяснение метода двух указателей (fast/slow pointer). Для меня на самом деле немного удивительно, что можно не знать эту технику, если ты литкодишь/ходишь на такие собеседования) то есть как будто - это достаточно очевидный алгоритм, и типа надо сразу щёлкнуть пальцами и выдать решение) но с другой стороны - я отучился на матмехе СПбГУ, там достаточно было проги и алгоритмов, но я тогда вряд ли бы решил эту задачу быстро) так как про fast/slow pointer никогда не видел задач. з.ы. а какое условие у человека на собеседовании было? может всё таки немного другая задача какая-то? или не?

Качество ролика просто супер, задачка удивила!

Привет Саша!помнится ты в прошлом ролике по квартире в Лондоне говорил что обязательно сделаешь ролик через месяца 2-3 (если не путаю) с нетерпением жду

продакшн - огонь, отличная работа!

Красивое решение, обязательно попробую при случае!

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

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

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

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

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

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

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

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

Можно сделать немного по другому, у каждого элемента что мы прошли менять ссылку на следующий элемент и делать ее саму на себя. Те прошли узел 1 - изменили ему ссылку что бы он ссылался сам на себя. Если новый узел ссылается сам на себя - он начало цикла. Если узел ссылается на null - цикла нет. Так кажется получается o(n) и без выделения памяти?

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

Сразу подумал про rabbit / turtle указатели, но никогда бы не догадался, что можно так легко найти начало цикла!

А что если "метить" уже пройденные узлы? Скажем множим значение на "-1" в первом прогоне пока не найдем отрицательное. Во втором множим на "-1" и возвращаем значения ячеек к исходному.

Интересно🙃 Вспомнилось про инвариант в игре "пятнашки", почему-то🙄

6:20 "Магия, друзья" - офигенное объяснение! Хотя настоящее объяснение совсем несложное и интересное 🤷‍♂😢

Пушка, спасибо! Жаль фантазии не хватило докрутить самостоятельно этот пример)

У меня есть свое решение. Присваивать на каждом шаге указателю на следующий элемент значение (0). Таким образом, после попадания в цикл, в вершине уже в след будет 0. Предварительно надо пробежать по цепочке, проверить, нет ли там базового (0). Умники, которые будут писать про (memory leak) идут лесом, ибо в условии об этом ничего не было.

Хитрая задачка. Спасибо за разбор! Было бы интересно увидеть видео с подбором задач из литкода для подготовки к FAANG.

Ну хоть приведённое решение и лучше, но задачу можно решить и иначе. Пусть чуть хуже. Как словарь уже виденных можно использовать сам же список. С каждой итерацией проверяя его от начала и до текущего элемента. Примерно так: List findLoop(list) { int index = 0; for (var curr = list; curr != null; curr = curr.next) { if (contains(list, curr, index++)) { return curr; } } return null; } bool contains(list, searched, limit) { for (var curr = list; curr != null && --limit > 0; curr = curr.next) { if (curr.equals(searched)) { return true; } } return false; }

Примерно за 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, как только совпали - они указывают на начало цикла. Так что задачка точно не из тех, где есть строго одно решение, указанное в видео, которое неочевидно в силу нетривиальности доказательства того, что второй шаг этого решения приведет к встрече указателей в начале цикла.

Спасибо. Была такая на литкод, 100%. Но никогда бы не догадался, что они встретятся в одной точке.

А если вложенным циклом: одним циклом от первой до последней точки (или пока не нашли зацикливание вершин) перебираем все вершины, где текущая итерации будет называться i. А вторым циклом (с итератором j) , вложенным в первый цикл, мы проверяем точки от первой до i-1 на совпадение вершины по идентификатору с вершиной i, выполняется ли i=j. Если зацикливание вершин будет, то оно будет в i-ой вершине, она же вершина j. Плохой вариант? Или даже так: чем этот вариант хуже, объясните, пожалуйста. Благодарю.

Привет, можешь рассказать немного подробнее о работе в больших компаниях? А именно на каких языках там пишут код? Так как в большинстве вакансиях просто пишут а-ля 5 лет опыта разработки на одном или нескольких языках программирования. И каково будет проходить собеседование фронтенд разработчику? Очень интересны эти моменты так как я большую часть своей карьеры писал на React и React Native и совсем непонятно каково будет с этим бэкграундом в таких компаниях 😢

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

Прикольный алгоритм, особенно не тривиально по поводу 2 шага 👍

А если к моменту прихода к циклу медленный будет отставать на Н шагов от первого? Тут надо доказать, что на любых данных первый этап приведет к тому, что запуск медленного с начала совпадет с быстрым в начале цикла.

Есть более простой алгоритм, так же не требующий памяти. Собственно, это первый алгоритм, только без выделения дополнительной памяти, т.к. вместо неё используется сам связанный список. Пишу на псевдокоде: VertexFirst = первая вершина; vertexCheck = vertexFirst->next; с=1; while(vertexCheck != NULL) { Проверка_зацикливания(); c++; vertexCheck = vertexCheck->next; } Подпрограмма Проверка_зацикливания { vertexCur = vertexFirst; i=c; while(i>0){ i--; if(vertexCur == vertexCheck){ Вывести_вершину; } vertexCur = vertexCur->next; } }

Можно решить, храня только одно число с длинной арифметикой, но для этого все вершины должны быть пронумерованы от 1 до n. Два раза пройдём граф "переворачивая" связи при проходе, в каждом проходе мы вернёмся в начало (или null, но это тривиальный случай). После двух проходов все направления рёбер будут восстановлены. При проходе будем суммировать номера всех пройденных вершин (в число с длинной арифметикой, если то потребуется). Итоговая сумма делится пополам, и получается сумма всех номеров вершин плюс номер вершины, которую мы посетили два раза. Или может получиться просто сумма вершин, если граф это кольцо без "аппендикса".

Есть очень классный видос под названием "if programming was an anime". Там разбиралась эта задача, только оттуда про неё слышал) Очень удивился, когда понял, что подобную штуку можно решить за O(1) памяти

Хм, замчем мне тогда устраиваться в гугл, если там так мало платят что приходится пихать рекламу яндекс практикума? 🤔

Товарищ, который очень хорошо знает алгоритмы так отреагировал: «Прикольно. Спустя 7 лет)» Как я понял ему это давали в Гугл 7 лет назад))

Эта задача была на межнаре Точнее нужно было узнать длину цикла и длину хвоста. Первым действием как здесь используем 2 указателя с шагом 1 и шагом 2 Вторым узнаем длину цикла прогоняя один из указателей по кругу Третим действием используем 2 указателя с шагом 1 и форой у второго с длиной цикла

1 а сохранять укзатели это не дополнительная память? 2 что мешало сохранить индексы (ссылки/указатели) в 1 варианте?

Вы можете спросить. И это необходимо. Для опытного интервьюера не так важно, будет ли выполнен алгоритм. Вы всегда можете найти его в Интернете. Важно, как думает собеседник. Он Зацикливается. Или ищите решения, разные, если зашли в тупик. Если только решение алгоритма является показателем, такого работодателя вы сразу отбрасываете. Вам не понравится работать на него.

Мне кажется, если даже не знать решение этой задачи, то можно попытаться догадаться, но времени собеседования обычно мало для таких задач. Мне почему-то эта задача напомнила другую, которую мне задавали: Есть бесконечная линия (для удобства можно просто взять условно "Ось Х"), на эту линию приземлились два парашютиста в разные точки, парашютист и парашют стоят в одной и той же точке, расстояние между ними неизвестно. Парашютисты двигаются синхронно "в цикле", как они двигаются мы задаем сами (например 2 шага влево или 3 шага вправо или шаг влево и шаг вправо и т.д., любые варианты). Если парашютист наступит на парашют (любой, свой или второй), то цикл для него можно изменить. Возможно ли сделать так, что парашютисты встретятся? Какие циклы движений необходимо задать, чтоб они встретились? Еще пример - Пусть первый цикл будет шаг влево и шаг вправо. Они оба синхронно сделают шаг влево от парашюта и потом шаг вправо и оба встанут на парашют, сработает условие (для обоих) и можно сказать, а давайте дальше делать "5 шагов вправо" и они поскачут уже по пять шагов вправо, так же синхронно.

2:34 поставил на паузу, решил подумать как бы я решал. Самое быстрое что надумал это пройтись по всему списку и проверить какое значение появляется повторно раньше других, сейчас досмотрю и проверю себя :D

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

Знал решение, потому что 24 года назад на 1м курсе института при изучении Теории графов в Дискретной математике изучали кучу подобных задач. Конкретно эту задачу вытянул на экзамене.

Буквально недавно на литкоде сталкивался с задачей на алгоритм флойда, но без второй части - очень коварная! Интересно было порассуждать над доказательством второй части. Все ли правильно? Пусть N - количество узлов в списке, M - количество узлов от начала списка до начала цикла, L - длина цикла, а K - число узлов между началом цикла и точкой первой встречи указателей. На момент встречи "быстрый" указатель пройдет M + n * L + K шагов (n - целое количество полностью пройденных циклов). "Медленный" указатель пройдет M + K шагов. Поскольку "быстрый" указатель двигается вдвое быстрее, то верно следующее уравнение: 2 * (M + K) = M + n * L + K M = n * L - K Что в буквальном смысле означает, что, если "медленный" указатель пройдет M шагов от начала списка, а "быстрый" указатель пройдет те же M шагов от (n * L - K) узла с единичной скоростью (напомню, что (n * L - K) = M) => оба указателя встретятся в точке M, которая является началом цикла.

Саша, привет. Так указатели встретились на двойке в первом примере. Для чего второй шаг? 😊

Читаю комментарии и офигиваю. 95% не видят разницы между задачами "Поиск цикла в графе" и "Поиск начала цикла". Решение (и доказательство корректности) действительно весёлое, даже если знаешь про метод slow-fast pointers, ибо он без модификаций позволяет определить только наличие цикла, но не его начало.

1:52 что значит «Вот такая задача»? Задача не такая, как выяснилось. Почему же ты не сказал сразу, что нельзя использовать доп-память?

Большое спасибо предмету "Алгоритмы структуры даных" в универе. Один раз выучил, и забыл) Но когда надо вспомнить, то очень полезно

у меня был вариант схлопывание в одну точку. то есть берем точку 1 она ссылается на 4. смотрим на точку 4. если она не находится то выбрасывается исключение и 4 будет наше начало. если находится то его окончание записываем в точку 1. и теперь точка 1 ссылается на точку 2. цикл повторяется. + проверка что начало и коней совпадают

я придумал еще один супер простой способ, до которого можно додуматься, если не знаешь про быстрый и медленный указатели. оно очевидное, но работает медленно, но и не жрет памяти так как числа уникальные, то перед конкретным числом всегда должно быть одно и тоже число, если это не начало цикла. поэтому делаем следующее идем по графу и для каждой вершины, пытаемся опять попасть в нее с начала. когда попали, то сравниваем. если перед этой вершиной было одно и тоже число - переходим дальше. если разные - начало цикла например рассмотрим первый граф, мы в вершине 6, перед нами было 5 начинаем идти с начала пока не дойдем до 6, перед нами снова 5, значит переходим к рассмотрению 2 и вот тут то мы ловим начало цикла, точно так же начинаем идти с начала, пока не найдем 2, попали 2 и оказывается что перед этим было 4, а по нашей инфе у нас 6 - значит двойка начало цикла памяти не ждет, но сложность n*n

А можно ли просто проходя по элементам такого списка, удалять их/присваивать им мусорные значение по мере прохода, и соответственно, когда мы дойдём до начала цикла, мы увидим, что там погода или же элемента не существует. Или сам список менять нельзя?

"математик сделает лучше" с Савватеевым разбирали эту задачу. Найти решение можно просто, если ты олимпиадник. Если в компанию нужны олимпиадники, то хорошая задача

Заранее не зная алгоритм, за полчаса, конечно, *ооочень* трудно догадаться. В голову приходит вариант компактного хранения массива. В первую очередь хранить побитово. Но это как ни крути массив, пусть и максимально компактный. Далее, наверняка на собеседовании сказали, что нужно как-то обходиться переменными. Сразу вспомнил квадратное уравнение x^2+bx+c=0. Тогда x1+x2=-b, x1*x2=c. Пусть в первой переменной хранится произведение значений в вершинах. Во второй сумма делителей этих значений. Для 3-го примера v1=1*3*4*2=24, v2=1+3+(2+2)+2=10. При подходе к очередной вершине, получаем значение и на него делим v1. Если делится нацело, то находим из остатка все его делители и суммируем, а дальше вычитаем из v2, должно получится значение вершины. Если нет, это ещё не цикл.

Попадалась эта задача на литкоде, я полностью согласен, что такого плана нельзя спрашивать на собеседовании, но сразу как услышал задачу вспомнил решения. Мне тоже показалась она "магией" в каком-то смысле

Лайк, только тайм коды добавьте пожалуйста 😊

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

Хм, пока ещё не начал смотреть видео, и я предполагаю, что задача на превью - это не та задача, а просто для превьюшки прикол, но для задачи с превью ответ, очевидно - 2, а формула перехода: 4-(3-i)%4

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

В принципе на LeetCode есть очень похожая задача, но там проще, там нужно было просто обнаружить цикличность. Как раз вторым решением она решалась.

Вариант для изменяемых данных с изначально положительными индексами: Первая проходка по листу - умножаешь позитивные индексы на -1 Вторая проходка по листу - умножаешь негативные индексы на -1, позитивный (корень листа) возвращаешь O(n), с одним указателем

Интересная задачка) У меня появилось пару мыслей, я и не понимаю где косяк в моей логике. Если у нас есть цикл, то он очевидно только в конце. Смотрим последнюю вершину, если она ссылается на null, то цикла нет, НО если она куда то ссылается, то она может ссылаться только на начало цикла, разве нет?

Жаль не объяснил с точки зрения математики, откуда появляется магия того, что во втором цикле попадаем в вершину цикла. Почему не может получится ситуации, когда два указателя будут бегать по циклу, типа первый в 3, а второй в 6; первый в 5, второй в 2 и т.д.

На такие задачи надо спрашивать: а давно ли ты применял что-то подобное на практике? Собеседование на работу же, а не в сборную по спортивному программированию

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

Не совсем понимаю, а что значит, нк использую дополнительную память? Указатели как бы тоже сохраняют адрес объекта, на который ссылаются.

Я придумал решение посложнее, т.к. не знал этого алгоритма, но по сложности тоже O(n). По мере прохождения, запоминаем каждый следующий элемент стоящий на месте степени двойки и сверяем с ним далее идущие, пытаясь определить зацикливание. Для примера пусть у нас цепочка из 100 элементов и на конце цикл на 40. Первый элемент сравниваем со вторым, второй с третьим и четвертым, четвертый с пятым-восьмым и т.д. 128ой элемент сравниваем с последующими и натыкаемся, что 168ой элемент равняется 128ому. В этом случае мы понимаем, что длина цикла равна 40 и 128ой элемент уже точно в цикле. Тогда мы вновь доходим сначала до 128-40=88го элемента и одновременно запускаем два курсора от 88го и 128го которые шагают по одному, каждый раз сверяя элементы. Когда элемент совпадет (по курсорам это будет 100 и 140) это и есть искомый элемент.

Блин, когда решение сказал, я вспомнил, что такое было в универе) я придумал другое решение, правда менее эффективное: идём один узел за одним и на каждом узле делаем следующее: разворачиваемся список назад, т.е. узел начинает смотреть не на следующего, а на предидущего. На каждом узле идём назад до конца, если нашли на обратном пути текущий узел, то он является вершиной петли. В условии задачи ничего не было сказано, что список нельзя менять)

да ну нафиг)) этот способ засел у меня в голове много лет назад и я все ждал Ну когда же пригодится

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

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

Не сразу, но покумекав 10 минут вспомнил, что применяется такая методика где есть зацикливания, ну а потом через ещё 5 минут заметив что не всё так просто начал "жонглировать" чем имеется до победного

Может я не до конца понимаю задачу, но я добавил бы просто 1 переменную - длинна списка. И проходился бы по листу пока не получу нужное число или null. Поправьте меня если не прав.

Я бы сделал немного по-другому. Я добавил бы числовую метку к каждой вершине, после ее посещения. Вроде, значение было 4, стало 4.12345 или любое int значение, которое навряд ли можно случайно встретить. Затем шагал бы по списку, пока не встретил числовую метку.

А нельзя было просто типо для каждого числа обойти все числа, если повторится, то ответ это число, если нет переходим к следующему числу. Такое решение очень легко придумать, но оно долгое(или возможно так нельзя решать?)

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

Это же сколько дополнительных итераций, + использование памяти для 2-х указателей. Первая мысль была конечно хешировать и проверять текущую ноду в хеше. Про способ с 2-мя указателями я не знал и не догадался бы скорее всего. А по хорошему при создании списка нужно было сделать счетчик элементов и тогда за O(n) получить последний элемент и от вернуть сслыку на следуюую ноду. Или создать в списке ссылку на "хвост" и тогда за O(1) получить результат.

А какое практическое применение этого алгоритма?

Первая встреча указательных маркеров была в вершине 2

Даже без двух указателей простое решение есть. Считая сколько сделано шагов до текущего узла от первого узла (пусть N), легко узнать находясь в текущем узле, проходим ли мы его первый раз, или нет. Можно посчитать число шагов от первого узла до первого попадания в текущий, пусть это будет M. Если M меньше N, то это уже цикл.

Придумал другое решение. Создаем новый элемент списка, на него будет указывать каждый элемент который мы уже прошли (при переходе на next меняем указатель next у предыдущего на новый). Как только мы опять на него наткнёмся, то возвращаем значение элемента стоящего перед ним. Но этот способ разрушает исходный граф.

Ну хорошо бы пояснить за алгоритм и почему он будет работать, а не посто на 2 примерах

Строго говоря условие "не используя дополнительную память" не соблюдается уже в момент заведения дополнительного указателя.

Но даже прохождение технического интервью с достижением 100%-го результата, включая реализацию подобного алгоритма не гарантирует получение оффера. Просто в конце вам очень вероятно скажут "Спасибо за уделенное время, но мы наняли другого кандидата. Обязательно оставим ваш профиль в нашей базе, следите за вакансиями на нашем сайте и не стесняйтесь подаваться снова. Удачи в поиске". Никакого другого фидбэка не получите.

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

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

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

По сути, использование указателей - это тоже доп память, но решение интересное