Проверить список на зацикленность

nemiga · Сообщение **nemiga** » 31 мар 2007, 08:17

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

.

Stanislav · Сообщение **Stanislav** » 31 мар 2007, 08:46

Вы это серьезно? Прямо в субботу утром?
У меня к вам встречная задача: случайно был удален OU из AD - предложите самый быстрый способ восстановления OU.

nemiga · Сообщение **nemiga** » 31 мар 2007, 09:59

Tony писал(а):Easy, it involves a "Turtle and Rabbit" algorithm

Спасибо. Я так и ответил. Единственно, я думал, что этот алгоритм называется Ахиллес и черепаха -- может, поэтому интервьювер и сказал "almost correct"?

.

ajkj3em · Сообщение **ajkj3em** » 31 мар 2007, 10:29

nemiga писал(а):может, поэтому интервьювер и сказал "almost correct"?

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

это из серии, что удаление элемента из бинарного tree - это
алгоритм вирта. ну да, в какой-то книжке так написано, но
по жизни он называетcя "удаление элемента из бинарного дерева" :)

sz · Сообщение sz » 31 мар 2007, 13:07

Tony писал(а):Easy, it involves a "Turtle and Rabbit" algorithm.

You have two pointers traversing the linked list - one fast (2 steps at a time), another slow (1 step). If the fast one reaches the end of the list, there is obviously no loop involved. If the fast one passes the slow, there must be a loop.

Вот интересно. Алгоритм этот все знают и на интервью регулярно спрашивают.
Но лично я ни разу не видел его в реальной программе. По моему, он реально, по жизни, нафиг не нужен.

nemiga · Сообщение **nemiga** » 31 мар 2007, 13:23

sz писал(а):Вот интересно. Алгоритм этот все знают и на интервью регулярно спрашивают.
Но лично я ни разу не видел его в реальной программе. По моему, он реально, по жизни, нафиг не нужен.

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

.

ajkj3em · Сообщение **ajkj3em** » 31 мар 2007, 18:44

sz писал(а):
Tony писал(а):Easy, it involves a "Turtle and Rabbit" algorithm.

You have two pointers traversing the linked list - one fast (2 steps at a time), another slow (1 step). If the fast one reaches the end of the list, there is obviously no loop involved. If the fast one passes the slow, there must be a loop.
Вот интересно. Алгоритм этот все знают и на интервью регулярно спрашивают.
Но лично я ни разу не видел его в реальной программе. По моему, он реально, по жизни, нафиг не нужен.

я его первый раз уcлышал в немного другой форме на военной
кафедре в универе - дана функция генератора псевдо-случайных
чисел x(n) = f( x(n-1) ), найти ее период для данного seed value.

кстати хороший вариант задавать местным на интервью. про список
с двумя поинтерами все ответ знают, а на генераторе - сыпятся :)

Anry · Сообщение **Anry** » 31 мар 2007, 19:11

Stanislav писал(а):Вы это серьезно? Прямо в субботу утром?
У меня к вам встречная задача: случайно был удален OU из AD - предложите самый быстрый способ восстановления OU.

Ntdsutil.exe

Stanislav · Сообщение **Stanislav** » 31 мар 2007, 21:37

sz писал(а):
Tony писал(а):Easy, it involves a "Turtle and Rabbit" algorithm.
You have two pointers traversing the linked list - one fast (2 steps at a time), another slow (1 step). If the fast one reaches the end of the list, there is obviously no loop involved. If the fast one passes the slow, there must be a loop.
Вот интересно. Алгоритм этот все знают и на интервью регулярно спрашивают.
Но лично я ни разу не видел его в реальной программе. По моему, он реально, по жизни, нафиг не нужен.

Это алгоритм ловит все зацикления, а в реальной жизни тупое сравнивание ссылки на следующий элемент с запомненной ссылкой на 1 элемент эффективнее, поскольку использовать зацикленные списки с петлей на конце ни разу не приходилось.
А поскольку вопрос был о самом эффективном алгоритме, я голосую за соответствующую имплементацию метода add, которая всегда знает, будет ли список закольцован

Stanislav · Сообщение **Stanislav** » 31 мар 2007, 21:40

Anry писал(а):
Stanislav писал(а):Вы это серьезно? Прямо в субботу утром?
У меня к вам встречная задача: случайно был удален OU из AD - предложите самый быстрый способ восстановления OU.
Ntdsutil.exe

Ответ неправльный, но вопрос был не про это

Оптимальность каких либо действий сильно зависит от текущих условий и поставленной задачи. Универсальность алгоритма ведет к его неоптимальности. В частности, если в OU только один пользователь, то может проще заново его создать, а если пользователей десятки, то без восстановления из бэкапа не обойтись?

Аман Ванкуверский

Stanislav писал(а):случайно был удален OU из AD - предложите самый быстрый способ восстановления OU.

Stanislav писал(а):В частности, если в OU только один пользователь, то может проще заново его создать ... ?

SID-то будет другой, так что формально это не восстановление

Stanislav · Сообщение **Stanislav** » 31 мар 2007, 22:18

Аман Ванкуверский писал(а):
Stanislav писал(а):случайно был удален OU из AD - предложите самый быстрый способ восстановления OU.

Stanislav писал(а):В частности, если в OU только один пользователь, то может проще заново его создать ... ?
SID-то будет другой, так что формально это не восстановление

Восстановление - это чтобы все работало так же, как и прежде! Не надо усложнять!

При использовании дисков аварийного восстановления SID тоже меняется - однако их не перестают называть дисками аварийного восстановления

Аман Ванкуверский

Stanislav писал(а):
Аман Ванкуверский писал(а):
Stanislav писал(а):случайно был удален OU из AD - предложите самый быстрый способ восстановления OU.

Stanislav писал(а):В частности, если в OU только один пользователь, то может проще заново его создать ... ?
SID-то будет другой, так что формально это не восстановление
Восстановление - это чтобы все работало так же, как и прежде! Не надо усложнять!

"Как прежде" оно работать не будет, в чем Вы убедитесь при первой попытке этого юзера открыть какой-нибудь файл с соответственно настроенными permissons

Stanislav · Сообщение **Stanislav** » 31 мар 2007, 23:58

Аман Ванкуверский писал(а):
Stanislav писал(а):
Аман Ванкуверский писал(а):
Stanislav писал(а):случайно был удален OU из AD - предложите самый быстрый способ восстановления OU.

Stanislav писал(а):В частности, если в OU только один пользователь, то может проще заново его создать ... ?
SID-то будет другой, так что формально это не восстановление
Восстановление - это чтобы все работало так же, как и прежде! Не надо усложнять!
"Как прежде" оно работать не будет, в чем Вы убедитесь при первой попытке этого юзера открыть какой-нибудь файл с соответственно настроенными permissons

Со специально настроенными - вы хотели сказать - Creator/Owner и конкретный аккаунт. А обычно филеи на компе имеют установленные права для Users, куда по умолчанию входят все пользователи домена.

Аман Ванкуверский

Stanislav писал(а):
Аман Ванкуверский писал(а): "Как прежде" оно работать не будет, в чем Вы убедитесь при первой попытке этого юзера открыть какой-нибудь файл с соответственно настроенными permissons
Со специально настроенными - вы хотели сказать - Creator/Owner и конкретный аккаунт. А обычно филеи на компе имеют установленные права для Users, куда по умолчанию входят все пользователи домена.

BMHATK. Не вижу смысла продолжать разговор