Комментарии 147
А если там unsigned int?
Очевидно, надо уточнять условия задачи при её постановке. Но в целом место для лишнего битика мы обычно можем найти, если не в номере ноды, то в указателе.
В любом случае адресуемая память не может вместить столько узлов нашей структуры, сколько возможно адресов. Поэтому место всегда есть.
Правда, баловство с указателями трудноисполнимо в системах программирования со сборщиком мусора.
Но в целом место для лишнего битика мы обычно можем найти, если не в номере ноды, то в указателе.
Это если мы чётко знаем, что какие то биты виртуального адреса не используются. А то может оказаться, что памяти выделено меньше, но мапится на разбросанные диапазоны с разными битовыми сочетаниями.
Но я бы скорее о многопотоковости задумался, мало ли кто кроме нас по этому списку ходит...
Вопрос даже не в том, есть ли место. Вопрос — не занято ли место? Если номер узла уникальный и не обязательно в порядке узлов, то неизвестно, не встретится ли отрицательный номер в нормальной немаркированной нумерации. Это ведь тоже в условии не запрещено. Возможны ложные срабатывания.
И вообще, насчет маркировки с изменением имеющихся данных. В синтетических задачах на голые алгоритмы этот финт ушами выглядит изящно и показывает нестандартность мышления. В реальности имеющиеся в нодах данные могут использоваться кем-то еще в параллельном потоке или по прерываниям, а мы тут их портим внезапно...
В реальности я бы запользовал хеш таблицу, а дальше смотрел, насколько проблемно выделение дополнительной памяти на реальных данных.
Допустим, хеш совпал. Что это нам даёт?
Это ведь может быть и случайное совпадение.
Под хешом имелся в виду std::unordered_map, оно коллизии само обработает.
Допустим, хеш совпал. Что это нам даёт?
Не знаю как у вас в сишечке, а у нас в жаве, если хэш коды совпадают, ноды в HashMap (в нашем случае в HashSet, но неважно) попадают в один бакет, и там хранятся в виде списка или дерева. При доставании ноды с одним хэш кодом сравниваются методом equals. Есть реализация хэш структур со сдвигом, open addressing, так называемый. Там в случае коллизии просто ищется свободный слот.
В реальной жизни в Java я бы тоже применил хэшсет. Не говоря уж о том, что менять на лету айди (а этот инт в узле это именно айди) на отрицательный и обратно так себе идея и, обычно, просто невозможно.
Устройство HashMap это, кстати, любимый вопрос на собеседованиях по Java. Просто всегда задают. Ну, по крайней мере, раньше спрашивали.
Алгоритм кролика-черепахи не гарантирует нам, что указатели встретятся на первом же обороте цикла, быстрый указатель может сначала перескочить медленный. Поэтому у нас может образоваться лишний проход по циклу.
Но ведь прыжок "кролика" на 2 шага - не атомарная операция, и ему ничто не помешает проверять совпадение и на промежуточном узле тоже.
Справедливое замечание.
Но в смысле производительности это не особенно влияет.
Не на промежуточном. Вместо скорости черепаха - 1, кролик - 2, использовать черепаха - 0.5, кролик - 1. Т.е. каждый цикл сдвигаем указатель кролика, а черепаший только каждую чётную (или не чётную) итерацию. Прос их скорость работы можно попробовать выровнять дополнительным указателем пометки. Помечаем позицию кролика, затем не трогаем её, пока её не догонит черепаха. Если догнала, то помечаем текущее положение кролика. А критерием остановки станет: 1. если достигнут конец незамкнутого списка. 2. кролик на первом элементе списка (кольцо). 3. кролик догнал черепаху. 4. кролик догнал помеченный указатель.
Чисто на пальцах тогда кол-во операций на поиск петли устремиться в 1.5*N в среднем...
На самом деле алгоритм как раз гарантирует встречу на первом проходе черепахи, оптимизация не нужна
Как он может это гарантировать? Всё зависит от чётности длины пути.
Я не знаю, что вы этим хотите сказать, но если вы банально разберёте по шагам третий пример на картинке, то там кролик перепрыгивает черепаху и обегает цикл два раза, прежде чем встретится с черепахой.
Я хочу сказать именно то что и написал - гарантируется что за первый проход черепахи по циклу кролик ее встретит. Доказательство - по ссылке. Третий пример вырожденный, потому что там "хвост" = 0, очевидно что он ее перескочит, т.к. мы уже находимся в цикле.
Оптимизация нужна для того, чтобы кролик встретил черепаху за первый свой совместный с черепахой проход по циклу, а не первый проход черепахи. За один проход черепахи кролик успевает обернуться два раза, это в наихудшем случае лишние L*1.5 операций по сравнению с неоптимизированной версией (лишние полкруга проходит черепаха и лишний круг проходит кролик).
Оптимизация нужна для того, чтобы кролик встретил черепаху за первый свой проход по циклу, а не первый проход черепахи
Тогда у меня вопрос - как найти начало цикла в вашей оптимизированной версии?
Это не моя оптимизированная версия, но ответ простой – отъехать кроликом на одну клетку назад (т.е. на место встречи, которое он перепрыгнул бы), а черепахой на одну клетку вперёд (т.е. начать во второй раз черепахой со второго узла), чтобы скомпенсировать изменившуюся чётность:
while ((ptr2 != NULL) && (ptr2->next != NULL)
&& (ptr1 != ptr2) && (ptr1 != ptr2->next)) {
ptr1 = ptr1->next;
ptr2 = ptr2->next->next;
}
if (ptr1 == ptr2->next) {
ptr2 = ptr1;
ptr1 = &array[1];
}
else
ptr1 = &array[0];
if (ptr1 != ptr2)
loopnode = 0;
else {
while (ptr1 != ptr2) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
loopnode = ptr1->num;
}Дело - не в четности как таковой. Тот факт что X(n) = X(2n) дает гарантию, что после того как мы скинем один из указателей на начало списка встреча произойдет в начале цикла. Есть ли такая гарантия после оптимизации?
Да, может я и неправ.
Тогда получается, что алгоритм неоптимизируемо содержит дофига лишних операций.
Я бы не назвал это "лишними операциями". Задача стоит в поиске такой ноды, в которой черепаха равноудалена от начала, а кролик равноудален от черепахи. После ее нахождения мы точно:
можем сказать, что в списке есть цикл
найти начало цикла
вычислить его длину
При этом гарантируется, что при наличии цикла такая нода встретится при первом проходе черепахи по нему. На мой взгляд это крайне изящный алгоритм)
Эта задача помечена как "Easy" на Leetcode. Там же, в разделе "Solutions" описаны примерно 8000 решений с использованием широкого спектра языков программирования и алгоритмических подходов.
По ссылке приведена более простая задача, где требуется просто обнаружить наличие цикла. Если действовать методом кролика и черепахи, то основная сложность состоит в рассуждении, необходимом для поиска начала цикла.
Да, действительно, это я невнимательно прочитал условие задачи. На Leetcode, кстати, есть и этот вариант.
Это сложность выбранного способа решения, а не собственно задачи.
Но она действительно сложнее литкодовской. А более сложная эта задача потому, что поставлено дополнительное условие не использовать дополнительную память для накопления списка пройденных узлов. Без этого условия задача становится чуть ли не тривиальной, и необходимость найти начало цикла её почти не усложняет.
А где, кстати, доказательство что движение из точки встречи приведёт именно к началу цикла? Самое важное в посте отсутствует :)
Если вообще они встретятся, двигаясь оба с одинаковой единичной скоростью, то не могут первоначально встретиться ни в каком другом месте, кроме начала цикла, так как это точка объединения их траекторий.
"Далее более тонкими рассуждениями можно показать, что после встречи, если продвигать два указателя по 1 узлу за шаг, начав от начала списка и от места встречи соответственно, то эти указатели встретятся в начале цикла."
Насколько я могу судить, это неверно. На мой взгляд правильное решение, это делать по одному шагу из начала списка, и после каждого такого шага делать полный круг из точки встречи.
Это абсолютно точно верно. Вообще об этой задаче проще становится думать (по крайней мере лично мне) когда ты цикл представляешь в виде бесконечной числовой последовательности, часть которой постоянно повторяется. Место их встречи - это некое количество шагов, которое прошла черепаха и по свойствам цикла это количество делится нацело на длину цикла. Если вернуть черепаху в начало то разница в расстояниях между ними - это удвоенное расстояние которое прошла черепаха, но которое все еще делится нацело на длину цикла. А значит, что как только черепаха, двигаясь от начала, попадет на начало цикла кролик будет там же.
Даже если расстояние до начала цикла взаимопростое с длиной цикла?
Кстати, оптимизация "заец проверяет пересечение когда бежит" ломает гарантию встречи вначале
Я ни про какие оптимизации не говорил, я про классический вариант алгоритма. Расстояние до начала цикла особо не имеет значения, оно влияет только на количество шагов до встречи черепахи и кролика в первый раз, свойства алгоритма от этого не меняются
Я про кратность расстояния - не понимаю как оно гарантирует встречу в начале цикла.
А оптимизация это мысли вслух по поводу
У самого цикла есть характеристика - его длина. И есть свойство - если мы выберем любую ноду внутри цикла и пройдем число шагов кратное его длине мы окажемся в том же месте. Т.к. расстояние между черепахой и кроликом как раз такое число, то если мы начнем бежать черепахой сначала списка, то начало цикла как раз и есть первая нода, в которой они встретятся.
Понятнее не стало совершенно...
Обозначим
r — "длина ручки", оно же число узлов до входа в цикл.
L — длина цикла.
Пусть до первой встречи черепаха прошла r+t шагов, то есть r шагов вне цикла, t — внутри цикла. Черепаха стоит на позиции цикла
r+t-r (mod L) = t (mod L)
(считаем, что начальная нода цикла имеет номер 0).
Заяц за это время прошёл 2(r+t) шагов и стоит на позиции цикла
2(r+t)-r (mod L) = r+2t (mod L)
Т.к. позиции одинаковые,
t = r+2t (mod L)
r+t = 0 (mod L)
То есть, от той позиции t (mod L), где сейчас стоит черепаха, до стартовой позиции цикла 0, нужно сделать r шагов.
Запускаем зайца с начала "хвостика" с единичной скоростью, он делает r шагов по хвостику до входа в цикл. Черепаха делает за это время те же r шагов, и они встречаются в начале цикла.
Черепаха стоит на позиции цикла
r+t-r (mod L) = t (mod L)
Так вот это утверждение и требует доказательства...
По определению t и r.
Это равенство было лишним (в левой части подсчёт шагов с начала движения, в правой части — с момента входа в цикл).
Достаточно было просто написать:
Пусть t — число шагов, которое черепаха прошла внутри цикла. Тогда она стоит на позиции цикла t (mod L)
На сколько я помню, до гарантируется, что первое r + t:
r < r + t < r + L
0 < t < L
Т.е. остаток от деления здесь тоже лишний
Он не лишний в том смысле, что задаёт формализм рассмотрения. То есть это арифметика по модулю, а не операция нахождения остатка.
В частном случае операции +mod и =mod могут совпадать с + и =, но нам это неважно.
гарантируется, что первое r + t: 0 < t < L
Для меня не очевидно, что заяц не обгонит черепаху на первом круге, а точно в неё попадёт. Если это так, надо доказывать.
Строго говоря, надо доказывать, что позиция когда-нибудь совпадёт. Это так, потому что скорости, 1 и 2, взаимно простые (upd. если точнее, необходимо, чтобы разница скоростей была взаимно простой с L)
Более того, тривиально привести пример когда не встретятся на первом круге
Строго говоря, надо доказывать, что позиция когда-нибудь совпадёт. Это так, потому что скорости, 1 и 2, взаимно простые.
Свойство цикла: X(n) = X (n + k * L), где k - натуральное число, а L - длина цикла. Словами: если мы из любой ноды пройдем количество шагов кратное циклу мы окажемся в ней же.
В случае если X(n) = X(2n), то n (mod L) = 0 из свойства выше, т.е. n = k * L.
Теперь можно показать, если n - первое такое число (их больше чем одно), то r < n < r + L
n > r - т.к. такое X(n) = X(2n) справедливо только для нод внутри цикла.
Теперь покажем что r + L > n
r = z * L + y, где y = r (mod L) и принадлежит натуральным числам.
Пусть первым n, которое больше r и делится без остатка на L будет r + t, или
z * L + y + t
Т.к. n (mod L) = 0, то y + t = L, или t = L - y
Получается что:
r + L > r + L - y
Неравенство выполняется, потому что y - натуральное число
Выходит что r < n < r + L
То есть, от той позиции t (mod L), где сейчас стоит черепаха, до стартовой позиции цикла 0, нужно сделать r шагов.
Я бы только уточнил, что до позиции цикла 0 будет
L - t шагов, но при этом есть гарантия, что если мы стоя на позиции t пройдем r шагов - мы попадем в начало цикла.
Если мне не изменяет память, то позицию черепахи надо бы сбросить на начало списка, тогда их встреча будет в начале
Да ладно. Мы же будем знать длину цикла (умноженную на какое-то натуральное число – сколько кругов сделал кролик) L*n, а зная её – наверняка почти все догадаются, как найти цикл (два курсора с расстоянием L*n между ними, двигающиеся с одинаковой скоростью – очень прозрачное решение... Визуально можно его представить, как змею длиной L*n, ползущую по списку – когда она полностью вползёт в цикл, голова совпадёт с хвостом).
Так что imho главное препятствие – додуматься (или вспомнить откуда-нибудь – ну там, из школьных олимпиадных задачек или из алгоритмов для машины Поста) до идеи "кролика и черепахи".
Идея интересная. При первом совпадении черепахи и зайца после X шагов, заяц останавливается, а черепаха продолжает движение. Когда она снова нагонит зайца, мы узнаем длину цикла L. Но я не могу сообразить, куда двигаться дальше, чтобы найти точку входа в цикл, не перезапуская один из курсоров с самого начала. Вроде как, одних только X и L недостаточно. Выше было доказано, что X=L, т.е. это зависимые переменные.
Это часом не про эту задачу? :)
Если кандидат предложит вам решение на базе модификации указателй -- гоните его в шею, это человек без внутренних тормозов, который и в прод такую чернуху протянет потом :)
Есть сермяжная правда в ваших словах, но в системном программировании такое встречается :)
В частности, в сборщиках мусора любимое дело размещать свои временные данные в собираемом мусоре.
При условии, что задача "штатная" -- про алгоритмы, без априорных знаний насчет архитектуры указателей на конкретной машине, выбор решения в поле модификации немодифицируемого -- большой минус в карму решающего. Просто за выбор нерелевантного костыля.
Да, есть класс задач специальной олимпиады "сделай компилятор в 256 байт", где можно любую грязь втащить, но это ж явно не оно.
Я часто использую модификацию указателей. Если адрес выровнен на границе 4 байт, то это значит, что младшие 2 бита указателя всегда 0, и их можно использовать в качестве битовых флагов. В задаче из статьи один из битов можно использовать для пометки того, что элемент уже пройден. Если нам попадётся элемент с этим установленным битом, то в списке - цикл.
// Распределение блока памяти, всегда выровненного на границе 4 байт
unsigned char *real_block =
(unsigned char *)malloc(num_bytes); // контейнер для блока
unsigned char *aligned_block; // выровненный блок
if((((size_t)real_block) & 3) == 0)
{
aligned_block = real_block;
}
else
{
// здесь можно использовать _expand(...), но я не стал усложнять пример
free(real_block);
real_block = (unsigned char *)malloc(num_bytes + 3);
size_t correction = (-(int)(size_t)real_block) & 3;
aligned_block = real_block + correction;
}В качестве блока можно рассматривать массив элементов, используемый для контейнера hive/colony. Из этого контейнера распределяются элементы для списка, и каждый из них будет выровнен на 4 байта.
А для навигации по списку используются методы, а не прямой доступ к полям:
struct ListItem
{
size_t next_with_flags;
int data;
ListItem* next() {return (ListItem *)(next_with_flags & (size_t)(ptrdiff_t)~3);}
unsigned flags() {return (unsigned)next_with_flags & 3;}
};Сталкивался с кое-чем похожим в продакшене. Раз в месяц на него падал взгляд и мы все передёргивались. Однажды нервы не выдержали, вычистили нафиг.
ЗЫ: А ещё – переключение между ARM и Thumb инструкциями по младшему биту адреса.
Ага, а параллельно этот список читает ещё сотня потоков, которые будут очень рады его модификации.
Достаточно одного потока и связного списка определённого в виде
struct linked_list;
int linked_list_node_number(const struct linked_list *);
const struct linked_list *linked_list_next(const struct linked_list *);
extern const struct linked_list *start;Попробуйте помодифицировать что‐то, не получив Undefined Behaviour. Для разумных программистов можно даже удалить все const — одной инкапсуляции достаточно.
Алгоритм кролика-черепахи не гарантирует нам, что указатели встретятся на первом же обороте цикла, быстрый указатель может сначала перескочить медленный
Текущий алгоритм с кроликом и черепахой, как я понимаю, двигает и кролика, и черепаху, а затем сравнивает местоположения.
Если же после каждого прыжка хоть кого-то сравнивать местоположения, то никакого "перепрыгнет" не будет. И соответственно не будет потенциального "второго оборота".
В этих условиях при проверке на каждом прыжке можно кролику прыгать не на 2, а на 3 узла. Всё равно мимо не проскочит.
Но при этом возможна лишняя бегодня кролика по циклу, к которому ползёт черепаха
В этих условиях при проверке на каждом прыжке можно кролику прыгать не на 2, а на 3 узла. Всё равно мимо не проскочит.
Если кролик и черепаха стартуют от двух соседних элементов, как в статье, то попадают на бесконечный цикл, при условии, что длина цикла в списке равна равна 6*n
В приведённых примерах оказывается, что элемены списка лежат подряд, и хождение по нему оказывается равносильно линейному чтению памяти. Для более релевантных результатов хорошо бы для начала "перемешать" список: так, чтобы прыжки по .next были бы в рандомные позиции. И время создания/перемешивания тоже не измерять, а только целевую задачу.
Что касается расположения элементов списка, я думал об этом, но в любом случае это вряд ли сильно изменит сравнительную картину – просто возрастут оба времени. Кроме того, вообще не очень очевидно, что рандомные позиции релевантнее последовательных.
Меня в измерениях беспокоил, в основном, ответ на вопрос, не просядет ли производительность из-за операций записи. И на другом процессоре, образца 12-летней давности, она действительно заметно просаживается.
А что касается времени создания, то оно не учитывается.
Интересное наблюдение: первый алгоритм делает 4 прохода по массиву от начала до конца: сначала 3 прохода до совпадения указателей, потом ещё один для нахождения 1ого элемента (один потому что ввиду построенного списка, где конец указывает на 2ой элемент, ptr1 и ptr2 оказываются недалеко друг от друга, и зафетченное в кеш для "спешащего" указателя пригождается чуть позже "опаздывающему"). Второй алгоритм (с восстановлением) тоже делает 4 прохода: один раз вычитывает всю память, тут же (с лагом в размер кеша, предполагая что тот writeback) отписывает обратно, потом ещё раз делает то же самое (для восстановления). Последний алгоритм делает лишь 2 прохода.
По скорости выполнения ровно то и выходит -- 1ый и 2ой время примерно одинаковое, у 3его в 2 раза быстрее.
Тут смысл задачи в том, что в элементах списка нельзя ничего хранить.
И тогда получается типичная задача на собеседовании: если не знать подхода, не решишь, если знаешь трюк про шаг по 1 и по 2 -- решишь. По подходу ничем особо не отличается от "почему люки круглые" :)
В таком условии нет особого содержательного смысла. Почему нельзя?
Почему может не хватать лишней памяти – это объяснимо. А тут было бы искусственное ограничение, на мой взгляд.
Почему нельзя?
Например у нас 32битное приложение на 64битной системе (соответственно, практически всё адресное пространство может быть использовано, лишнего бита в адресе нет), а номер элемента - unsigned short (и допустимы списки до 65535 элементов), то есть там тоже битика не найдётся.
Даже при таких замороченных условиях будет лишний младший бит адреса, так как 6- или 8- байтовые структуры на практике будут выравнены на 2.
Ok, предположим что у нас используется кастомный аллокатор, который может и нечётные адреса выдавать (на интеловской архитектуре выравнивание не требуется).
Причём всё это может вылезти не сразу, а после того, как код с модификацией протестировали в "обычных" условиях, закоммитили в продукт, странное поведение началось через пару лет, когда автор давно уволился.
Кмк если человек выдаст решение с пометкой узлов – ему просто озвучат дополнительное условие. Вряд ли это станет проблемой на собеседовании (а если станет – в такое место лучше не идти), нормальный разговор про задачку...
ЗЫ: Вот всё думаю, как бы я решал такую задачку, если бы вылезла в реальной жизни. 99% не метил бы узлы – плохо трогать чужие данные (мультитрединг и всё такое). Но и решение с зайцем и черепахой – красивое, но придётся писать комментарии для того, кто будет читать код. Наверняка бы доп условия собрал (типа возможной длины списка) и тогда уже думал...
Я бы копал в сторону фильтра Блума и его модификаций
Можно рассуждать так. Пусть цикл есть. Пусть r - длина ручки списка (число шагов до первого узла в цикле), m - длина цикла. Тогда черепаха делает r + k шагов, где k шагов в цикле. Заяц делает r + t * m + k = 2 * (r + k), где t - полное число проходов по циклу, и т.к. на каждый шаг черепахи 2 шага зайца. Поэтому r + k = t * m, r = t * m - k. Пусть оба встречаются в некотором узле А цикла, тогда после встречи пусть одна черепаха бежит из начала списка, друга из узла А. Тогда они встретятся в искомом узле (начале цикла), потому что пока одна пробегает длину ручки, другая пробегает остаток цикла m - k и делает несколько полных оборотов - число кратное m, если t > 0 это t - 1.
Как насчет такого ненормального подхода?
Т.к. значение каждого узла ограничено -10^5 <= Node.val <= 10^5, значит можно каждому такому числу сопоставить некое простое число, не превышающее какой-то фиксированный размер в памяти, например взять простое число под номером 2*abs(Node.val) + (sign(Node.val) + 1)//2. При проходе по листу, считаем бегущее произведение прошлых простых чисел, и если простое число, соответствующее текущему Node.val делит это произведение без остатка, значит мы оказались в узле, в котором мы уже раньше были.
Вот это мощно!!!
Но по сути это форма запоминания номеров.
Если правильно понял, для этого нужно взаимно-однозначное соответствие между узлами и простыми числами. По ссылке длина списка до 10^4, то есть в случае отсутствия цикла у нас в итоге будет произведение 10^4 первых простых чисел. Множество чисел изначально слишком большое и произведение будет слишком большое. Десятитысячное простое число больше 100000.
Будьте проще – сопоставьте каждому узлу число 2**n. И считайте их дизъюнкцию (or). Но это память O(n) (с простыми числами, кажется, ещё больше).
ЗЫ: Ваше решение напомнило доказательство теорема Гёделя о неполноте, там емнип тоже как раз простые числа использовались... Надо перечитать.
ЗЫ2: Теоремы я, наверное, спутал... Но где-то точно в доказательстве такую идею видел.
Задача действительно лишена практического смысла так как следить за отсутствием циклов в списке надо на этапе создания списка. Если есть вероятность появления такого списка в какой-то реальной программе программу надо переписывать, она не то что не будет работать, она вполне может предстовлять опасность.
Получается это задача о том как правильно подставить костыль. А надо писать так чтобы костыли были не нужны.
Мы ж не знаем прикладного назначения этой структуры данных. Может, она как раз и предназначена для каких-то циклических вещей.
В этом случае в структуре должно быть записано где и как она хитровыделана, потому что это напрямую влияет на ее обработку.
UPD: задача, на самом деле, не то что нереалистичная, просто она из серии как сделать через жопу а потом рвать на жопе волосся, героически превозмогая.
Мы ж не знаем прикладного назначения этой структуры данных
и из этого также следует бесполезность решения любых задач на основе такой структуры данных. Раз мы не знаем прикладного назначения мы ни как не достигнем этого прикладного назначения.
Допустим, вам скажут, что это номера авторитетных инстанций, без согласования которых по правилам нельзя подписать какой-то документ. И мы хотим на всякий случай проверить, что реально существующая в физическом мире цепочка согласований не циклична.
А для такой задачи вот это допусловие
Следующим шагом зрителям в ролике давалась подсказка: если кто придумал сохранять пройденные узлы в какой-то своей структуре данных и проверять каждый новый узел на присутствие в этой структуре, то такое решение плохое, так как алгоритм не должен требовать O(n) дополнительной памяти.
не имеет смысла. Если это единичная проверка входных данных, которая отрабатывает раз в год, то она должна в первую очередь проверять данные, во вторую — быть понимаемой, читаемой и редактируемой, а заниматься хитрыми извращениями — в самую распоследнюю.
и при чем тогда здесь указатели, и связанный список?
Потом вы допустили одно, он другое, кто то третье, решать будем что-то в среднем что ли? Вы считаете это имеет смысл?
Задача действительно лишена практического смысла
Нет. Пусть есть последовательность зависимостей, которую нужно проверить на отсутствие циклов. Циклы могут образовывать зависимости, например, в программных файлах, включаемых друг в друга, или в вызывающих друг друга функциях. Тут https://youtu.be/Qc8zuhaqWPM?t=457 Тим Кейн рассказывает о таком случае в разработке Arcanum. Он решает её добавлением ограничения на количество вложенных вызовов. Эта задача - разновидность задачи поиска цикла в графе. Она возникает в самых разных местах. Именно о задаче из статьи впервые услышал на лекции Степанова А.А. в Яндексе. Яндекс, кажется, местами отмирает - не могу найти ссылку на лекцию, а та что есть не работает.
Пусть есть последовательность зависимостей
Если можно начать с "Пусть", я предпочту начать так:
(А-) Пусть ее НЕТ, этой последовательности зависимостей ...
В том смысле, например, что давайте не будем ее допускать по мере формирования списка, список то в памяти все равно как то формируется, а не из сферической реальности прилетает!
Гоголь когда-то написал:
Тогдашний род учения страшно расходился с образом жизни: эти схоластические, грамматические, реторические и логические тонкости решительно не прикасались ко времени, никогда не применялись и не повторялись в жизни. Учившиеся им ни к чему не могли привязать своих познаний, хотя бы даже менее схоластических. Самые тогдашние ученые более других были невежды, потому что вовсе были удалены от опыта.
Если модификация списка не запрещена, есть один вариант, только я его до конца не додумал. Таки да, на первом проходе надо указатели разворачивать, тогда или (1) список закончится (циклов нет), или (2) мы вернёмся к его началу. При этом надо считать количество шагов L. При исходе (1) можно список развернуть обратно. При исходе (2) у нас будет элемент в позиции L/2, который является самой дальней точкой и находится точно в середине цикла (или два элемента, с учётом четности L). Нам нужно дойти до него (опять же, разворачивая указатели) и дальше идти по обеим веткам обратно, пока указатели не укажут на один элемент, это и будет начало цикла. При этом ветку, которая идёт "вперёд", надо разворачивать, а ветку, которая идёт "назад" и по которой мы пришли в L/2, разворачивать не надо. Тогда после завершения поиска у нас список вернется в исходное состояние.
Возможно, я сейчас изобрёл велосипед, который описан где-то в умных книгах. Зато сам)
В каждом узле списка располагается его уникальный номер (не обязательно в порядке связности списка)
А обязательно ли нумерация начинается с 1 и нет пропусков в нумерации? А то ведь можно просто считать максимум и количество пройденных узлов. Как только превышение, значит мы на первом узле кольца. Само собой если встретили null, то кольца нет
осталось только выяснить откуда взять количество узлов в списке, когда список зациклен их посчитать не получится.
Как я уже писал выше:
Задача действительно лишена практического смысла так как следить за отсутствием циклов в списке надо на этапе создания списка. Если есть вероятность появления такого списка в какой-то реальной программе программу надо переписывать, она не то что не будет работать, она вполне может предстовлять опасность.
откуда взять количество узлов в списке
Так посчитать можно.
int count = 0;
int maxId = 0;
Node *item = <первый элемент>;
while(item!=null) {
maxId = max(maxId, item->info);
count++;
if(count > maxId) {
printf("Первый элемент цикла %i",item->info);
break;
}
item = item->link;
}
if(head==null) {
printf("Нет циклов");
}Если начинается всегда с 1-го номера и без пропусков, то даже если они не по порядку, то алгоритм будет работать.
Проблема в том что постоянно вылезают какие-то "если"!
если у item есть item->info
если определена операция max() для (maxId, item->info)
Это только то что вы придумали, выше смотрите другие варианты!
При таком количестви "если" это превращается в какой-то маразматический перебор для всех "если" и "не-если".
Лично я вот, очень не люблю маразматические переборы, и к тем кто их устраиваевает отношусь с недоверием, мягко говоря.
Я считаю, что задача для интервью должна решаться в том виде, в каком она была поставлена. Если человек нарисовал в качестве примеров три схемы с последовательными натуральными числами и ничего больше не сказал, то имеет право получить решение в соответствии со своим ТЗ. Поэтому, с моей точки зрения, важен приведённый скриншот.
если у item есть item->info
если определена операция max() для (maxId, item->info)
Вот это не предположение, а 100% верно исходя из условия задачи. Тут я ничего не придумываю.
"Если" тут только относится к нумерации с 1 и предположения что нумерация идет без пропусков. Про это в условии задачи ничего нет и требуется уточнение. Не "маразматический перебор", а уточнение у постановщика. Вполне допускаю что суть задачи не только в решении, а ещё и в правильно заданном вопросе.
upd: слишком долго писал комментарий, shasoftX меня опередил
Если мы знаем, что все уникальные номера узлов находятся в пределах от 1 до N, где N — число элементов списка, то есть решение, которое требует одного "прогона" и не меняет исходный список.
Заводим два числа:
- Счетчик количества узлов с начала
- Бегущий максимум встреченных значений элементов
Как только 1-е число оказывается строго больше 2-го, значит мы находимся на искомом элементе входа в "цикл" (если мы конечно не придем в null до этого).
Почему это работает? Потому что максимум инвариантен к перестановкам в списке, и при проходе всех элементов списка мы обязательно получим 2-е число равное N. Поэтому, как только мы вернемся в элемент, который уже посещали до этого, т.е. перейдем в N+1 элемент по счету, мы получим выполнение условия на выход из цикла.
Если нам во время проверки не требуется читать список из другого потока и временно можно его модифицировать, то возможен другой неожиданный способ - инвертировать список.
Т.е. проходимся по списку, меняем направление ссылки с потомка на родителя. В списке без петель новой головой списка станет хвост. В списке с петлёй мы придём к голове.
Т.е. 1. Инвертируем список. 2. Проверяем равна ли новая голова старой. 3. Восстанавливаем список, снова инвертируя его, относительно новой головы.
Набросал быстро программку для проверки идеи. Вроде работает. Проверить можно здесь.
Что было под рукой...
{$MODE OBJFPC}{$H+}
{$R+}
type
PListNode = ^TListNode;
TListNode = record
Next: PListNode;
Id: Integer;
end;
function AddNode(PrevNode: PListNode; Id: Integer): PListNode;
begin
New(Result);
Result^.Next := nil;
Result^.Id := Id;
if PrevNode <> nil then
PrevNode^.Next := Result;
end;
procedure DeleteList(FirstNode, LastNode: PListNode);
var
DelNode: PListNode;
begin
repeat
DelNode := FirstNode;
FirstNode := FirstNode^.Next;
if FirstNode = LastNode then
FirstNode^.Next := nil;
Write(DelNode^.Id, ' ');
Dispose(DelNode);
until FirstNode = nil;
Writeln;
end;
function InvertList(FirstNode: PListNode): PListNode;
var
PrevNode, CurrNode, NextNode: PListNode;
FirstPass: Integer;
begin
PrevNode := nil;
CurrNode := FirstNode;
NextNode := CurrNode^.Next;
FirstPass := 0;
repeat
if CurrNode = FirstNode then
FirstPass := FirstPass + 1;
CurrNode^.Next := PrevNode;
PrevNode := CurrNode;
CurrNode := NextNode;
if CurrNode <> nil then
NextNode := CurrNode^.Next;
until (CurrNode = nil) or ((FirstPass = 2) and (PrevNode = FirstNode));
if CurrNode = nil then
Result := PrevNode
else
Result := CurrNode;
end;
function CheckLoop(FirstNode: PListNode): Boolean;
var
NewFirstNode: PListNode;
begin
if FirstNode^.Next <> nil then
begin
if FirstNode^.Next <> FirstNode then
begin
NewFirstNode := InvertList(FirstNode);
Result := NewFirstNode = FirstNode;
InvertList(NewFirstNode);
end
else
Result := True;
end
else
Result := False;
end;
procedure WriteBool(Value: Boolean);
begin
if Value then
Writeln('True')
else
Writeln('False');
end;
var
N1_1, N1_2, N1_3, N1_4, N1_5, N1_6, N2_1, N2_3, N2_2, N3_1, N3_2, N3_3,
N3_4: PListNode;
begin
N1_1 := AddNode(nil, 1);
N1_4 := AddNode(N1_1, 4);
N1_2 := AddNode(N1_4, 2);
N1_3 := AddNode(N1_2, 3);
N1_5 := AddNode(N1_3, 5);
N1_6 := AddNode(N1_5, 6);
N1_6^.Next := N1_2;
N2_1 := AddNode(nil, 1);
N2_3 := AddNode(N2_1, 3);
N2_2 := AddNode(N2_3, 2);
N3_1 := AddNode(nil, 1);
N3_3 := AddNode(N3_1, 3);
N3_4 := AddNode(N3_3, 4);
N3_2 := AddNode(N3_4, 2);
N3_2^.Next := N3_1;
WriteBool(CheckLoop(N1_1));
WriteBool(CheckLoop(N2_1));
WriteBool(CheckLoop(N3_1));
DeleteList(N1_1, N1_6);
DeleteList(N2_1, N2_2);
DeleteList(N3_1, N3_2);
end.
Я не смотрел оригинальное видео и не знаю как там преподносится, но я просто обожаю такие варианты постановки задачи, а именно:
- Вот задача и у вас развязаны руки
- А нет не развязаны, а немного связаны(так как алгоритм не должен требовать O(n) дополнительной памяти), почему сразу это не озвучить
- Подсказка никак не выплывающая из постановки задачи(Использовать один указатель, и в каждом пройденном узле менять, например, значение номера на отрицательное) Оказывается можем колбасить список как ходим.
Да какогож хрена я должен догадаться до пункта два и пункта три.
С такими подходами может от меня ждут что я вообще при помощи файловой системы это решить должен?
Да какогож хрена я должен догадаться до пункта два и пункта три.
Ни с какого. Так в общем случае делать нельзя. Такой подход называется "тегирование", но его применение допустимо, лишь если у вас есть дополнительные гарантии. В данном случае, что все числа не отрицательные.
А то так-то и верхний бит указателей на следующий узел можно использовать для пометки.
Есть универсальное решение, а есть контекстно-зависимое, с оптимизацией под конкретные данные. Так как в задаче про конкретные данные ничего не сказано, то и решение должно быть универсальное. Так как я могу на том же собеседовании сказать, что это поиск петли в readonly БД на 45 петабайт и вся эта маркировка канет в лету.
Если это поиск во внешней памяти, то мы не только вправе, но и обязаны строить кеш в оперативке. Не бывает универсальных решений.
Если это поиск во внешней памяти, то мы не только вправе, но и обязаны строить кеш в оперативке
нет оперативки
Не бывает универсальных решений
все библиотеки всех языков программирования разом заорали - ведь они, оказывается, не существуют. По-вашему этого просто не существует?
Это существует, но это далеко не универсальный метод. Попробуйте так отсортировать магнитную ленту.
Это проблема не метода и не реализации, это вопрос организации доступа к оборудованию. Например я пользовался стиммерами HP еще в 2008 году, там всё делала сама железка и софтовая часть в ядре, для Oracle *nix работа ничем не отличалась от работы с SAS СХД или HDD. Соответственно и Sort будет работать, а вопрос эффективности - уже находится в категории "контекстно-зависимое решение".
Кстати, вот тут задачка резко становится интересной для разговора. Ибо оптимальный вариант построения кэша совершенно неочевиднен (кэш длиной с таблицу, очевидно, недоступен, надо задаться конкретным размером и придумать структуру с максимальной производительностью).
Метод маркировки (сменой знака) требует O(n) дополнительной памяти. Он возможен в тех случаях, когда в списке изначально присутствуют пустые места, например, пустой знаковый бит. В остальных случаях он нерабочий.
Это игра словами. В любом случае, приводившийся выше в комментариях метод маркировки сменой направления указателя не требует дополнительной памяти даже в вашем определении. При этом он использует меньше проходов по узлам даже в том случае, когда мы восстанавливаем исходное состояние.
Это игра словами
Это у вас игра словами. Если забывать "мелочи" на расходы памяти, можно написать идеальный архиватор, который любой файл гарантированно уменьшает на 1 байт, перенося этот байт в имя файла. Трюк с записью неиспользуемых бит в указателе примерно такого же рода читерство.
В любом случае, приводившийся выше в комментариях метод маркировки сменой направления указателя не требует дополнительной памяти
Формально, это не метод маркировки, это другой алгоритм. И он по нескольким причинам хуже "зайца и черепахи", потому что
1) требует 2 раза пройти и хвостик, и петлю, восстанавливая указатели как было
2) не находит позицию входа в петлю.
(не говоря уже о модификации данных)
Если забывать "мелочи" на расходы памяти, можно написать идеальный архиватор, который любой файл гарантированно уменьшает на 1 байт, перенося этот байт в имя файла.
Это вполне нормальный ход, если стоит именно такая задача.
Алгоритм с битовой маркировкой имеет заданный вход, заданный выход, заданный расход рабочей памяти и заданный результат работы. Какие вопросы?
Если нам дали на вход структуру данных, содержащую пустые места, это наша законная добыча.
Формально, это не метод маркировки, это другой алгоритм. И он по нескольким причинам хуже "зайца и черепахи", потому что 1) требует 2 раза пройти и хвостик, и петлю,
Алгоритм кролика и черепахи требует от 2 до 3.75 раз пройти все узлы. Указателя-то два.
2) не находит позицию входа в петлю.(не говоря уже о модификации данных)
В этом комментарии намечено, как в таком случае найти точку входа. Хотя это опять-таки лишняя работа.
3.75 3.5
Как вы решали бы эту задачу?
Тестовая задача обычно рассматривается в контексте интервью. В опросе нет ни одного правильного варианта.
Кроме решения задачи, на интервью, смотрят на то, как вы работаете с требованиями и рассуждаете.
Если вы после получения задачи замолчите и вернётесь с идеальным техническим решением, то вы провалили интервью. Пожалуйста, не далайте этой ошибки.
На своём опыте, я бы порекомендовал такую стратегию:
- Проговорить несколько вариантов, хэш, зайц и черепах, маркировка. Объяснить плюсы и минусы (сложность по памяти, сложность выполнения, сложность реализации). В процессе этого уточнять требования, типа: "Подойдёт ли решение O(n) по памяти?" (если вы на сеньёра, то скорее всего нет) или "Влезут ли данне в хэшмэпу?" (она большая, но не бесконечная). "Можно ли мутировать?" (без этого вопроса, предлагать вариант с мутацией, это путь к провалу).
И после этого договориться с интервьюером, какой вариант вы будете решать. По возможности стоит попробовать подтолкнуть интервьюера, к решению, которое вам кажется более простым в реализации.
Этим вы покажете ширину своих знаний и инженерный подход к решению задач. И пойметё, что решаете ту задачу которую нужно. Я как-то похоже на собеседовании сделал, https://habr.com/ru/articles/743514/#comment_25682476, не перезвонили.
вызвать метод для получения количества элементов в структуре и цикле пройти n + 1 элементов
Если б был метод для получения количества элементов, не было б задачи.
Это литкод изи... Плюс, не надо недооценивать как много людей могут провалить даже такую реализацию
Нет, изи это просто проверить, что цикл есть, эта задача средняя.
https://leetcode.com/problems/linked-list-cycle-ii/
Использовал бы алгоритм с двумя кроликами.
Публикации
Об одной тестовой задаче