?

Log in

No account? Create an account
entries friends calendar profile My Website Previous Previous Next Next
"Глокая куздра" на программистский лад - Уголок Школьника
scolar
scolar
"Глокая куздра" на программистский лад
Все конечно знают наизусть про то, как "глокая куздра штеко будланула бокра и курдячит бокренка". Несколько лет назад на каком-то из порталов типа грамоты.ру (или на форумах передачи "Говорим по-русски" радио "Эхо Москвы") несколько энтузиастов предлагали иные разборы (отличные от канонического) - там то "глокая" было деепричастием, то "куздра штеко" была "антилопой-гну", короче оттянулись.

К чему это я? А, вот: пару дней назад avva предложил русский вариант "интервью невпопад" (для непрограммистов - там соискатель выдаёт идеи решения известных задач, ставших классикой интервью). Первый обмен фразами там:
— Расскажите о своей карьере до сих пор.
— Запустить два указателя по списку, чтобы один двигался в два раза медленнее другого. Или, если можно разрушить список, пройти по нему, меняя направление указателей в обратную сторону.

dimrub в комментариях дополнил это ещё одной известной задачкой:
— Как вы предпочитаете изучать новую для вас технологию?
— В цикле меняем сохраненный элемент на текущий с вероятностью единица деленная на номер текущего элемента.

Это была предыстория. Мое наблюдение состоит в том, что вторая идея работает для первой задачи!

Задача: имеется односвязный список, определить, используя дополнительную память, размер которой не зависит от длины списка, не закольцован ли он.
Решение: заведем два указателя, один из которых идёт по списку, а второй указывает на один из уже пройденных элементов. Условие остановки цикла: первый дошёл до конца - список не закольцован, либо первый дошёл до второго - есть кольцо. В теле цикла на N-ой итерации мы с вероятностью 1/N меняем значение второго на значение первого, первый всегда сдвигаем на единицу вперед. Всё.

Вопрос: почему это сработает? Ответ: по теории вероятности.
Лемма 1. Если кольцо есть, то оба указателя, попав туда, уже оттуда не выйдут. Очевидно.
Лемма 2. Если кольцо есть, то второй элемент туда когда-нибудь попадёт. Следует из расходимости гармонического ряда.
Лемма 3: Если кольцо есть, то наступит такой момент, когда первый элемент пробежит полный круг, а второй за это время никуда не сдвинется - чуть интереснее, но тоже понятно: при длине кольца K вероятность того, что второй не сдвинется за следующие K итераций, начиная с итерации N+1, есть N/(N+K), что стремится к единице при N, стремящемся к бесконечности.

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

Tags: , ,

7 comments or Leave a comment
Comments
pilpilon From: pilpilon Date: March 3rd, 2007 08:04 am (UTC) (Link)
Я, когда меня спросили, придумал на нном шага сохранять текущщее значение, сдвинуть н раз и сравнить с сохраненным.
А какое четвертое решение?
scolar From: scolar Date: March 3rd, 2007 03:14 pm (UTC) (Link)
1. С переворотом списка и проходом от предыдущего к началу (ставшему хвостом) - если пройдет через текущий - нашли цикл.
2. С двумя указателями - один сдвигается на единицу, второй на два. В круге догонет.
3. Твоё решение
4. Вышеизложенное извращение
From: sonte Date: March 8th, 2007 09:53 am (UTC) (Link)
А как "на N-ой итерации мы с вероятностью 1/N меняем...", используя только O(1) памяти при N, стремящемся к бесконечности?
scolar From: scolar Date: March 8th, 2007 02:23 pm (UTC) (Link)
Я, наверное, торможу спросонок: в чём вопрос?

Как с памятью O(1) организовать генератор случайных чисел от нуля до единицы с равномерным распределением? Или как сравнить число на отрезке [0;1] с числом 1/N?

From: sonte Date: March 8th, 2007 02:45 pm (UTC) (Link)
Вопрос: не придётся ли хранить число N?
Вроде бы при навном подходе нужно, и на это нужно много битов (кажется, даже матожидание зависит от длины кольца в списке).
scolar From: scolar Date: March 8th, 2007 04:40 pm (UTC) (Link)
Ага - это дырка. Справедливая, впрочем, и для оригинальной задачи, от которой взято решение (выдача с равной вероятностью элементов поступающей на вход последовательности неизвестной длины с использованием памяти, размер которой не зависит от длины последовательности).
From: sonte Date: March 8th, 2007 09:19 pm (UTC) (Link)
Жаль. Красивое решение. Остаётся надеяться, что что-то похожее полезно в каком-нибудь варианте rho-метода для разложения на множители.
7 comments or Leave a comment