Сегодня был озадачен следующим вопросом (у нас его иногда задают на интервью), требующим потенциально ответа в 5-10 минут, желательно с примером кода.
Найти середину связного списка за один проход. Длина заранее не известна, а есть только указатель на голову.
Кто не догадается, смотрите комментарии. Уверен, там задачу быстро "возьмут".
Задача очень жизненная, и реально полезно знать решение.
Как научиться решать задачи подобного рода? алгоритмические программистские задачи? В чем суть обучения?
Есть определенная категория программистов, которым я профессионально завидую. Это бойцы спортивного программирования типа TopCoder'а, Google Code Jam'а и прочих контестов. Для которых что-то вроде поиска цепочек в частично упорядоченном множестве как для меня сложить две переменные. Там, где мне надо открыть книгу или хотя бы Википедию, они это пишут сходу из головы.
Из личного опыта, перед некоторыми интервью, я мог на память сходу написать любую базовую сортировку, вставку в красно-черное дерево, послойный обход дерева и многое другое. Но проблема в том, что это ни разу не помогало на интервью! Все что я в итоге решал (или не решал), было связанно с задачами, которые могли быть в разы проще любой сортировки или дерева, но требовали "догадаться". И основном спортивное программирование построено на теме "догадаться как".
Но как научиться догадываться? Есть ли какая-то методика обучения? Именно методика, а не "решай все подряд, и все тебе будет". Второй подход, конечно, работает, но методика могла бы ускорить процесс, сделать его более эффективным.
Например, взять физику или математику. Обычно ты учишь теорию и ее отражение на физический мир вокруг нас, учишь уже выведенные законы, теоремы (возможно их доказательства) и построенные на них базовые формулы. Далее при решении конкретной задачи ты, основываясь на выученных основах, пытаешься понять, что за физическая или математическая модель могла бы иметь место в задаче. Далее пытаешься приложить эту модель и смотришь, что получается (или не получается).
То есть тут есть методика, которая помогает тебе найти связь между теорией и задачей. Конечно, есть задачи, в которых "надо догадаться", но это как опция, нежели норма. Тебе дается инструмент, когда зная малое, можно решать многое.
В нашем же программистском мире, как мне кажется, все из серии "надо догадаться". Взять, например, эту задачу про поиск середины связного списка в один проход. Я могу изучить всё про такие списки: как их строить, как их сортировать, как их обходить (просто линейно) и т.д. Но все эти знания не подвинут меня ни шаг к решению этой простой задачи. Тут надо "просто догадаться". Как научить догадываться? Неужели есть только один путь - решать и решать, пока количество не перейдет в качество, и ты будешь легко решать задачи на "догадаться" просто потому, что ты это уже так или иначе видел раньше.
Кстати, сравним среднего выпускника MIT и МАИ (я там учился). Наверное, выпускник MIT потенциально "сильнее" выпускника МАИ (при всей моей любви и уважении к Альма-матер). Почему? Там книги другие? Там профессора хуже? Я не могу пожаловаться, что мой курс программирования, где изучались алгоритмы был недостаточен.
Пока у меня только одно объяснение - скажем так, в объективно престижных ВУЗах просто больше прессуют и фактически заставляют учиться (иначе - это пустая трата денег и большой шанс вылететь).
Выходит, что количество так или иначе переходит в качество. И никакой магии.
пятница, 16 апреля 2010 г.
Подписаться на:
Комментарии к сообщению (Atom)
Сообщения
Два итератора, оба начинаются с начала списка.
ОтветитьУдалитьНа каждые две итерации первого - делаем одну итерацию второго.
Как первый дойдёт до конца, второй будет указывать на середину.
> Тут надо "просто догадаться". Как научить догадываться?
ОтветитьУдалитьТут надо использовать принцип разделяй и властвуй, делим список на две части - обработанную и не обработанную. Вначале, обработанная часть списка состоит из одного элемента, который у нас одновременно и середина списка и граничный элемент. Далее, нужно придумать способ так передвигать граничный элемент, что-бы всегда знать середину обработанной части списка. Лично я размышлял так, и пришел к такому же решению, что и Qehgt.
А как вы "догадались", что нужен принципе разделяй и властвуй?
ОтветитьУдалитьА вот строго говоря, при таком подходе список проходится 1,5 раза: 1 раз первым итератором и 0,5 раза вторым итератором. Можно ли это считать решением "за один проход"?
ОтветитьУдалитьЯ думаю, что проблема с программистскими задачами как раз в том, что сама задача формулируется весьма туманно, типа "нужно сделать вот такую хрень". И в реальности по мере реализации новой хрени всплывают всё новые и новыё бизнес-подробности и нюансы и продукт неизбежно эволюционирует.
Поэтому решать быстро олимпиадные задачи -- это для разминки мозга. А вот решать бизнес-задачи правильно -- не всегда нужно быстро. Или я не прав?
bialix: На счет итераторов - по большому счету, вы правы. Физически при таком подходе первый итератор прощелкает n раз, а второй - n/2 раз. В сумме 1.5*n. И не будет особой разницы, если просто пройти в одну сторону, посчитать количество, а потом пройти еще раз до половины, то будет тоже 1.5*n итераций.
ОтветитьУдалитьНо если делать таки в один цикл, то может кеш будет лучше использоваться, или может какие-то инструкции спарятся или что-то еще.
А по поводу программистких задач я не согласен. Например, Stock Charts про построение непересекающихся графиков, например, курсов валют.
Абсолютно жизненная задача для моей предметной области. Я как-то взялся за нее, пару дней покопался, и таки глянул в ответ. Сначала я думал типа вот блин посмотрю ответ, а потом буду жалеть, ибо там все просто и "надо было догадаться". Но нифига: я потом ответ грыз еще несколько дней (поиск цепочек в DAGе, частично отсортированные множества и.д.). Хотя официальный судейский вариант решения - программа с пару десятков строк! На самом контесте эта задачка должна была решаться менее чем за два часа, я на нее убил более недели. Вот и подумаешь - кто-то может решить эту реальную задачу из жизни за час, а кто-то за неделю. Чья производительность на выше на работе?
Решать быстро - не значит плохо. Архитектура, дизайн - это да, тут не следует порой торопиться. Но когда доходит просто до алгоритмической реализации, тут сложно отрицать, что скорость имеет значение, а большая скорость - особенно.
Если в списке четное количество элементов, то середины нет. Задача с подвохом.
ОтветитьУдалитьЗапустить итераторы с обоих концов и сравнивать их разницу на 0(нечетное число элементов) или 1(четное число элементов). Как раз и будет один проход, только с разных концов )
ОтветитьУдалить> Это бойцы спортивного программирования типа TopCoder'а, Google Code Jam'а и прочих контестов.
ОтветитьУдалитьвот тут все их секреты
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index
oyefremov: Спасибо за ссылку.
ОтветитьУдалить@Optimisto: такой подход сработает только если список двусвязный. А из условия задачи это не очевидно.
ОтветитьУдалитьТак решение в 1.5N принимается или нужно в N?
ОтветитьУдалитьПо хорошему, N тут не будет вообще.
ОтветитьУдалитьА если при проходе итератора запоминать каждый элемент списка? Например, сохранять указатели в векторе. Когда итератор дойдет до конца - узнаем длину списка n, и выбираем, соответственно, (n/2)-й элемент-указатель из вектора, который и будет указывать на середину списка.
ОтветитьУдалитьПравда, если длина списка будет большой, то понадобится такой же длины вектор ..)
Есть несколько простых соотношений, которые помогают "догадываться". Например, известнейший факт, что сложность алгоритма обычно уменьшается за счёт увеличения использования памяти.
ОтветитьУдалитьТ.е., в данном случае мы имеем очевидное решение - за один проход получаем длину списка, за второй - находим середину.
Вспомнив, что скорость повышается за счёт использования памяти, вполне валидное решение, которое приходит на ум - сохранять все элементы в векторе.
O(1.5n) = O(C*n) = O(n).
ОтветитьУдалитьесть сильное подозрение, что "в 1 проход", не используя доп. контейнер и не зная длинну листа нельзя найти середину ввиду O(n) сложности выборки элемента из листа.
Используя контейнер можно балансировать между "за 1 проход" и "за полтора прохода в худшем случае" (:
Или я не понимаю условия задачи или тут все слишком просто. Простите за темноту, если что, но мне кажется, что если есть однонаправленный список, то нам понадобятся два указателя: P1 и P2.
ОтветитьУдалитьВ итерации сдвигаем указатель P1 на два элемента, а P2 на один. К моменту когда P1 достигнет конца списка (только нужно проверять, чтобы он не вышел за пределы, но это зависит от реализации) P2 будет указывать на середину.
В целом -- да, использование быстрого и медленного указателей в целом не дадут реального ускорения по сравнению с просто проходом туда и подсчетом элементов и потом проходом до половины назад.
ОтветитьУдалитьТак, а решение с хранением индексированного массива указателей на все элементы списка, как предложил KAHuCTPA подойдет?
ОтветитьУдалитьИли есть более компактное решение? В условии не сказано о том сколько нужно занять памяти, так что уточните этот момент, пжлста.
Хотя, если рассматривать последующий поиск в индексированном массиве указателей элемента с номером n/2, то снова получится 1,5 прохода. Я правильно понял?
Решение от KAHuCTPA вполне себе здравое, если прочие условия позволяют. Вообще, это задача предназначена для интервью, поэтому ее условия можно варьировать как нравится.
ОтветитьУдалитьЕсли бы ее задавал лично я, меня бы удовлетворил и простой проход до конца и потом назад до середины, и прием с двумя указателями, если будет пояснение, почему количество итераций тут будет одинаковое.
ОтветитьУдалитьОдинаковое где и где?
ОтветитьУдалитьЕсли речь о том, что количество "итераций" в варианте с "быстрым" и "медленным" указателем одинаковое с количеством "итераций" в проходе вперед и назад до середины, то тут все очевидно. Непосредственно проходов цикла в варианте быстрый-медленный - одна, но в каждой итерации этого цикла машина выполняет три "атома" "получение адреса следующего элемента списка". Дважды выполняется "атом" для быстрого указателя, так как в связанном списке нельзя перепрыгивать _через_ элемент и один раз для медленного. Итераций цикла будет N/2, а "атомов" всего (N/2)*3=1,5*N. А для метода вперед-назад в одной итерации цикла находится всего один "атом", но этих итераций будет, как уже говорили 1,5*N
ОтветитьУдалитьТ.е. разницы или выигрыша в производительности нет.
Но все-таки интересно _существует_ ли решение без хранения набора адресов в индексированном массиве и при этом в N итераций?
Я думаю, что вариант с быстрым и медленным указателем может быть быстрее за счёт особенностей архитектуры процессора. Их тут две: одновременное выполнение комманд для передвижения обоих указателей и оптимизация чтения памяти, больше шансов что всё будет в кеше.
ОтветитьУдалитьПросто кроме алгоритмической сложности в вакууме есть и реальная. Не подумайте плохо, но во многих задачах это очень важно.
Можно исхитриться и метод с двумя указателями свести к не более чем (1 + 1/4)*N проходам, исключив из перебора самую первую четверть списка:
ОтветитьУдалитьtemplate
typename list::const_iterator midOfList(const list& l)
{
typedef list::const_iterator It;
typedef list::size_type Sz;
if (l.empty())
return l.end();
It cur = l.begin();
Sz counter = 1;
It quatBegin = l.begin(); // начало второй четверти
It quatEnd = l.begin(); // конец второй четверти
// первый и полный проход списка
Sz half = 1;
while (++cur != l.end()) {
if (++counter == 2 * half) {
quatBegin = quatEnd;
quatEnd = cur;
half *= 2;
}
}
// второй проход списка по 2-ой четверти
cur = quatBegin;
Sz rest = (counter - half + 1) / 2;
while (rest-- > 0)
++cur;
return cur;
}
Тьфу, тупорылый журнал вырезал отступы и куски кода стоящие в угловых скобках (параметры шаблона).
ОтветитьУдалитьА вообще что-то какая-то сомнительная задачка. За один проход можно найти серединку только если собирать адреса пройденных узлов. Красивым такое решение назвать трудно: выиграем в производительности, проиграем по памяти.
ОтветитьУдалитьАвтор, пора бы тебе опубликовать и свое решение. Или признать, что косячите и вы на своих собеседованиях. (ироничный смайлик)
А мне кажется, что Александр выложил прекрасную задачу, даже если она и не имеет красивого решения. Теперь я иногда с досадой возвращаюсь к ней в мыслях и снова пытаюсь решить (говоря себе: ну, как же так! не может же быть). И знаете что! Задачу я не решил, зато эти размышления натолкнули меня на несколько очень удачных ходов в моей текущей работе. Не, это определенно очень полезная задача! =)
ОтветитьУдалитьserge-stepanoff: Как я говорил, задача реально может решаться по разному. Но так как у нее нет однозначного решения и много всяких деталей в зависимости какой результат нужен.
ОтветитьУдалитьНапример, один человек на собеседовании предложил идею с двумя указателями, но пущенными в параллельных потоках, и написал тут же код.
А вашу идею я себе тоже записал. Спасибо.
Рекурсивно это делается в один проход. Контейнер заводить не надо - пользуемся стеком.
ОтветитьУдалитьПример кода
Плохие новости:
ОтветитьУдалитьТРИЗ зародился во времена зарождения компьютеров, на базе обычной техники, т.е. железяки, и даже не электроника, а тем более не ПО. Т.е. и книга о технике в железяках, а не о программировании. Из книги не вылетят алгоритмы.
Но, так оказалось, что знания по ТРИЗу и опыт решения задач применимы в других самых различных областях и даже в науке. Есть упоминания об успешном применении в электронике с 70х годов, в прикладных науках и даже в математике.
Ясно вижу, что в программировании ТРИЗ применим. Плохая новость: такая версия ТРИЗа не создана, ну по крайней мере мне не знакома.
Всё-равно книга по ТРИЗу однозначна полезна. Она именно из класса тех не стареющих книг-методологий. Кроме того книга не дубовая, как учебник по спецразделу высшей математики, для меня было увлекательное, великолепное чтение.
ТРИЗ развивался всю жизнь основателя, и выходили всё новые, улучшенные версии. Он умер. Его наследие огромно по значению, но не велико по объёму. Всего три книги по 400 страниц. Одна из них по ТРИЗу.
Ещё одна плохая новость: много шарлатанов вокруг.
Ещё при жизни он начал публиковать списки шарлатанов вокруг ТРИЗа. А сейчас их вообще не разобрать. Соавторы тоже старенькие или ушли.
Читать именно последнюю книгу основателя ТРИЗа:
Поиск новых идей: от озарения к технологии (Теория и практика решения изобретательских задач)/ Г.С.Альтшуллер, Б.Л.Злотин, А.В.Зусман, В.И.Филатов. - Кишинев: Картя Молдовеняскэ, 1989.- 381 с.
Ну, и на закуску: как часть ТРИЗа идёт методика (методики) развития воображения и мышления. Из этой книги узнаете, что мозговой штурм, хоть и даёт результаты и лучше чем ничего, но вовсе не самый эффективный.
Я читал книгу в ленинке, но я видел djvu в инете.
Хм, какие-то забавные ошибки блогспота и с десятого раза опубликовалось. Да не в том порядке. ;-)
ОтветитьУдалить@digmet — Andrei Anufriev: Очень интересно, спасибо на наводку. Не слышал о такой методике.
ОтветитьУдалитьЗдравствуйте, Александр
ОтветитьУдалитьи уважаемая публика.
Прочитал только сейчас, потому и отвечаю спустя полгода.
В профиле закрыт адрес почты, потому сюда.
Кинулись все обсуждать задачку о списке, но вижу в статье более серьёзные вопросы.
1. Как выбирать алгоритм (или хотя бы класс алгоритмов) для конкретной задачи.
2. Какого бы класса алгоритм создать, чтобы решить вот такую-то новую проблему.
Тут я подразумеваю, что пункт 1 — это что-то близкое к таким олимпиадным-соревновательным задачам или к каждодневным рабочим проблемам, а пункт 2 — уже ближе к действительно науке (к первой букве из R&D), когда нужно найти решение не известное ранее.
3. Задачка об отыскании середины списка.
4. Почему выпускники МТИ круче наших.
Ну, приступим к существенным пунктам 1. и 2. Я написал это сообщение именно потому, что проблемы эти серьезные, и я думаю, что знаю решение.
ОтветитьУдалитьКратко: ТРИЗ — теория решения изобретательских задач.
Пояснения: Перескажу тут основную идею создания Триза и некоторые аспекты.
Основная идея:
Г.С. Альтшуллер работал в патентном бюро и через некоторое количество лет пришел к мысли, что все это технические открытия, которые проходят через патентное бюро, имеют в своей основе объективные принципы и закономерности. А ведь это в те времена, после войны, было очень невероятная мысль, как это так изобретения основаны на принципах? Ведь есть вучёный и его хоп внезапно озаряет и он делает открытие! Ну, или не внезапно, а под действием всяких факторов, яблоко там упадёт, или ванну примет, или сон приснится и открытие! А тут приходит студент и говорит, что технические изобретения это не психология, а есть объективные принципы развития технических систем.
Он начал развивать эту мысль и в итоге за несколько десятилетий создал ТРИЗ. ТРИЗ состоит из нескольких разделов. Первоначально, следуя этой идее, он разработал АРИЗ — алгоритм решения изобретательских задач. Сейчас, кроме ариза есть ещё несколько разделов.
Например, таблица типовых решений и приёмов. Когда он стал анализировать изобретения (десятки тысяч), то пришел к удивительному выводу, что за ними стоит не так уж много принципов и типовых приёмов, всего около сорока.
По ним составил таблицу типовых приёмов. И проверка: а может ли проблема быть решена типовым (стандартным) способом? Стоит сейчас в начале алгоритма (АРИЗ).
Ну, и говоря поближе к тексту сообщения и пункту 1. :
Типичная олимпиадная задача, алгоритм, применить и выиграть, не подразумевает НИОКРа, не подразумевает месяцев исследований и экспериментов,
я уверен, что таблица классов алгоритмов типовых решений поможет.
Видел я, что знакомо имя Гены Короткевича, а если прочитать интервью с его тренером, то можно заметить, что тренер явно говорит, что всё зависит от натренированности. Уверен, что такая таблица у них есть.
Ну, разумеется, это может быть не таблица, а дерево, или граф, да не важно.
И, разумеется, кроме таблицы можно ещё применять методики.
А вот пункт 2. может потребовать как раз исследований и изобретения чего-то нового. По-моему, это гораздо более серьёзный пункт, потому, я разделил их, и написал это сообщение.
И ТРИЗ тут как раз уместен.
Рекомендую всем прочитать книгу по ТРИЗу. Но перед тем как в гуглю полетят запросы, я ещё скажу немного важного.
Утомился бороться с ошибками блогспота при публикации коментариев.
ОтветитьУдалитьИзвините, Александр, что замусорил немного,
ответил тут:
http://digmet1024.blogspot.com/2010/11/blog-post.html