Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, GUID, Вы писали:

GUI>>Динамический сортированный вектор? <Если, конечно, я правильно понял что-такое "бублирвание запрещено" >
WH>Вставка/удаление линейны.

Поскольку массив сотрированный, то вставка/удаление реализуются через поиск методом двоичного деления, т.е. они имеют временную сложность O(ln2(n)).

Здравствуйте, Flamer, Вы писали:

F>Здравствуйте, Жмур, Вы писали:

F>[]

Ж>>Задача: найти этот последний элемент структуры. Копировать структуры нельзя,
Ж>>применять дополнительные средства, типа создать карту элементов, чтобы потом
Ж>>проверить повторно встречающийся элемент, нельзя.

F>Навскидку надо пустить два итератора по списку — один итерируется нормально, а другой в два раза быстрее. Когда они встретятся — это и будет тот самый последний элемент...

Что-то я тоже не понял алгоритм.
А как он сработает в таком случае: a->b->c->d->e->b ? Итераторы встретятся на b, если я правильно понимаю алгоритм...

Мне самому навскидку приходит в голову только такое неэлегантное решение.
Все элементы списка можно разделить на две категории — "линейные" (те, через которые не проходит цикл) и "циклические", причем линейные располагаются строго до циклических, если идти от начала. Тогда искомый элемент — это тот, который указывает на первый циклический (e указывает на b в моем примере). Поэтому мы в цикле перебираем все элементы и для каждого (обозначим его X) двумя итераторами (по предложенной вами схеме) пробегаем дальше по списку. При таком пробеге мы либо в какой-то момент получим указатель на X, либо итераторы встретятся, так и не пройдя через X. В первом случае искомый элемент — это тот, с которого мы пришли в X, во втором случае X является линейным и мы продолжаем поиск. Сложность — O(n^2).

Здравствуйте, GUID, Вы писали:

GUI>Поскольку массив сотрированный, то вставка/удаление реализуются через поиск методом двоичного деления, т.е. они имеют временную сложность O(ln2(n)).
Ты забыл про то что элементы массива при вставке придется сдвигать... От сюда и линейная сложность.

Здравствуйте, mikadi, Вы писали:

M>Здравствуйте, Flamer, Вы писали:

F>>Здравствуйте, Жмур, Вы писали:

F>>[]

Ж>>>Задача: найти этот последний элемент структуры. Копировать структуры нельзя,
Ж>>>применять дополнительные средства, типа создать карту элементов, чтобы потом
Ж>>>проверить повторно встречающийся элемент, нельзя.

F>>Навскидку надо пустить два итератора по списку — один итерируется нормально, а другой в два раза быстрее. Когда они встретятся — это и будет тот самый последний элемент...

M>Что-то я тоже не понял алгоритм.
M>А как он сработает в таком случае: a->b->c->d->e->b ? Итераторы встретятся на b, если я правильно понимаю алгоритм...

Все правильно, итераторы встретятся на b. Мы нашли закольцовку, не так-ли? Т.е. мы нашли тот элемент, который должен быть последним в списке, но по какой-то причине указывает на другой элемент.

А постановка задачи "найти последний элемент в кольцевом списке", имхо, бессмысленна. Что есть "последний элемент" в кольцевом списке?

Salve, Flamer.

В mid:687975@news.rsdn.ru от 21.06.2004 (понедельник) 16:41 ты писал[а]:


F> А постановка задачи "найти последний элемент в кольцевом списке", имхо,
F> бессмысленна. Что есть "последний элемент" в кольцевом списке?

По условию, есть список. Он может быть закольцован. Надо убедиться, что он
закольцован/не закольцован и найти тот сбойный элемент. Таково вот задание.
Выходит собеседователь решил, у компания не хуже MS и решил, задать вопрос,
который был использован на http://www.techinterview.org — но, увы, не совсем
также его сформулировал.

--
Vale, Жмур. mailto:serzh[masyamba]vmail.ru ICQ#: 338-690-194
Подозрений у человека тем больше, чем меньше он знает. /Ф. Бэкон/
Наслаждаюсь тишиною... \m/

Salve, _AK_.

В mid:686807@news.rsdn.ru от 20.06.2004 (воскресенье) 19:55 ты писал[а]:

_> Очень халявные задания.

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

--
Vale, Жмур. mailto:serzh[masyamba]vmail.ru ICQ#: 338-690-194
Колкость глаз не колет. /Пираты карибского моря. Джек Воробей/
Наслаждаюсь тишиною... \m/

Здравствуйте, Жмур, Вы писали:

Ж>Salve, Flamer.

Ж>В mid:687975@news.rsdn.ru от 21.06.2004 (понедельник) 16:41 ты писал[а]:


F>> А постановка задачи "найти последний элемент в кольцевом списке", имхо,
F>> бессмысленна. Что есть "последний элемент" в кольцевом списке?

Ж>По условию, есть список. Он может быть закольцован. Надо убедиться, что он
Ж>закольцован/не закольцован и найти тот сбойный элемент. Таково вот задание.
Ж>Выходит собеседователь решил, у компания не хуже MS и решил, задать вопрос,
Ж>который был использован на http://www.techinterview.org — но, увы, не совсем
Ж>также его сформулировал.

Ну так тем более выходит, что приведенное мной решение — верное А задача рассчитана чисто на логическое мышление... От программирования там ничего нету

Здравствуйте, Flamer, Вы писали:

F>Здравствуйте, Жмур, Вы писали:

Ж>>Salve, Flamer.

Ж>>В mid:687975@news.rsdn.ru от 21.06.2004 (понедельник) 16:41 ты писал[а]:


F>>> А постановка задачи "найти последний элемент в кольцевом списке", имхо,
F>>> бессмысленна. Что есть "последний элемент" в кольцевом списке?

Ж>>По условию, есть список. Он может быть закольцован. Надо убедиться, что он
Ж>>закольцован/не закольцован и найти тот сбойный элемент. Таково вот задание.
Ж>>Выходит собеседователь решил, у компания не хуже MS и решил, задать вопрос,
Ж>>который был использован на http://www.techinterview.org — но, увы, не совсем
Ж>>также его сформулировал.

F>Ну так тем более выходит, что приведенное мной решение — верное А задача рассчитана чисто на логическое мышление... От программирования там ничего нету

Она то на логическое решение, только догадаться до него — совершенно не просто. Такие вопросы вообще задают на интервью в довольно солидные компании...
тут интервьюверы немного переборщили (Если они не собирались, конечно, вам платить скажем 2-3-4к)

Здравствуйте, Flamer, Вы писали:

M>>Что-то я тоже не понял алгоритм.
M>>А как он сработает в таком случае: a->b->c->d->e->b ? Итераторы встретятся на b, если я правильно понимаю алгоритм...

F>Все правильно, итераторы встретятся на b. Мы нашли закольцовку, не так-ли? Т.е. мы нашли тот элемент, который должен быть последним в списке, но по какой-то причине указывает на другой элемент.

Так это вроде должен быть e. Он ведь последний (еще не пройденный), если идти от выделенного начального элемента (a).

F>А постановка задачи "найти последний элемент в кольцевом списке", имхо, бессмысленна. Что есть "последний элемент" в кольцевом списке?

Наверное, я неверно понял задачу — я понял ее именно так, как ее описал Жмур. Т.е. что зацикливание списка — это дефект, а по сути список должен быть линейным. При такой постановке можно найти дефектный элемент — он указывает на ранее пройденный элемент (все предыдущие указывают на новый элемент).

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

Здравствуйте, Жмур, Вы писали:

Ж>Salve, _AK_.

Ж>В mid:686807@news.rsdn.ru от 20.06.2004 (воскресенье) 19:55 ты писал[а]:

_>> Очень халявные задания.

Ж>Возможно... В таком случае я делаю выводы, что писать проги, без оперативного
Ж>решения этих задач именно таким способом, я не могу. Т.е. выходит, что не могу
Ж>писать их совсем. Гы-гы.

Ж>--
Ж>Vale, Жмур. mailto:serzh[masyamba]vmail.ru ICQ#: 338-690-194
Ж>Колкость глаз не колет. /Пираты карибского моря. Джек Воробей/
Ж>Наслаждаюсь тишиною... \m/

С первым ещё могу согласиться — это скорее академическая задача

Но вот второй вопрос — очень хороший и правильный вопрос: если ты неадекватно выберешь структуру данных, то потом можешь огрести по полной программе. Поверь мне далеко не все все пишут простенькие приложения, в которых данные можно хранить чёрти в чём — и ничего тормозить не будет... Если не веришь я тебе могу привести пример (причём не надуманный с какими-то мифичесикми оптимизациями, а из жизни — где смена структуры данных ускорила скорость выполнения программы в сотни раз).

Здравствуйте, Жмур, Вы писали:

Это одна из известных микрософтских задач на списки.
За 5 минут в такой постановке и стрессовой ситуации ее не решает почти никто.
В микрософте ее дают так:
1) Сначала надо определить, закольцован список, или нет.
2) Определить его последний элемент.
Время не ограничивают.

Здравствуйте, Flamer, Вы писали:

F>Здравствуйте, Жмур, Вы писали:

F>Навскидку надо пустить два итератора по списку — один итерируется нормально, а другой в два раза быстрее. Когда они встретятся — это и будет тот самый последний элемент...

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

Salve, _AK_.

От 22.06.2004 (вторник) 12:24 ты писал[а]:

_> Но вот второй вопрос — очень хороший и правильный вопрос: если ты неадекватно
_> выберешь структуру данных, то потом можешь огрести по полной программе.

Насчёт второго я ничего не имею против — но, если бы мне пришлось писать такой
поток, как во втором задании, то я сначала должен для чего он — т.е. сколько
можно уделить внимания эффективности структуры, а сколько остальному коду. Если
эффективность главное, то для перепробовал бы несколько вариантов. Ведь это не
аксиома, что бинарное дерево лучше всего для любого типа данных.

--
Vale, Жмур. mailto:serzh[masyamba]vmail.ru ICQ#: 338-690-194
— Hаши добродетели это чаще всего переряженные пороки. /Франсуа де Ларошфуко/
Наслаждаюсь тишиною... \m/

Здравствуйте, Gaperton, Вы писали:

G>Это одна из известных микрософтских задач на списки.
G>За 5 минут в такой постановке и стрессовой ситуации ее не решает почти никто.

Решают, если заранее знают решение

Здравствуйте, Жмур, Вы писали:

Ж>Salve, All.

Ж>Имеется некая большая структура:

Ж> _ _ _ _
Ж>|_| |_| |_| |_| и т.д.

Ж>в которой каждый её элемент может ссылаться на любую другою из этой же
Ж>структуры, а последний должен содержать нулевую ссылку.

Ж>Выходит это связанный однонаправленный список. Так?
Помоему не так.
Пусть есть елементы 1,2,3,4,5
1->2, 2->1, 3->4, 4->3, 5->NULL
Получилось 2 цикла, а не один однонаправленный список.
А в общем случае там может быть несколько циклов с подходами
и одно дерево (если не ошибаюсь в терминологии, давно графы изучал) с корнем уходящим в NULL.
Или я не прав?

Здравствуйте, Flamer, Вы писали:

F>Навскидку надо пустить два итератора по списку — один итерируется нормально, а другой в два раза быстрее. Когда они встретятся — это и будет тот самый последний элемент...

С помощью этого трюка мы всего лишь определим наличие цикла.

Здравствуйте, Andy77, Вы писали:

A>С помощью этого трюка мы всего лишь определим наличие цикла.

Так как в условии не требуется эффективное решение, можем запустить паровозики первый раз, определив длину цикла, и потом запускать их, уменьшая максимальный путь медленного на единицу каждый раз до тех пор, пока цикл не пропадёт Ну или применить мега-метод "деление отрезка пополам"

Здравствуйте, Жмур, Вы писали:

Вот решение за время <const*length, с двумя итераторами и двумя переменными.

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

Считаем кол-во шагов, которые сделает _второй_ итератор между _первым_ и _вторым_ совпадением положения итераторов (не считая начального состояния).

Эта величина бкдет равна длине _циклической_ части списка. Запоминаем ее.

Запускаем от начала два итератора, один на длину цикла шагов впереди первого и с одинаковой скоростью. Их положение совпадет через кол-во шагов, равное длине _линейной_ части списка. Итератор, шедший первым перед этим шагом находилмся на "последней" ячейке списке.


А вообще это классическая олимпиадная задача "для своих". Те, кто знает стандартный прием с итераторами с разной скоростью, ее решат. Остальные — вряд ли.

F>> Ну так тем более выходит, что приведенное мной решение — верное А
F>> задача рассчитана чисто на логическое мышление... От программирования
F>> там ничего нету

w> Она то на логическое решение, только догадаться до него — совершенно не
w> просто. Такие вопросы вообще задают на интервью в довольно солидные
w> компании... тут интервьюверы немного переборщили (Если они не
w> собирались, конечно, вам платить скажем 2-3-4к)

Хе-хе. А мне такое в питерской Аэлите попалось, собеседовался на "С++ стажер".
Потом Кнута перелистовал, полагая что дурак и совсем классики не знаю
(Саша, без притензий хоть не скучно было )

Salve, www.

22.06.2004 (вторник) 6:18 ты писал[а]:

w> Такие вопросы вообще задают на интервью в довольно солидные компании... тут
w> интервьюверы немного переборщили (Если они не собирались, конечно, вам
w> платить скажем 2-3-4к)

Ага, я целых минут сорок искал тот "проспект" (на самом деле проспект N) — а
оказалось грязный узкий переулок, где даже машины очень редко ездят. Потом искал
оффис — оказалась комнатка 9x5 метров (правда компы на вид не плохие с LCD и у
главного ноут) с шестью челами (явными недавними выпускниками ВУЗов) спорящими
куда им указатель поставить "взад" или "вперёд". . В высоком ГРЯЗНОМ и
разваливающемся (с большой буквы) здании какого-то бывшего завода, который сдаёт
себя в аренду всем подряд. Чесслово не вру, без преукраски. Очень солидная
фирма. Гы-гы.

У меня вообще сложилось впечатление, что они просто так мне позвонили — от
нечего делать, а брать на работу и не хотели. :/

А зарплата ожидалась ОТ 6000 р. %( Мля... Знал бы — лучше бы дома это утро
проспал.

--
Vale, Жмур. mailto:serzh[masyamba]vmail.ru ICQ#: 338-690-194
Пока летишь с обрыва, внизу ещё могут кусты вырасти. /Унди Мышатник. Идущие в ночь. А. Китаева, В. Васильев, А. Лайк/
Наслаждаюсь тишиною... \m/