Собственно вопрос этот прежде всего для тех, кто участвовал в собеседованиях:
Короче, сегодня побывал на собеседовании на работу "программера-C++ общего
направления".
Ну так вот, собеседователь сначала позагонялся о компиляторах — ну для каких я
пишу — типа "это очень важно", потом с хитренькой ухмылочкой сунул первое
простейшее тестовое задание, на которое дал 5 минут.
Дико интересует (этот вопрос прежде всего для тех, кто проходил собеседования)
как бы вы ответили на, примерно, следующее задание:
Имеется некая большая структура:
_ _ _ _
|_| |_| |_| |_| и т.д.
в которой каждый её элемент может ссылаться на любую другою из этой же
структуры, а последний должен содержать нулевую ссылку.
Выходит это связанный однонаправленный список. Так?
Так, вот, есть баг — последний элемент ссылатся на существующий, а не на нуль.
Т.е. вся структура закольцована.
Задача: найти этот последний элемент структуры. Копировать структуры нельзя,
применять дополнительные средства, типа создать карту элементов, чтобы потом
проверить повторно встречающийся элемент, нельзя.
Оформить это нужно не в виде языка, а показать на пальцах.
Ну вот, примерно такое. Ентим самым местом чую, что для решения подобных проблем
существуют уже готовые паттерны, но я их, увы, не читал.
Очень хотелось бы узнать ваше мнение/решение о таком задании (за такое время и с
бубнящими о каких-то своих указателях кентами за спиной)???
--
Vale, Жмур.
— Люди редко опаздывают туда, где их меньше всего ждут. /Михаил Генин/
Наслаждаюсь "Enya — Pilgrim"... [
[]
Ж>Задача: найти этот последний элемент структуры. Копировать структуры нельзя, Ж>применять дополнительные средства, типа создать карту элементов, чтобы потом Ж>проверить повторно встречающийся элемент, нельзя.
Навскидку надо пустить два итератора по списку — один итерируется нормально, а другой в два раза быстрее. Когда они встретятся — это и будет тот самый последний элемент...
Здравствуйте, Жмур, Вы писали:
Ж>в которой каждый её элемент может ссылаться на любую другою из этой же Ж>структуры, а последний должен содержать нулевую ссылку.
Ж>Выходит это связанный однонаправленный список. Так?
Дык...
Ж>Задача: найти этот последний элемент структуры. Копировать структуры нельзя, Ж>применять дополнительные средства, типа создать карту элементов, чтобы потом Ж>проверить повторно встречающийся элемент, нельзя.
Хм.
Встаём в начало списка. Начинаем по нему бежать, записывая в массив адреса того, что нашли по дороге.
На каждом жаге проверяем, нет ли в массиве совпадающих адресов.
Если есть — алгоритм окончен и на предыдущем шаге нам попался тот самый последний эл-т.
То же самое можно сделать и без массива.
Сложность — n^2, если меня не глючит.
Есть ли более быстрые алгоритмы?
Это не наезды, это вопросы. И вообще, над ламерами смеяться грешно.
Hello, Astaroth!
You wrote on Sat, 19 Jun 2004 12:04:02 GMT:
A> Здравствуйте, Жмур, Вы писали:
[]
A> Встаём в начало списка. Начинаем по нему бежать, записывая в массив адреса того, что нашли по дороге.
Автор говорил, что применять дополнительные средства нельзя.
[]
A> Есть ли более быстрые алгоритмы?
Flamer привел правильное решение. Единственное, навскидку, в этом решении, возможно, придеться учесть четное или нечетное количество элементво в списке.
В mid:686165@news.rsdn.ru от 19.06.2004 (суббота) 16:04 ты писал[а]:
A> Встаём в начало списка. Начинаем по нему бежать, записывая в массив адреса того, что нашли по дороге. A> На каждом жаге проверяем, нет ли в массиве совпадающих адресов. A> Если есть — алгоритм окончен и на предыдущем шаге нам попался тот самый последний эл-т.
Вот примерно-такой же родил и я — ну как после ещё дополнительно оказалось
оказалось, что при поиске нельзя использовать никакой вектор для слежения
(вообще дополнительно выделать память на какую либо структуру).
B всё это должно быть очень эффективно.
A> То же самое можно сделать и без массива.
Мона подробнее?
--
Vale, Жмур.
— А чего ты ожидала? Воплей — "какой ужас"? Я не ханжа. Восторгов? Тоже причин не нахожу. /Леонид. Лабиринт отражений. С. Лукъяненко/
Наслаждаюсь тишиною... \m/
В mid:686162@news.rsdn.ru от 19.06.2004 (суббота) 15:56 ты писал[а]:
F> Навскидку надо пустить два итератора по списку
А когда они встретяться? Можно развёрнутее?
--
Vale, Жмур. mailto:serzh[masyamba]vmail.ru ICQ#: 338-690-194
А есть такое же, но без пуговец и резинки от трусов?
Наслаждаюсь тишиною... \m/
Posted via RSDN NNTP Server 1.8
Re: Очените, плз, задание
От:
Аноним
Дата:
19.06.04 12:43
Оценка:
Здравствуйте, Жмур, Вы писали:
Ж>Задача: найти этот последний элемент структуры. Копировать структуры нельзя,
элементарно:
1. Запомнить указатель на первый элемент
2. Идти по структуре до тех пор, пока ссылка в очередном элементе не будет равна сохраненному указателю.
Здравствуйте, Жмур, Вы писали:
Ж>Salve, Flamer.
Ж>В mid:686162@news.rsdn.ru от 19.06.2004 (суббота) 15:56 ты писал[а]:
F>> Навскидку надо пустить два итератора по списку
Ж>А когда они встретяться? Можно развёрнутее?
Можно.
#include <iostream>
#include <list>
#include <boost/iterator/counting_iterator.hpp>
int main()
{
typedef std::list<int> List;
List list;
std::copy(
boost::counting_iterator<int>(0),
boost::counting_iterator<int>(10), // Меняешь число - получаешь количество элементов в списке
std::back_inserter(list));
List::const_iterator it1 = list.begin();
List::const_iterator it2 = list.begin();
std::advance(it2, 1); // Здесь начинаем с первого
List::const_iterator end = list.end();
for (;;)
{
if (it1 == end)
it1 = list.begin();
if (it2 == end)
it2 = list.begin();
if (it1 == it2)
{
if (list.size() & 1)
{
std::cout << "last element is: " << *it1 << ", check " << *it2 << std::endl;
}
else
{
// Get pervious valueif (it1 == list.begin())
it1 = list.end();
std::advance(it1, -1);
it2 = it1;
std::cout << "last element is: " << *it1 << ", check " << *it2 << std::endl;
}
break;
}
std::cout << "i1 = " << *it1 << ", it2 = " << *it2 << std::endl;
++it1;
if (std::distance(it2, end) > 1)
std::advance(it2, 2);
else
it2 = list.end();
}
}
Если теперь эмуляцию кольцевого списка заменить на настоящий кольцевой список, то алгоритм будет достаточно коротким.
В целом, суть должна быть ясна.
Вот так например. В этоге один из этих элементов ссылается не в нуль, а в снова
el_2. Мы знаем начало, это el_1. А конечный (котя мы-то не можем понять что он
конечный) el_2 ссылается на непервый el_10
--
Vale, Жмур.
— Говорить и писать можно все, что думаешь, но думать следует осторожно. /Hора фон Эльц/
Наслаждаюсь тишиною... \m/
--
Vale, Жмур. mailto:serzh[masyamba]vmail.ru ICQ#: 338-690-194
Создавайте лишь немного законов, но следите за тем, чтобы они соблюдались. /Д. Локк/
Наслаждаюсь тишиною... \m/
Posted via RSDN NNTP Server 1.8
Re[3]: Очените, плз, задание
От:
Аноним
Дата:
19.06.04 20:38
Оценка:
Здравствуйте, Жмур, Вы писали:
Попытаюсь продолжить мысль предыдущего анонима
число элементов структуры = n
1. запоминаем адрес первого элемента
2. идем по структуре, если на n-ом шаге получаем адрес первого элемента, значит n-ый элемент искомый — последний. если нет — пункт 3.
3. раз на n-ом шаге мы не получили адрес первого элемента, значит последний элемент указывает не на первый и соответственно первый элемент из этого кольца выпадает. Повторяем все пункты сначала, но уже без 1го элемента, приняв число элементов структуры n = n — 1.
Ну и при постепенном уменьшении числа элементов n, когда на n-ом шаге получим адрес 1го элемента (первые элементы с каждым проходом тоже меняются) — тогда n-ый элемент и будет последним
Здравствуйте, Жмур, Вы писали:
Ж>Salve, Сергей.
Ж>Увы, не то.
Это как раз то, что от вас хотели...
стандартная задачка из всяких интервью.
А вообще, ВАМ сюда: http://www.techinterview.org
Ж>-- Ж>Vale, Жмур. mailto:serzh[masyamba]vmail.ru ICQ#: 338-690-194 Ж>Создавайте лишь немного законов, но следите за тем, чтобы они соблюдались. /Д. Локк/ Ж>Наслаждаюсь тишиною... \m/
Здравствуйте, Жмур, Вы писали:
Ж>Есть очень интенсивный поток данных (команд например). Его размер может Ж>достигать, например, миллионна записей.
Ж>Данные в него помещаются в произвольном порядке с помощью add.
Ж>Данные в нём ищутся порядке с помощью find.
Ж>Данные из него удаляются с помощью delete.
Ж>Бублирование записей запрещено.
Ж>ЗАДАЧА: разработать ЭФФЕКТИВНЫЙ алгоритм для вставки, поиска, удаления этих Ж>данных.
Ж>Естественно условие ничего не говорить о размерности и формате данных. Пусть Ж>данные — это double (как было предложено мне);
Ж>Итак, какой эффективный алгоритм вы придумаете? Времени на решение задачи в Ж>обрез (ну также, минут 5).
Ж>Есть очень интенсивный поток данных (команд например). Его размер может Ж>достигать, например, миллионна записей.
Данные имеют отношение порядка те их можно сравнивать на больше меньше?
Ж>Данные в него помещаются в произвольном порядке с помощью add.
Ж>Данные в нём ищутся порядке с помощью find.
Это слово какоето левое Ж>Данные из него удаляются с помощью delete.
Ж>Бублирование записей запрещено.
В смысле дублирование?
Ж>Итак, какой эффективный алгоритм вы придумаете? Времени на решение задачи в Ж>обрез (ну также, минут 5).
Ж>Естественно условие ничего не говорить о размерности и формате данных. Пусть Ж>данные — это double (как было предложено мне);
Тогда будем считать что отношение порядка есть.
Тк о переборе элементов контейнера ни чего не сказано то
Вариантов много.
1)Бинарное сбалинсированое дерево
Поиск O(log(N))
Вставка O(log(N))
Удаление O(log(N)) если не удалять элемента, а помечать их как удаленные и иногда перебалансировать дерево.(если кто мне обьяснит как можно из сбалансированого дерева удалить ноду с двумя чилдами и при этом обойтись без полной перебалинсировки дерева я буду очень благодарен)
2)Упорядоченый динамический массив указателей на упорядоченые массивы(фиксированые но с подсчетом элементов считай динамические)
Поиск O(log(N))
Вставка/Удаление O(log(N)) но иногда скачки O(N) с очень маленькой константой
ЗЫ ИМХО надо тему в Алгоритмы снести
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Жмур, Вы писали:
Ж>Salve, Жмур.
Ж>Ладно, сдаётся мне, по первому заданию никто бы не прошёл.
Чем вас мой правильный ответ не устроил?
Ж>Далее, задание второе, у кого есть желание себя или оценить кого-то (меня Ж>например — я же его не здал ):
Ж>Есть очень интенсивный поток данных (команд например). Его размер может Ж>достигать, например, миллионна записей.
Ж>Данные в него помещаются в произвольном порядке с помощью add.
Ж>Данные в нём ищутся порядке с помощью find.
Ж>Данные из него удаляются с помощью delete.
Ж>Бублирование записей запрещено.
Ж>ЗАДАЧА: разработать ЭФФЕКТИВНЫЙ алгоритм для вставки, поиска, удаления этих Ж>данных.
Ж>Естественно условие ничего не говорить о размерности и формате данных. Пусть Ж>данные — это double (как было предложено мне);
Ж>Итак, какой эффективный алгоритм вы придумаете? Времени на решение задачи в Ж>обрез (ну также, минут 5).
Здравствуйте, 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)). Ты забыл про то что элементы массива при вставке придется сдвигать... От сюда и линейная сложность.
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, mikadi, Вы писали:
M>Здравствуйте, Flamer, Вы писали:
F>>Здравствуйте, Жмур, Вы писали:
F>>[]
Ж>>>Задача: найти этот последний элемент структуры. Копировать структуры нельзя, Ж>>>применять дополнительные средства, типа создать карту элементов, чтобы потом Ж>>>проверить повторно встречающийся элемент, нельзя.
F>>Навскидку надо пустить два итератора по списку — один итерируется нормально, а другой в два раза быстрее. Когда они встретятся — это и будет тот самый последний элемент...
M>Что-то я тоже не понял алгоритм. M>А как он сработает в таком случае: a->b->c->d->e->b ? Итераторы встретятся на b, если я правильно понимаю алгоритм...
Все правильно, итераторы встретятся на b. Мы нашли закольцовку, не так-ли? Т.е. мы нашли тот элемент, который должен быть последним в списке, но по какой-то причине указывает на другой элемент.
А постановка задачи "найти последний элемент в кольцевом списке", имхо, бессмысленна. Что есть "последний элемент" в кольцевом списке?
F> А постановка задачи "найти последний элемент в кольцевом списке", имхо, F> бессмысленна. Что есть "последний элемент" в кольцевом списке?
По условию, есть список. Он может быть закольцован. Надо убедиться, что он
закольцован/не закольцован и найти тот сбойный элемент. Таково вот задание.
Выходит собеседователь решил, у компания не хуже MS и решил, задать вопрос,
который был использован на http://www.techinterview.org — но, увы, не совсем
также его сформулировал.
--
Vale, Жмур. mailto:serzh[masyamba]vmail.ru ICQ#: 338-690-194
Подозрений у человека тем больше, чем меньше он знает. /Ф. Бэкон/
Наслаждаюсь тишиною... \m/
В 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) Определить его последний элемент.
Время не ограничивают.
Re[2]: Очените, плз, задание
От:
Аноним
Дата:
22.06.04 12:39
Оценка:
Здравствуйте, Flamer, Вы писали:
F>Здравствуйте, Жмур, Вы писали:
F>Навскидку надо пустить два итератора по списку — один итерируется нормально, а другой в два раза быстрее. Когда они встретятся — это и будет тот самый последний элемент...
Это было бы верно если бы было известно, что последний элемент указывает на первый. Но сказано, что он указывает на некий произвольный элемент списка.
От 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к)
Хе-хе. А мне такое в питерской Аэлите попалось, собеседовался на "С++ стажер".
Потом Кнута перелистовал, полагая что дурак и совсем классики не знаю
(Саша, без притензий хоть не скучно было )
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/
Ж>Задача: найти этот последний элемент структуры. Копировать структуры нельзя, Ж>применять дополнительные средства, типа создать карту элементов, чтобы потом Ж>проверить повторно встречающийся элемент, нельзя.
Ж>Оформить это нужно не в виде языка, а показать на пальцах.
Ну если на пальцах, то вот более рациональное и соответсвующее условию, имхо, решение, чем то что приводил Flamer. Его решение находит только закольцован список или нет. Потом еще дополнительно нужно будет искать последний элемент.
Я опущу проверку на закольцованость, которую добавить не трудно (понадобятся: память на хранение адреса первого элемента и пара if-ов), тем более что в условии ясно сказано что список закольцован. Сделаем так: будем идти по списку и менять направление ссылок на обратное, при этом первый элемент сошлем на "нулевой". При этом будем вести счетчик пройденых элементов списка.
То есть, если начальный список будет такой:
a -> b -> c -> d -> e -> f -> c
То после нескольких итераций он станет таким(при этом мы сейчас рассматриваем пару элементов d-e):
a <- b <- c <- d -> e -> f -> c
Дойдя до "конца" списка получим:
a <- b <- c <- d <- e <- f -> c
После чего продолжаем идти по ссылкам и менять их на "противоположные". Дойдя до начала(то есть элемента который ссылается на "нулевой элемент") мы получим такую структуру:
a -> b -> c <- d <- e <- f <- c
Вот тут, кстати говоря, и нужно, если что сделать проверку на закольцованость: достаточно сравнить адреса пары элементов: ссылющегося на "нулевой" элемент и начального, сохраненного нами в самом начале. Если совпадают — закольцован, нет — линеен.
Заметим, что после данного прохода в счетчике мы получили некое число, которое, если разобратся, равно 2k+p, где p-кол-во элементов в цикле, а к-кол-во элементов не входящих в цикл. Обозначим его C(count). После этого пройдем по списку C шагов не меняя ничего. При этом мы окажемся где-то внутри цикла. После этого нам осталось запомнить адрес текужего элемента и пройтись полностью по циклу — до попадания на этот же элемент, при этом подсчитывая шаги в новом счетчике. Мы получили p. Теперь совсем не сложно вычислить k=(c-p)/2. Теперь мы знаем номер элемента(если считать от начала), который "начинает" список. Также у нас есть адрес первого элемента — так что найти нужный нам элемент труда не состовляет.
Вот и все. На все про все понадобилось 2*(2*k+p)+p шагов, а также несколько дополнительных байт памяти.
1)Берем 1-й элемент смотрим валидна ли ссылка 1-го элемента.
2)Если связь валидна то сохраняем 1-й элемент в качестве последнего елемента с валидной сслыкой.
3)Переходим к элементу на который ссылается 1-й элемент
4)и рвем связь между 1-м элементом и тем на который перешли.
5)Далее проделываем тоже самое с элементом на который перешли.
6)Делаем 1-5 до тех пор пока не окажется, что текущий элемент никуда не ссылается.
7)По выходу из цикла мы будем иметь последный(искомый) элемент, как последний элемент, который на что-то
ссылался.
Здравствуйте, Jakop, Вы писали:
J>Здравствуйте, Жмур, Вы писали:
J>[skip] J>Это делается помоему так:
J>1)Берем 1-й элемент смотрим валидна ли ссылка 1-го элемента. J>2)Если связь валидна то сохраняем 1-й элемент в качестве последнего елемента с валидной сслыкой. J>3)Переходим к элементу на который ссылается 1-й элемент J>4)и рвем связь между 1-м элементом и тем на который перешли. J>5)Далее проделываем тоже самое с элементом на который перешли. J>6)Делаем 1-5 до тех пор пока не окажется, что текущий элемент никуда не ссылается. J>7)По выходу из цикла мы будем иметь последный(искомый) элемент, как последний элемент, который на что-то J>ссылался.
J>Вот он то и будет искомым
Кстати предупреждая недовольные высказывания типа "Да он же портит список... " итд
хочу сказать ,что
1)в условии задачи сказано всегда ровно то что требуется сделать,
2)теми средствами , которыми это можно сделать и с
3)теми ограничениями которые налагаются на решение.
Не больше не меньше.
Здравствуйте, Jakop, Вы писали:
J>Здравствуйте, Жмур, Вы писали:
J>[skip] J>Это делается помоему так:
J>1)Берем 1-й элемент смотрим валидна ли ссылка 1-го элемента. J>2)Если связь валидна то сохраняем 1-й элемент в качестве последнего елемента с валидной сслыкой. J>3)Переходим к элементу на который ссылается 1-й элемент J>4)и рвем связь между 1-м элементом и тем на который перешли. J>5)Далее проделываем тоже самое с элементом на который перешли. J>6)Делаем 1-5 до тех пор пока не окажется, что текущий элемент никуда не ссылается. J>7)По выходу из цикла мы будем иметь последный(искомый) элемент, как последний элемент, который на что-то J>ссылался.
J>Вот он то и будет искомым
Да вот еще....для того, чтобы определить закольцовал ли список нужно просто проверить ссылается ли текущий елемент на чтонибудь. И если не ссылается — то список не закольцован выходим из цикла.
A>> Встаём в начало списка. Начинаем по нему бежать, записывая в массив адреса того, что нашли по дороге. A>> На каждом жаге проверяем, нет ли в массиве совпадающих адресов. A>> Если есть — алгоритм окончен и на предыдущем шаге нам попался тот самый последний эл-т.
Ж>Вот примерно-такой же родил и я — ну как после ещё дополнительно оказалось Ж>оказалось, что при поиске нельзя использовать никакой вектор для слежения Ж>(вообще дополнительно выделать память на какую либо структуру).
A>> То же самое можно сделать и без массива.
Ж>Мона подробнее?
Вместо дополнительного массива использовать этот же самый список.
Ж>B всё это должно быть очень эффективно.
Здравствуйте, Жмур, Вы писали:
Ж> Чесслово не вру, без преукраски. Очень солидная Ж>фирма. Гы-гы.
Что за контора?
... << RSDN@Home 1.1.4 @@subversion >>
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius — and a lot of courage — to move in the opposite direction. -- Albert Einstein
А задача рассчитана чисто на логическое мышление... От программирования там ничего нету 
