Эту Несложную Задачу НЕВОЗМОЖНО Решить - Собеседование в Apple
HTML-код
- Опубликовано: 8 июн 2023
- Разбираем задачу, которую дали моему знакомому на собеседовании в Apple на позицию Software Developer. При этом найти решение самому заранее не зная ответ, как мне кажется, невозможно.
Причем задача звучит очень просто, а решение пишется буквально в несколько строк кода.
Задача на LeetCode: leetcode.com/problems/linked-...
ya.cc/t/0qsU2tAQ4FaNHQ - Попробуйте себя в роли «Фронтенд-разработчика» в Яндекс Практикуме
Токен - LdtCKJPt2
---
Дисклеймер:
Изначальная задача, которую дали моему знакомому, была немного другой, но решалась с помощью этого же алгоритма.
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
А на работе в это время: "Сделайте пожалуйста эту кнопку БОЛЬШЕ"
Ага. Делаешь кнопку БОЛЬШЕ.. а не получается. ¯\_(ツ)_/¯
да, обычно так и бывает, на собесе сидят с умным видом и гоняют тебя по алгоритмам, а потом ты сидишь и красишь кнопки 🙁
Или еще хуже - "должно работать красиво" 😆😆😆
нене, это ж эпл, "сделайте эту кнопку ПЛАТНОЙ" ))
У вас очень скудное представление о работе
Это не для работников задачка, а для любителей алгоритмов. Я считаю, что многие собеседующие путают, нужен ли им сотрудник, который фанатеет по самым разным необычным алгоритмам и хитрожопым решениям, или им нужен простой усидчивый и усердный сотрудник, который не будет просирать дедлайны.
Постоянно наблюдаю примеры когда отличные усидчивые сотрудники не просирают дедлайны. Но их отличные решения требуют расширения ресурсов железа каждые полгода.
@@_iNDEX3 Это проблема не сотрудников, а проблема поставленной задачи. Уверен, что загуглить решение задачи, подобное той, что в обсуждаемом ролике - дело 2 минут. Ограничивающий фактор это не уровень интеллекта или алгоритмическая сообразительность сотрудников. Ограничивающий фактор - грамотный менеджер, ставящий правильные цели и указывающий, что в данном случае важно, а что второстепенно.
@@The14Some1 Это так не работает. Алгоритмы на собеседованиях спрашивают для того, чтобы понять, есть ли у кандидата базовые теоретические знания. На практике же "усердный" сотрудник, не владеющий базой, попав в нетривиальную ситуацию с оптимизацией производительности просто не поймет, в каком направлении копать в большинстве случаев. И я говорю сейчас только о базовых вещах - например нужно знать, какие бывают структуры данных, как они хранятся в памяти, какова сложность алгоритма, как ее посчитать, и тд.
@@2213klon Вы всерьёз считаете задачу, приведённую в данном ролике в качестве примера «базовыми теоретическими знаниями»? 99% до конца жизни доживут так ни разу и не применив этого алгоритма. Вы прочтите ещё раз одним глазком, что я в самом начале написал. Я не писал о действительно базовых вещах типа ооп, структурах данных и т.п. Я считаю и себя не глупым, и сотни других ребят, которые не знают, как решить эту задачу. В конце концов, умение справляться с такими сложностями - редкая способность, и если уж цель у проверяющего и стоит на самом деле, то не просто проверить «а знает ли кандидат вот этот алгоритм», а скорее «а входит ли кандидат в 1% эрудитов, которые сами догадаются до решения такой нетривиальной задачи за 10 минут».
Вот я к себе примеряю. Я думаю, я бы нашел решение, но мне на это понадобилось бы намного больше 10 минут. Сутки, может двое. И это нормально, я считаю. Хотя нет. На самом деле я считаю, что даже так это чуть лучше нормального :)
Вы не поверите, но в моём первом собеседовании (в 2013) именно эту задачу спросили, я решил так, как в первой части видео, а другое решение они просто объяснили и всё :)
А какая компания была?
@@AkramAzizmurodov маленькая компания в Армении, имя ничего не скажет.
@@SargsyanAndranik 👍
@@SargsyanAndranikբարև, բարև)))
@@limebro_ բարև։ Ո՞ւմ հետ պատիվ ունեմ խոսել 😄
Про доказательство второй части.
Ключевой момент -- понять, что время первой встречи М нацело делится на длину цикла С.
Почему? Медленный указатель за время M сделает M шагов, быстрый -- 2*M.
Но по предположению они должны встретиться, поэтому быстрый указатель сначала дойдёт до шага M (естествено, зайдя в цикл), а за оставшееся время навернёт ЦЕЛОЕ число кругов внутри этого цикла. Если число нецелое -- встретиться не получится.
Таким образом:
2*M = M + alpha*C
M = alpha*C
Ну а дальше просто. Возвращаем первый указатель в начало, вторым продолжаем с места встречи М, но уже с единичной скоростью. Я утверждаю, что через M шагов они снова встретятся. Первый указатель дойдёт до точки M, а второй, начав с неё, просто прокрутится целое число раз внутри цикла, ибо M = alpha*C.
Нас интересует точка начала цикла X. Т.к. наши указатели встретились, при этом двигаясь с одинаковой и единичной скоростью, то от точки начала цикла X до точки M они шли вместе. Поэтому точка первой встречи на втором прогоне и есть X.
Прокомментирую. Да, вы правы относительно М и С. А вот дальше... А если не 6, а 8? Это частное решение. А если в цикле будет нечётное число? А если будет не просто нечётное, но и простое? Да, это я о том, что С не должно быть произведение простых чисел.
А дальше? Вот мы и приехали. Это лишь тест на сообразительность. Да, вот эту задачу решить можно, а более сложную?
Мне кажется, что эта задача не для математика, а для программиста без математического(с логикой как предмет) образования. Математик тут же начнёт усложнять.
С другой стороны, может, на это и был расчёт. А как иначе проверить реальный уровень образования(образованности) и соответствия ему?
@@user-xh4cv4ei1iа сколько петабайт можно сэкономить таким образом? Чтобы хранить историю прохода нужно допустим 8 байт на элемент...
Очень интересные видео с разбором задач и алгоритмов. Ждём ролики как можно чаще!
Спасибо за видео)
Хотелось бы в дальнейшем увидеть какие-нибудь задачи с использованием графов)
Классно рассказал, спасибо огромное. Хочется побольше видео с такими разными примерами! Респект!👍
спасибо большое за информацию
История этого алгоритма берёт начало из задачи на собесе в гугле о том как найти цикл в замкнутом списке.И в 90ые годы один чело придумал (чем удивил) алгос с обходом двумя указателями, которые встретятся рано или поздно. Т.е. то, что было ВАУ тогда сейчас хотят чтобы все знали (нафига?!) по дефолту.
@@ti75425 и весь смысл в собеседованиях это поиск того избранного
В 2014 году купил первую книгу по программированию - работа мечты для программиста (дж. Монган), данная задача была описана вроде самой первой, и решение там через быстрый и медленный указатель. На самом деле задачи с хитрыми алгоритмами даются людьми которые даже не знают что она как то хитро решаются).
Решил начать литкодить недавно совсем, стал заниматься на основе leetcode beginner's guide. Там один из первых разделов как раз про связные списки. И там примерно сразу была эта задача. Ну и перед этим объяснение метода двух указателей (fast/slow pointer).
Для меня на самом деле немного удивительно, что можно не знать эту технику, если ты литкодишь/ходишь на такие собеседования) то есть как будто - это достаточно очевидный алгоритм, и типа надо сразу щёлкнуть пальцами и выдать решение)
но с другой стороны - я отучился на матмехе СПбГУ, там достаточно было проги и алгоритмов, но я тогда вряд ли бы решил эту задачу быстро) так как про fast/slow pointer никогда не видел задач.
з.ы. а какое условие у человека на собеседовании было? может всё таки немного другая задача какая-то? или не?
Отличное объяснение и решение, большое спасибо за ролик
Блин, вот зачем знать столько алгоритмов? Есть классические, а дальше надо уметь думать и составлять свои. Я считаю, что основная цель собеседования - это проверить, способен ли "думать" собеседуемый
И возможно, что чел не умел думать, поэтому не прошёл. Попросили придумать алгоритм котрый может решить не используя память. Берешь два указателя один смотрит на первый элемент, а второй бежит по списку, если указатели снова совпали, то первый элемент это начало цикла. Если второй указатель дошел до null то нет цикла. Тут ты понимаешь, что если цикл есть и начало не в первом элементе. То второй указатель не дойдет до null и с первым не встретится. значит первый надо тоже сдвигать. Дальше становится понятно, что если скорость указателей будет одинаковая, то расстояние между ними будет тоже одинаковое и они будут ходить по кругу и не узнают круг это или бесконечная прямая. тут приходит идея что скорость должна быть разная. И вот у тебя готов этот секретный алгоритм
Давай ты будешь нанимать, как сам хочешь. А другие - как они хотят. Хорошо, сорокалетний джун? Или кто ты там, мидл?
память наше все! Если ты не пишишь чистый код с минимальным коэфицентом провала, то этот код можно выкинуть в помойку, поскольку при первой нормальной нагрузке приложение упадет
@@EugeneKazatskyесть тривиальный алгоритм, не использующий доп. память. Решение аналогичное первому, 2 указателя, а проверка при совпадении узла на разности шагов до него
Так это и есть классика, описанная еще у Кнута, кажется Флойда. Магии не надо, надо знать арифметику остатков и попробовать описать движение двух указателей по модулю, равному длине цикла. Сразу получите магию, и интересный факт, что номер шага первой встречи делится на длину цикла. А есть простой алгоритм без математики, писать чуть больше, но работает вдвое быстрее
продакшн - огонь, отличная работа!
Красивое решение, обязательно попробую при случае!
Привет Саша!помнится ты в прошлом ролике по квартире в Лондоне говорил что обязательно сделаешь ролик через месяца 2-3 (если не путаю) с нетерпением жду
Я как-то раз ходил на техническое собеседование в банк. По факту собрали группу человек 6 в компьютерном классе, и дали задачу создать простого биржевого робота (что это такое мы без понятия). Время было ограничено одним часом, из которого первые 20 минут ушли на обсуждение, начинать было нельзя, даже если ты начал понимать что от тебя хотят. За оставшиеся 40 минут задачу не решил никто, даже хотя бы неправильно! А я для себя сделал вывод - что даже если пройду испытание работать здесь не буду!
Когда на собесе больше чем 1 собеседуемый это уже какое-то наебалово
Не знал решения, я бы просто стал красить вершины любым способом - нужен лишь один бит. Его можно взять из конца или начала указателя (т.к. в реальности указатели выравнены больше чем на 1) или из неиспользуемой части диапазона индекса (например делая их отрицательными). Ну и вернуть все вторым проходом в исходное состояние.
С ходу придумался такой вариант, помимо массива узлов, которые уже обходили:
При обходе списка указатель получает значение следующего узла, при этом полю next предыдущего присваиваем заведомо неправильное значение, к примеру -1, и далее переходим к следующему узлу и так далее.
В конце концов мы приходим к узлу, поле next которого содержит null - значит нет цикла, либо -1, значит это узел начала цикла.
Да, при этом мы портим список, но в условии задачи его сохранение не звучало. ))
Если я правильно понял, то нам нужно именно значение узла в ответ отдать, а не сам узел найти. Но тут непонятно, на доске когда он объяснял алгоритм ответом были цифр. А в коде ответом был сам узел. Если нужно значение узла, то такой Варик тоже не прокатит.
Качество ролика просто супер, задачка удивила!
С самого начала понял, что суть задачи именно в О(1) памяти, но так и не допер, как это сделать. Посмотрел видео, и понял, что надо иметь воображение, чтобы решить такую задачу: это как два гонщика на треке, у которых скорости отличаются в 2 раза, они будут встречаться (один опережает второго) когда остаток от деления разности пройденных путей на длину круга будет равен нулю, что произойдет не сразу, и.к. может быть линейный участок в начале, но рано или поздно произойдет. И как только это произойдет, разность делится на длину без остатка - в конце пройденного круга, т е. в начале нового. Красивое решение, жаль не хватило выдержки и захотелось подсмотреть))
Интересно🙃 Вспомнилось про инвариант в игре "пятнашки", почему-то🙄
Отличная задача! Но чтобы на нее попасть не обязательно идти в Apple. Мне такую же задачу задали на собеседовании в Avito. Причем на мобильного разработчика (которым как мы знаем алгоритмы не нужны 😁)
В общем задачу я не решил, но собес все равно прошел.
Спасибо за видео
Здравствуйте. А под какую платформу вы пишите, iOS/Android?
@@TC_IVA пишу под iOS
Интересно, откуда пошло то, что мобильному разработчику не нужны алгоритмы?)
@@geekphone1343 почти все приложения представляют собой что-то такое:
1. Получи данные с бека
2. Отобрази их в приложении
Из за этого обычно вся логика, которой требуются алгоритмы, лежит на беке. И ее не нужно отдельно писать на ios и Android
Конечно, есть ситуации, когда нужно воспользоваться знаниями алгоритмов и мобильным разработчикам, но они настолько редки, что ими можно пренебречь, особенно в самом начале карьеры
Забавно
Когда автор рассказывал решения, то я негодовал от такого "специфичного" подхода, и был приятно удивлен, что Александр так же смутился
Возможно для интервью в FAANG действительно нужно знать подобные подходы, но мне кажется можно упустить достаточно годного специалиста, только потому что он не знает такого специфичного решения. А как мне кажется его можно только знать
Просто он не попробовал подумать
В FAANG огромный поток cv и крутые зарплаты. Им тупо дешевле провести пару false-negative собесов и отсеять несколько крутых челиков, но гарантированно не взять плохих, чем взять балбеса, потратить кучу времени и денег на онбординг и по итогу его уволить как неуспевающего. Для небольших контор такой алгоритм подбора персонала - ОЧЕНЬ плохая идея
Согласен с @volervagashim. FAANG собеседования отбирают людей, которые могут дисциплинированно самостоятельно изучать материал и прокачивать навыки. Ставка на корреляция по дисциплинированности, самостоятельности и трудоспособности. Никак не связано с "умением думать".
Там есть третье тривиальное решение, удовлетворяющее требование экзаменатора.
Действительно зачем хранить перечень пройденных узлов если сами узлы есть карта. 2 указателя нужны. Один делает шаз. И запоминает число шагов. Другой добигает с начала до первого и если число шагов не сошлось выдает текущий узел
@@volervagashimну так может прежде чем тратить огромные деньги на зарплату и адаптацию, стоит потратить деньги на рекрутинг? Если человеку дали задачи решать, то он уже точно прошел через HR, прошел через первичный отбор нанимающим менеджером, и уже на этом этапе мы отсекаем «полных балбесов». Как это вообще работает и в чем экономия? Типо HR меньше часов потратит или менеджер меньше будет, а что будет, как это вообще соизмеримо с деньгами, затрачиваемыми на уже нанятых сотрудников?
И я почти уверен, что в самих FAANG это прекрасно понимают, и каждый отдел наверняка имеет свою специфику и именно под нее составлены задачи (нужно выбрать специалиста конкретного профиля), а не так, как ты описал
Зачем так сложно? Достаточно менять номер вершины на отрицательный при проходе по списку. Как наткнулись на отрицательный - это начало цикла. На втором проходе поменять минус на плюс. По-моему, Кнут или Дейкстра что-то подобное разбирал.
Это, кстати, эффективней предложенного алгоритма на несколько кругов по циклу.
Так ведь не сказано, что исходные значения - неотрицательные, сказано только что они - int :)
@@user-rw3cy9rb5jпереводи в real 😂
Первое правило алгоритмов - не мутировать исходные данные, если в задаче не сказано обратное
но ведь чтобы изменять входные данные нужно их дополнительно сохранить в память
Можно решить, храня только одно число с длинной арифметикой, но для этого все вершины должны быть пронумерованы от 1 до n. Два раза пройдём граф "переворачивая" связи при проходе, в каждом проходе мы вернёмся в начало (или null, но это тривиальный случай). После двух проходов все направления рёбер будут восстановлены. При проходе будем суммировать номера всех пройденных вершин (в число с длинной арифметикой, если то потребуется). Итоговая сумма делится пополам, и получается сумма всех номеров вершин плюс номер вершины, которую мы посетили два раза. Или может получиться просто сумма вершин, если граф это кольцо без "аппендикса".
Проблема этого алгоритма в том что он как бы простой, но доказать что он работает не так то просто(действительно даже после объяснения кто то смог доказать что оно действительно так, судя по тому что автор не привел это доказательство, оно видимо довольно сложное), и даже если что то подобное тебе пришло в голову, ты задумаешься а действительно ли эти два указателя когда нибудь встретятся или если потом снова начать с первого элемента, придем ли мы придем в начало цикла во всех случаях, а за пол часа, когда ты еще не уверен что в принципе этот путь верный, это сделать нереально
Я где-то читал, что с момента постановки задачи в 50х и до описания алгоритма Робертом Флойдом в 67 году прошло 12 лет. Более того, этот алгоритм только первая часть решения. Так что я сильно сомневаюсь, что такие вещи можно решить на интервью, только знать.
Кстати да. Одно дело найти пару рабочих примеров, а другое дело, наверное, математически доказать, что алгоритм работает для любого списка.
@@floppathebased1492 получается если длина цикла 2, а хвоста 3, то черепашка прошла ровно -1 шаг по циклу?
Ну хоть приведённое решение и лучше, но задачу можно решить и иначе. Пусть чуть хуже. Как словарь уже виденных можно использовать сам же список. С каждой итерацией проверяя его от начала и до текущего элемента.
Примерно так:
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, как только совпали - они указывают на начало цикла.
Так что задачка точно не из тех, где есть строго одно решение, указанное в видео, которое неочевидно в силу нетривиальности доказательства того, что второй шаг этого решения приведет к встрече указателей в начале цикла.
Буквально недавно на литкоде сталкивался с задачей на алгоритм флойда, но без второй части - очень коварная! Интересно было порассуждать над доказательством второй части. Все ли правильно?
Пусть 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, которая является началом цикла.
Есть более простой алгоритм, так же не требующий памяти.
Собственно, это первый алгоритм, только без выделения дополнительной памяти, т.к. вместо неё используется сам связанный список.
Пишу на псевдокоде:
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;
}
}
Хитрая задачка. Спасибо за разбор! Было бы интересно увидеть видео с подбором задач из литкода для подготовки к FAANG.
Можно сделать немного по другому, у каждого элемента что мы прошли менять ссылку на следующий элемент и делать ее саму на себя. Те прошли узел 1 - изменили ему ссылку что бы он ссылался сам на себя.
Если новый узел ссылается сам на себя - он начало цикла. Если узел ссылается на null - цикла нет.
Так кажется получается o(n) и без выделения памяти?
А можно тупо сослать первый на себя и сказать: смотрите, это начало цикла! 😆
Мне кажется, если даже не знать решение этой задачи, то можно попытаться догадаться, но времени собеседования обычно мало для таких задач. Мне почему-то эта задача напомнила другую, которую мне задавали: Есть бесконечная линия (для удобства можно просто взять условно "Ось Х"), на эту линию приземлились два парашютиста в разные точки, парашютист и парашют стоят в одной и той же точке, расстояние между ними неизвестно. Парашютисты двигаются синхронно "в цикле", как они двигаются мы задаем сами (например 2 шага влево или 3 шага вправо или шаг влево и шаг вправо и т.д., любые варианты). Если парашютист наступит на парашют (любой, свой или второй), то цикл для него можно изменить. Возможно ли сделать так, что парашютисты встретятся? Какие циклы движений необходимо задать, чтоб они встретились?
Еще пример - Пусть первый цикл будет шаг влево и шаг вправо. Они оба синхронно сделают шаг влево от парашюта и потом шаг вправо и оба встанут на парашют, сработает условие (для обоих) и можно сказать, а давайте дальше делать "5 шагов вправо" и они поскачут уже по пять шагов вправо, так же синхронно.
Так очевидная же задача, просто сначала движение влево по одному шагу, при встрече парашюта движение влево по два шага. Принцип похожий, но додуматься до этой в разы легче
@@timofeysimonov9265 не выйдет. Они идут синхронно. Если вы имеете ввиду что первый будет в цикле делать один шаг, а второй два. То синхронное выполнение означает по действию от каждого. Т.е. для первого цикл будет выполнен два раза. А для второго один. Они будут двигаться влево и расстояние между ними не будет меняться.
@@_carrot1 я имею в виду, что изначально они оба движутся влево по одному шагу, а когда правый парашютист встает на парашют левого, для него меняется алгоритм и он начинает идти по два шага, постепенно догоняя левого
@@timofeysimonov9265 нет. Так он не будет догонять. Я же говорю одно действие для каждого. В своем цикле.
@@timofeysimonov9265 если например будет для одного цикл - три шага влево. А для другого - один шаг влево. По действию за раз означает, что первый сделает один шаг, в своем цикле из трёх шагов. А для второго выполнится весь цикл в один шаг. Потом первый сделает второй шаг в своем цикле. Второй опять выполнит свой цикл в шаг. Потом первый сделает третий шаг в своем цикле и завершит его. А второй снова сделает шаг. Т.е. по действию на каждого. Синхронно. Не может сделать один два шага, а другой один шаг. Синхронно по действию.
решил эту задачу за 1 проход по списку и не выделяя памяти) но с одной оговоркой (в условиях не было: что список перестанет быть списком) проходим по нодам, и проверяем на что ссылается нода, если next == null , то конец списка, если next == nextNode, то переходим на эту ноду, а в текущей ноде next сетим на себя) теперь первая нода которая ссылается на саму себя и будет вершиной цикла, сложность О от Н, выделяем памяти 0, все условия выполнены
Самому придумать решение сложно. Хотя тот, кто уже готовится к собесам (читай, решает/изучает алгоритмы), скорее всего знает про технику двух указателей, и конкретно про их разновидность, когда один указатель - Заяц (быстрый), а второй - Черепаха (медленный). Задачка ооочень известная.
Да, но это знание не поможет решить задачу. Как додуматься до второго шага?
@@Vitek_23 да и до первого как додуматься? Почему второй должен идти в 2 раза быстрее, а не в 3, не в 4, не в 1.5...? Почему именно 1 и 2? Это ведь математически как-то должно объясняться. И после таких задачек я чувствую себя каким-то безнадежным профаном, ибо не могу додуматься до таких решений. Наверное, программист это должно быть больше чем человек, заучивший алгоритмы? Это должен быть человек, который еще и свое что-то придумывает? И решает подобные задачи не зная алгоритмов? Надеюсь я ошибаюсь
@@geekphone1343 вообще необязательно в 2 раза. например, есть алгоритм Брента, который на каждой степени двойки телепортирует медленный указатель на позицию быстрого, и работает быстрее (не асимптотически, а на практике так получается в среднем)
@@geekphone1343 В 1,5 раза - никак, список-то дискретный. В 3, 4 и т. п. раз - тоже никак, потому что если длина цикла не взаимно проста с разностью скоростей, то указатели рискуют вообще не встретиться. Возьмите, например, скорость зайца 4x от черепашьей, создайте цикл в 9 элементов и раскрасьте элементы последовательно в 3 каких-нибудь цвета (например: красный, жёлтый, зелёный, красный, жёлтый...) и подгадайте длину нециклической части так, чтобы при попадании в цикл черепаха оказалась на элементе НЕ того же цвета, что и заяц в этот же ход. Тогда каждый следующий шаг они будут синхронно менять цвета и никогда не попадут на один цвет, следовательно, никогда и не встретятся. Полагаю, что для решения задачи можно взять любые скорости, различающиеся на 1 (например, 2 и 3), но у них и реализация сложнее, и асимптотика хуже.
@@geekphone1343 В 2 удобней. За один проход медленного указателя, второй как раз пройдёт два раза все узлы (если цикл полный). Да и в других алгоритмах часто именно такой проход используется.
Заранее не зная алгоритм, за полчаса, конечно, *ооочень* трудно догадаться. В голову приходит вариант компактного хранения массива. В первую очередь хранить побитово. Но это как ни крути массив, пусть и максимально компактный. Далее, наверняка на собеседовании сказали, что нужно как-то обходиться переменными. Сразу вспомнил квадратное уравнение 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, должно получится значение вершины. Если нет, это ещё не цикл.
А что если "метить" уже пройденные узлы? Скажем множим значение на "-1" в первом прогоне пока не найдем отрицательное. Во втором множим на "-1" и возвращаем значения ячеек к исходному.
а если в узлах изначально будут отрицательные числа
@@magitrop5336по условию там номера.
Но можно и указатели метить. Например, младшим битом, используя то, что все выровненные указатели чётные. Или старшим, используя то, что 2**64 байт памяти не наберётся.
@@magitrop5336если значения могут быть отрицательными, то можно заменять их дробными значениями зеркально относительно точки. Например 1 -> 0.1; 4 -> 0.4; 10 -> 0.01; -12 -> -0.21 и так далее. Мы так можем делать по тому что не сказано где мы будем писать код в javascript все числа имеют один тип это number и поэтому в js в этом случае ошибки не будет и размерность переменной не изменится. Но остаётся проблема с 0.
Сразу подумал про rabbit / turtle указатели, но никогда бы не догадался, что можно так легко найти начало цикла!
Я придумал решение посложнее, т.к. не знал этого алгоритма, но по сложности тоже O(n). По мере прохождения, запоминаем каждый следующий элемент стоящий на месте степени двойки и сверяем с ним далее идущие, пытаясь определить зацикливание. Для примера пусть у нас цепочка из 100 элементов и на конце цикл на 40. Первый элемент сравниваем со вторым, второй с третьим и четвертым, четвертый с пятым-восьмым и т.д. 128ой элемент сравниваем с последующими и натыкаемся, что 168ой элемент равняется 128ому. В этом случае мы понимаем, что длина цикла равна 40 и 128ой элемент уже точно в цикле. Тогда мы вновь доходим сначала до 128-40=88го элемента и одновременно запускаем два курсора от 88го и 128го которые шагают по одному, каждый раз сверяя элементы. Когда элемент совпадет (по курсорам это будет 100 и 140) это и есть искомый элемент.
Эта задача была на межнаре
Точнее нужно было узнать длину цикла и длину хвоста.
Первым действием как здесь используем 2 указателя с шагом 1 и шагом 2
Вторым узнаем длину цикла прогоняя один из указателей по кругу
Третим действием используем 2 указателя с шагом 1 и форой у второго с длиной цикла
Есть очень классный видос под названием "if programming was an anime". Там разбиралась эта задача, только оттуда про неё слышал) Очень удивился, когда понял, что подобную штуку можно решить за O(1) памяти
Прикольный алгоритм, особенно не тривиально по поводу 2 шага 👍
6:20 "Магия, друзья" - офигенное объяснение! Хотя настоящее объяснение совсем несложное и интересное 🤷♂😢
Привет, можешь рассказать немного подробнее о работе в больших компаниях? А именно на каких языках там пишут код? Так как в большинстве вакансиях просто пишут а-ля 5 лет опыта разработки на одном или нескольких языках программирования.
И каково будет проходить собеседование фронтенд разработчику?
Очень интересны эти моменты так как я большую часть своей карьеры писал на React и React Native и совсем непонятно каково будет с этим бэкграундом в таких компаниях 😢
я придумал еще один супер простой способ, до которого можно додуматься, если не знаешь про быстрый и медленный указатели. оно очевидное, но работает медленно, но и не жрет памяти
так как числа уникальные, то перед конкретным числом всегда должно быть одно и тоже число, если это не начало цикла. поэтому делаем следующее
идем по графу и для каждой вершины, пытаемся опять попасть в нее с начала. когда попали, то сравниваем. если перед этой вершиной было одно и тоже число - переходим дальше. если разные - начало цикла
например
рассмотрим первый граф, мы в вершине 6, перед нами было 5
начинаем идти с начала пока не дойдем до 6, перед нами снова 5, значит переходим к рассмотрению 2
и вот тут то мы ловим начало цикла, точно так же начинаем идти с начала, пока не найдем 2, попали 2 и оказывается что перед этим было 4, а по нашей инфе у нас 6 - значит двойка начало цикла
памяти не ждет, но сложность n*n
На самом деле, можно использовать сам же список вместо выделения дополнительной памяти для хранения значений.
Внешний цикл обходит список по шагу. А на внутреннем цикле начинать обход с начала и потом сравнивать количество шагов внутреннего и внешнего цикла, за которое они достигли этого значения. Если на внутреннем цикле количество шагов меньше, чем на внешнем, то это и есть нужный нам узел. Это долгий путь.
Есть короткий, но разрушительный, как бикфордов шнур))
Обходим список пошагово с одним указателем.
На каждом шаге, прежде чем перейти на следующий узел забиваем всю переменную next пройденного узла 0xFF. И если на очередном шаге мы встретим переменную next всю заполненную 0xFF, то это и будет наш узел.
Но при этом мы разрушим весь список))
Еще можем мутировать список - изменять ссылку на следующую ноду для пройденных нод на специальное значение и если второй раз посетим такую ноду, поймем что начало списка было в ней, так получим O(n) по времени, O(1) по памяти и сломанный список после использования
у меня был вариант схлопывание в одну точку. то есть берем точку 1 она ссылается на 4. смотрим на точку 4. если она не находится то выбрасывается исключение и 4 будет наше начало. если находится то его окончание записываем в точку 1. и теперь точка 1 ссылается на точку 2. цикл повторяется. + проверка что начало и коней совпадают
В видео не обозначено условие, что исходные данные меняться не должны.
А задача на литкоде ломается ещё как минимум двумя способами:
1) Учитываем что переменные создаются последовательно(верно для этой задачи с литкода). Достаточно последовательно перебрать ноды и найти следующую, в которой адрес указателя меньше адреса указателя текущей. Будет быстрее чем алгоритм Флойда, формально все проверки прошли.
2) Джедайские техники. Выключаем стандартную синхронизацию потоков. Перехватываем буфер, получаем ответ сразу в input. Дописываем текст до подходящего по формату ответа.(не мое, можно посмотреть решение в топе по памяти)
спасибо.
2:34 поставил на паузу, решил подумать как бы я решал. Самое быстрое что надумал это пройтись по всему списку и проверить какое значение появляется повторно раньше других, сейчас досмотрю и проверю себя :D
Другое решение:
Разбиваем решение как в оригинале на 2 этапа.
2-й этап такой же как в оригинале - начинаем проход по списку из двух точек (из начала списка и из найденной точки Х в цикле на 1-м этапе) до момента их встречи.
1-й этап - другим способом находим точку Х в цикле с которой будем стартовать во втором этапе. Для этого начинаем проход по списку с целью либо найти его конец, либо гарантированно найти любую точку из цикла. Поэтому с увеличивающимся шагом периодически берем опорное значение, которое будет сравниваться со значением в текущем узле. Совпадение будет означать, что узел пройден не первый раз, а значит мы уже в цикле. Таким образом найдена случайная точка Y в цикле При этом, подсчитаем количество пройденных шагов n1 и длину цикла n2.
Искомая на 1-м этапе точка Х должна определиться из положения о том, что, начиная проход с неё и одновременно из начала списка, мы за одинаковое число шагов дойдем до точки начала цикла, т.е. дойдем одновременно. Т.е. пока мы идем из начала списка другой проход из точки X может сделать ноль или несколько кругов и оба прохода одновременно попадут в начало цикла. Т.к. оба прохода одновременно попадают в начало цикла то если их продолжить, они одновременно попадут и в точку Y (которая ранее была найдена случайно). Остаток от деления n1 на n2 (n1%n2) определит на сколько шагов надо сдвинуться из точки Y против движения и затем начать двигаться чтобы через n1 шагов попасть в точку Y. Это и будет точка Х т.к. начав двигаться из начала списка также через n1 шагов попадем в точку Y. Получается Х находится на расстоянии n1%n2 против движения или n2- n1%n2 по движению. Х будет найдена проходом по списку из точки Y на n2- n1%n2 шага.
Код:
package main
import "fmt"
type node struct{
next *node
value int
}
type list struct{
head *node
}
func main(){
nums:= []int{1,2,3,4,5}
y:= &node{nil,nums[0]}
l:= list{y}
for i:= 1; i< len(nums); i++ {
x:= &node{nil,nums[i]}
y.next = x
y = x
if i == len(nums)-1 {y.next = l.head}
}
otvet:= resh(l)
fmt.Println("otvet",otvet)
}
func resh(l list) *node {
s:= 2
n:= 0
y:= l.head
x:= y.value
for {
n= n+1
y = y.next
if y == nil {return nil}
if y.value == x {break}
if n == s {
x = y.value
s = s*2
}
}
fmt.Println("n ",n)
fmt.Println("y ",y)
n1 := n
n2 := n - s/2
//++++++++++++++++++++++++++++++++++++++
n1 = n2 - n1%n2
n = 0
y1 := y
for{
if n == n1 {break}
n = n+1
y1 = y1.next
}
y = l.head
for{
if y.value == y1.value {break}
y = y.next
y1 = y1.next
}
return y
}
Вы можете спросить. И это необходимо. Для опытного интервьюера не так важно, будет ли выполнен алгоритм. Вы всегда можете найти его в Интернете. Важно, как думает собеседник. Он Зацикливается. Или ищите решения, разные, если зашли в тупик.
Если только решение алгоритма является показателем, такого работодателя вы сразу отбрасываете. Вам не понравится работать на него.
А если к моменту прихода к циклу медленный будет отставать на Н шагов от первого? Тут надо доказать, что на любых данных первый этап приведет к тому, что запуск медленного с начала совпадет с быстрым в начале цикла.
да ну нафиг)) этот способ засел у меня в голове много лет назад и я все ждал Ну когда же пригодится
Саша, привет.
Так указатели встретились на двойке в первом примере. Для чего второй шаг? 😊
На первом шаге указатели встретились на 5
@@atterson1441 Предположим, он не отошел от предыдущего алгоритма и подумал, а почему бы не юзнуть доп память). Совместив оба алгоритма в голове, у него получилось, что если оба указателя не встретились, но проходили одну и туже вершину, то это она. Потому что один из указателей перебирает все варианты и первое совпадение равно началу цикла что вовсе не так, потому что сделав список длиннее и скажем начав цикл с 5 встреча на 2ке уже ничего бы не значила =)).
@@atterson1441 Первый раз указатели встретились именно на двойке, но сделали разное количество шагов, и мы зачем-то пошли дальше до 5, иначе алгоритм бы не сработал - подтасовка получвется, а по факту алгоритм описан не верно, нужно чтобы указатели обязательно сделали одинаковое количество шагов
Подождите, но ведь сохраненные указатели - это тоже дополнительная память)) Я вот не знал про алгоритм, и предложил бы такое решение - при попадании в ноду, удалять из нее ссылку на следующую ноду. Тогда в какой то момент мы попадаем в ноду, в которой нет ссылки на следующую ноду - и это нода начала цикла. Ну или Null, если цикла нет.
Первая встреча указательных маркеров была в вершине 2
Это же сколько дополнительных итераций, + использование памяти для 2-х указателей.
Первая мысль была конечно хешировать и проверять текущую ноду в хеше.
Про способ с 2-мя указателями я не знал и не догадался бы скорее всего.
А по хорошему при создании списка нужно было сделать счетчик элементов и тогда за O(n) получить последний элемент и от вернуть сслыку на следуюую ноду.
Или создать в списке ссылку на "хвост" и тогда за O(1) получить результат.
А если вложенным циклом: одним циклом от первой до последней точки (или пока не нашли зацикливание вершин) перебираем все вершины, где текущая итерации будет называться i. А вторым циклом (с итератором j) , вложенным в первый цикл, мы проверяем точки от первой до i-1 на совпадение вершины по идентификатору с вершиной i, выполняется ли i=j. Если зацикливание вершин будет, то оно будет в i-ой вершине, она же вершина j.
Плохой вариант? Или даже так: чем этот вариант хуже, объясните, пожалуйста.
Благодарю.
Точно такое же решение и пришло в голову. Просто заводим счётчик шагов, и для каждого шага пробегаем заново от начала списка до текущего, проверяя на совпадение. Беготни по списку много, но расход памяти - всего одна переменная. Непонятно, почему это решение хотя бы не озвучили в ролике.
@@sergeykondrashov7989 да, ждал, что озвучат и пояснят в сравнении.
Опять же. Если в объект Вершина можно дописывать данные, т.е. можно модифицировать элементы списка, я бы добавил к каждой вершине поле "просмотрено" типа boolean. Например, если получаешь выборку из БД по пользователям, которые связаны иерархически, а значит, уже работаешь с временной копией исходных данных. Да, тут как раз появляются новые хранимые данные, но это лучше, чем ничего не предложить. И всяко быстрее, если позволено менять элементы. Но если список менять нельзя, то это не вариант.
Спасибо.
Была такая на литкод, 100%.
Но никогда бы не догадался, что они встретятся в одной точке.
если не трудно, скинь номер задачи пжлста.
@@lmorozkol
Пол года назад решал, я так не вспомню(((
@@lmorozkol недавно совсем на литкоде решал тоже, даже искать долго не надо. правда там она чуть проще, надо просто сказать есть =цикл или нет, но доработать до условий из видео это уже дело техники.
141. Linked List Cycle
@@lmorozkol Linked List -> Two Pointer Technique -> Linked List Cycle II - это именно та же задача: Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null
не знаю доступна ли она по дефолту, у меня подписка куплена
скажите тут спасбио автору. В таком изложении ни один гений не догадается). По сути там две несложные теоремки, причем автор назвал только вторую, но до нее без первой не догадаться вообще. Первая "магия": указатели встречаются в первый раз на шаге, номер которого кратен длине цикла. Мне было без алгебры не очевидно ни разу.
Товарищ, который очень хорошо знает алгоритмы так отреагировал:
«Прикольно. Спустя 7 лет)»
Как я понял ему это давали в Гугл 7 лет назад))
мне такое(метод двух указателей) в голову не пришло.. думал как-то так: проходимся в цикле по узлам и для каждого узла проверяем во внутреннем цикле содержат ли следующие узлы такое же значение,ну и если да возращаем это значение.Скорость O(n^2) и вроде бы без доп памяти
В принципе на LeetCode есть очень похожая задача, но там проще, там нужно было просто обнаружить цикличность. Как раз вторым решением она решалась.
Попадалась подобная задача на литкоде (287). Но в замаскированном виде. Там вообще одномерный массив и нужно еще догадаться, что можно представить его в виде списка и искать в нем точку входа в цикл. Хотя, конечно, можно и без этого просто бинарным поиском, но это не так красиво
Не знаю было ли где-то объяснение, я придумал такое.
Представим, что у нас есть цилиндрическая палка и верёвка переменной длины, типа резинка. Если будем наматывать верёвку на палку, так чтоб оба её конца оказались в одной точке(на одной линии). То некоторая "середина" верёвки тоже будет на той же линии, если количество петель чётное, или на строго противоположной стороне, если не чётное. Другими словами, если один из концов верёвки встретился с её серединой, то и второй конец верёвки обязательно будет на той же линии.
Это объясняет почему в третьем примере указатели сразу встретились в начале цикла.
Усложняя задачу, мы можем фиксировать верёвку на цилиндре гвоздиками, а концы верёвки останутся свисать. Тогда чтоб оба гвоздика и середина верёвки были на одной линии, свисающие концы должны быть равны. Отсюда последнее действие с возвратом в начало списка и поиском начала цикла.
для приличия стоило написать, почему верен второй шаг, вряд ли в нормальную компанию возьмут человека, который не может доказать корректность алгоритма). Пусть х - длина списка до начала цикла, l - длина цикла, тогда первый прошел n = x + kl + a шагов (a < l). Второй прошел 2n = x + ml + a шагов (тоже а, так как они встретились). Подставим вместо n правую часть выражения для первого указателя: 2x + 2kl + 2a = x + ml + a, откуда находим x = (m - 2k)l - a. Осталось заметить, что m > 2k. Таким образом, если применить второй шаг, то указатель с позиции встречи пройдет l-a + несколько циклов, что и требовалось, и место встречи будет точно в начале цикла
Читаю комментарии и офигиваю. 95% не видят разницы между задачами "Поиск цикла в графе" и "Поиск начала цикла".
Решение (и доказательство корректности) действительно весёлое, даже если знаешь про метод slow-fast pointers, ибо он без модификаций позволяет определить только наличие цикла, но не его начало.
Хм, замчем мне тогда устраиваться в гугл, если там так мало платят что приходится пихать рекламу яндекс практикума? 🤔
Эту задачу можно привести к поиску Strongly Connected Components. Решается 2 прогонами DFS, O(N+M)
В курсе по алгоритмам на Leetcode есть эта задача и пояснение как решать ее через два указателя :)
Я не знаю как, но буквально полчаса назад я наткнулся именно на эту задачу на литкод, тоже не знал как решить, и в рекомендациях нахожу это видео.
Если Бога нет, то что это? 😂😂
@@pz8916 Это cookies и глобальная слежка от гугловодов
@@vladkv2002 🤣🤣🤣
@@pz8916 рекомендательные алгоритмы ютуба, может быть?
У меня есть свое решение. Присваивать на каждом шаге указателю на следующий элемент значение (0). Таким образом, после попадания в цикл, в вершине уже в след будет 0. Предварительно надо пробежать по цепочке, проверить, нет ли там базового (0). Умники, которые будут писать про (memory leak) идут лесом, ибо в условии об этом ничего не было.
Пробежаться не получится, т.к. ты не поймёшь, идёшь ли ты по новым элементам, или уже зациклился.
Остаётся лишь цепляться за формулировку " все элементы уникальны, от 1 до N"
"математик сделает лучше" с Савватеевым разбирали эту задачу. Найти решение можно просто, если ты олимпиадник. Если в компанию нужны олимпиадники, то хорошая задача
Лайк, только тайм коды добавьте пожалуйста 😊
В моей текущей компании подобную задачу тоже ранее давали на собеседовании. Правда начиналось все с простой логической задачи: Два велосипедиста выезжают на трек, нужно определить является ли он цикличным или же прямым. Как нужно двигаться велосипедистам, что бы определить это. А дальше после решения этой задачи давали описываемую в видео. И нет никаких проблем с пониманием решения, на собеседовании цель понять как мыслит человек, а не то как много алгоритмов он смог вместить в свою голову
Вот еще вариант другой есть. У нас есть список, значит число элементов знаем. Дальше идем по списку банально считая шаги, как только число шагов превысило число элементов - мы пришли в начало цикла, возвращаем текущий элемент, если же очередной next вернул null - значит и цикла нет - null и на выход.
Знал решение, потому что 24 года назад на 1м курсе института при изучении Теории графов в Дискретной математике изучали кучу подобных задач. Конкретно эту задачу вытянул на экзамене.
Круто, за 24 года подобный алгоритм пригодился? (без сарказма)
@@dionisll Уверен на 100%, как и в других областях наук (я - физик - математик), за институт ты учишь "базу", успешно забывая её после сессии (как тебе кажется), а через 10 лет мгновенно даешь ответ на внезапный вопрос из курса.
Как в шахматах, можешь готовить дебютный вариант с 10-15 возможными продолжениями, а сыгран будет лишь 1 и не факт, что из тех, которые ты подготовил.
@@dionisll на собеседовании и пригодятся университетские знания, но это если знания были :)
@@alexanderpoplooukhin7448 ага, так за универ топите, а половина комментов говорит, что такие задачи есть в литкоде в топе 50 задач которых нужно решить. Я только спросли, где конкретно пригодился этот алгоритм и все. А то, что уневер дает тонну бесполезных знаний, так это и все без вас знают.
@@dionisll если университетские знания пригодятся для прохождения собеса в бигтех, то значит не такие уж и бесполезные знания дают в университете. Если вас интересует прикладной вопрос применения этого алгоритма, то определение цикла в пути, определение цикличных ссылок, определение дедлоков.
P.S. Алгоритм определения дедлоков я реализовывал только на лабораторке в универе.
Вообще-то это очень популярная задача в программировании. Да даже если тот же Dependency Injection вспомнить: нахождение циклических зависимостей. Но никто не запаривается с экономией памяти таким образом. Ведь можно просто пройтись по дереву связей и проиндексировать ветки. Если следующий шаг по цепочке попадает не в развилку и в ветвь отличную от текущей, значит мы нашли достаточный признак зацикливания. Дальше в зависимости от правил ветвления связанного списка можно дошагать и до начала цикла. Но обычно это не требуется. Чаще всего на этом алгоритм уже и заканчивается, так как ищут обычно не начало цикла, а первый элемент, который уперся в уже пройденный. Так что вообще можно было просто в списке булевы значения проставить - пройдено/не пройдено. А экономия памяти как в примере у автора необходима только в железе. Но там и связанных списков нет. Хотя, возможно в нейросетях такой алгоритм, как у автора, пригодился бы при условии, что связанные списки почти бескрайние. Однако надо понимать, что в алгоритмах частенько экономия памяти заставляет делать больше операций. Так что еще не известно что именно лучше экономить - память или процессорное время.
Большое спасибо предмету "Алгоритмы структуры даных" в универе. Один раз выучил, и забыл) Но когда надо вспомнить, то очень полезно
Вариант для изменяемых данных с изначально положительными индексами:
Первая проходка по листу - умножаешь позитивные индексы на -1
Вторая проходка по листу - умножаешь негативные индексы на -1, позитивный (корень листа) возвращаешь
O(n), с одним указателем
Только придется хранить первичную проходку... на экономию памяти не похоже. А похоже на экономию времени.
@@101picofarad так меняешь индексы на входной памяти прямо
Даже без двух указателей простое решение есть. Считая сколько сделано шагов до текущего узла от первого узла (пусть N), легко узнать находясь в текущем узле, проходим ли мы его первый раз, или нет. Можно посчитать число шагов от первого узла до первого попадания в текущий, пусть это будет M. Если M меньше N, то это уже цикл.
Хм, пока ещё не начал смотреть видео, и я предполагаю, что задача на превью - это не та задача, а просто для превьюшки прикол, но для задачи с превью ответ, очевидно - 2, а формула перехода: 4-(3-i)%4
1 а сохранять укзатели это не дополнительная память?
2 что мешало сохранить индексы (ссылки/указатели) в 1 варианте?
Придумал другое решение. Создаем новый элемент списка, на него будет указывать каждый элемент который мы уже прошли (при переходе на next меняем указатель next у предыдущего на новый). Как только мы опять на него наткнёмся, то возвращаем значение элемента стоящего перед ним. Но этот способ разрушает исходный граф.
А когда вам на это укажут, нужно сделать круглые глаза и сказать "а в задании не было условия о сохранении исходного графа"
Да, только потом попросят решить с сохранением графа
Хороший способ, только почему мы возвращаем значение элемента "перед ним"? Вроде нужно вернуть значение того элемента, на который и наткнулись. А в качестве доп. элемента просто любой Object создать, на него всё и ссылать.
И да, интересно, какого это потом все задачи на работе решать методом разрушения? 😀
@@Vitek_23 возвращаем значение элемента "перед ним", потому что он - "любой Object", а нам надо значение с которого начинается цикл.
Попадалась эта задача на литкоде, я полностью согласен, что такого плана нельзя спрашивать на собеседовании, но сразу как услышал задачу вспомнил решения.
Мне тоже показалась она "магией" в каком-то смысле
да, там еще классное мат доказательство есть почему именно такой алгоритм
На такие задачи надо спрашивать: а давно ли ты применял что-то подобное на практике?
Собеседование на работу же, а не в сборную по спортивному программированию
И что это поменяет? Ну типа ты его под*бешь, потешишь свое его но совбес не пройдешь моментально после такого вопроса, даже если он для приличия и вежливости задаст еще парочку. В целом более эффектно будет просто молча встать и уйти после такого вопроса если считаешь его рагульским чем вступать в стендап полемику.
На самом деле частенько приходится применять олимпиадные семитские трюки из теории графов, динамического программирования и т.п. в работе, не каждый день, но раз в пару месяцев - точно. Из последнего - писал анализатор OpenAPI спек, куча всего из теории графов пригодилось.
Ура, я догадался:)
Ну я после минут 5 размышлений заметил что в этом связаном списке если есть 4 то должны быть и 3, и 2, и1, и тоже самое со всеми числами, тоесть можно проходясь по списку записывать максимальный элемент и смотреть, если кол-во проходов больше чем максимальный элемент то это и есть начало цикла, тут, в этом алгоритме, память O(1)
Но это как оказалось не то решение которое нужно было
Привет, а почему нельзя использовать ту же память что уже выделана под список, меняя указатель только что пройденного элемента на самого себя? Если встретишь элемент ссылающийся сам на себя, то это и есть начало цикла.
Будет найдено начало несуществующего цикла.
Блин, когда решение сказал, я вспомнил, что такое было в универе) я придумал другое решение, правда менее эффективное: идём один узел за одним и на каждом узле делаем следующее: разворачиваемся список назад, т.е. узел начинает смотреть не на следующего, а на предидущего. На каждом узле идём назад до конца, если нашли на обратном пути текущий узел, то он является вершиной петли. В условии задачи ничего не было сказано, что список нельзя менять)
Вот ещё лучшее и понятное решение.
Заводим 2 указателя.
Они двигаются с шагом 1 но один всегда на 1дну позицию опережает второго. На каждом шаге рассчитываем длину от начала списка до указателей.
Если зацикливания нет то длинна до первого от начала будет всегда больше длины второго
И если зацикливание есть то в какой-то момент длина от начала до опережающего станет меньше чем длина от начала до отстающего.
Все. Мы нашли начало цикла. Т.е длина тут до опережающего и будет указатель на начало цикла
За 20-30 минут задачку конечно не решить, если не знаешь как. Но до такой же идеи я догадался сам при решении похожей задачи. Правда это не было собеседование - просто решал задачки и это заняло у меня несколько часов обдумывания в спокойной обстановке.
Не совсем понимаю, а что значит, нк использую дополнительную память? Указатели как бы тоже сохраняют адрес объекта, на который ссылаются.
Интересная задачка) У меня появилось пару мыслей, я и не понимаю где косяк в моей логике. Если у нас есть цикл, то он очевидно только в конце. Смотрим последнюю вершину, если она ссылается на null, то цикла нет, НО если она куда то ссылается, то она может ссылаться только на начало цикла, разве нет?
Что такое "последняя вершина"?
@@vladimirilyin3892 вершина с последним индексом
А можно ли просто проходя по элементам такого списка, удалять их/присваивать им мусорные значение по мере прохода, и соответственно, когда мы дойдём до начала цикла, мы увидим, что там погода или же элемента не существует. Или сам список менять нельзя?
По сути, использование указателей - это тоже доп память, но решение интересное