Собственно вопрос этот прежде всего для тех, кто участвовал в собеседованиях:
Короче, сегодня побывал на собеседовании на работу "программера-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).
