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

Это сообщение отредактировал(а) J0ker - 15.11.2008, 02:30

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

далее проделываем операции 1-6 с 2-мя, 3-мя, ... , n элементами, пока на шаге 6 мы не обнаружим разные элементы
при необходимости восстанавливаем положение нижних элементов

Добавлено через 2 минуты и 53 секунды
ЗЫЖ да, и с хонойской башней я там перемудрил - сортируется гораздо проще... не подумав ляпнул, сорри

Это сообщение отредактировал(а) J0ker - 15.11.2008, 03:22

проверять себя (метку) по указателю можно ?

делаем по списку N шагов, ставим метку и  идем дальше столько же шагов, 
если ни конец, ни метка не встретились - увеличиваем N нa M, переносим метку  и повторяем сначала.
попав в петлю мы оттуда не выберемся, и найдется она тогда, когда N будет больше длины петли.

оптимальнее будет использовать не одну, а несколько меток, сколько позволит доп. память.


Это сообщение отредактировал(а) mes - 15.11.2008, 05:20

идея правильная, но не оптимальная


даю подсказку - двух достаточно, необходимо N и M выразить конкретнее   

в буфере у нас первый элемент 

вот для примера содержимое очереди :  1,2,1,2,3,1,2,3,1 

ну получили мы 1..

и как узнать при каком 1 у нас сннова первый элемент ?

Добавлено через 7 минут и 37 секунд

предполагаем что длина списка Х,  тогда N = X/2, метки одна вначале другая в середине.
если не угадали, предполагаем, что  размер (думаю) в два раза больше, увеличиваем соответственно N и аналогично переставляем метки.

ага.

буду использовать словосочетание "идем с начала конец " как циклический pop_first и push_back 
и слово "возвращаемся" как обратные действия.




Это сообщение отредактировал(а) mes - 15.11.2008, 12:37

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

Починить список   

надо взять на вооружение.. в эту сторону я не думал. )

J0ker, я не понял задачу про список. Во-первых, какие методы доступны, явно не указано. Если итератор мы можем создать, то, как я понимаю, begin() доступен? И end() тоже? А почему тогда size() недоступен? И потом, если этот список у нас такой странный, что содержит петлю внутри, где гарантия, что next() работает правильно? Как-то задача изначально нечётко поставлена. И что означает починить? Разорвать цикл, но при этом смириться с тем, что хвост потерян безвозвратно? Что нам известно, можем ли мы как-то повлиять на результат, возвращаемый методом end()?

Отвечу вместо автора : 



J0ker, надеюсь я правильно изложил   



Это сообщение отредактировал(а) mes - 16.11.2008, 12:46

Добавлено через 3 минуты и 13 секунд

последний элемент должен указывать в NULL (ну или в специальный итератор end)


он не будет потерян
нарисуйте себе картинку и подумайте

Добавлено через 4 минуты и 34 секунды

да правильно

Этот вопрос задаю на понимание , что такое lvalue / rvalue
Вопрос задается в следующим виде.

Будет различаться результаты работы двух фрагментов кода и если будут, то почему?


и


Добавлено @ 19:32
Один из стандартных вопросов: рассказать, существуют ли какие либо особенности, которые нужно учитывать, при вызове виртуальных функций в конструкторе и деструкторе.

Как  в производном класса  без переопределения   "открыть" ( сделать public )   метод, защищенный(  protected )  в базовом классе классе

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

Результат работы программы