Сегодня был в одной конторе, на собеседовании. Называется она rapidsoft.

Мне задавали вопросы на смекалку и по причине полного отсутствия оной меня не приняли на работу .

Вопросы а вернее задачи такие

1. Представьте, что мы идём по земле, глобусу и т.д. сначала 1км. на север, потом 1км. на восток, потом 1 км. на юг.
Назовите все точки на глобусе из которых можно начать этот маршрут и вернуться в конце этого маршрута в исходную точку.
ОТВЕТ: южный полюс!
вариант 2 — за примерно 2 км от северного полюса (прикол в том, что сначала мы идём 1 км на север, потом не доходя до северного полюса вы поворачиваем на восток и пройдя по кругу доходим до точки нашего поворота на восток, где естественно поворачиваем на юг и через 1 км. возвращаемся в исходную точку.)

2 и 3 я рещаются по одному и тому же принципу, я бы назвал его "догоняй" (не в смысле догадайся, а в смысле беги.)

Итак номер 2: Представьте, что на плоскости есть железная дорога длина, которой бесконечна в обоих направлениях. На эту железную дорогу в разных местах ставим 2 паравоза, начальные позиции паровозов помечаются (в оригинальной версии были роботы на парашютах ) паравозы могут двигатся по шагам вправо или лево и делать проверку находятся ли они в начальной точке отчёта какого либо из этих паравозов. Задача: придумайте алгоритм следуя которому эти паравозы обязательно встретятся (кстати очень не удачное слово, сразу начинаеш думать как развернуть их навстречу друг другу), я бы сказал окажутся в одной точке на рельсах — так точнее.
ОТВЕТ: 1-е необходимо чтобы оба паравоза начали движение в одну и ту же сторону с одинаковой скоростью. Если паравоз обнаруживает, что он пересёк начальную позицию одного из паравозов, то он должен ускориться в 2 например раза. Суть в том что ускорится всегда только один паравоз.

Номер 3: Есть ОДНО связанный список неизвестной длинны. Как узнать есть ли в этом списке петля.
ОТВЕТ: запускаем 2 указателя по списку, первый движется быстрее второго и если в списке есть петля, то первый будет по ней кружить и позже в эту петлю войдет второй указатель и они пересекутся.

Задача 4
Есть 10 коробочек с таблеточками. В каждой коробочке лежит произвольное число таблеточек (это обязательно нужно подчёркивать, потому что я начал считать коробочки, а надо было таблеточки), так вот, далее таблеточки бывают 2-х видов съедобные и несьедобные, съедобная таблеточка весит 10 г. а не съедобная 9 г. Есть также весы. Задача — за ОДНО взвешивание найти и показать коробочку в которой лежат несъедобные таблетки.
ОТВЕТ: всё очень просто из первой коробочки берём одну таблетку из второй две и т.д. Ставим этот набор на весы, фиксируем вес, определяем на сколько он отличается от "эталонного" веса и в данном случае величина разницы в граммах укажет нам на номер коробочки с несъедобными таблетками. Вобщем по долям надо раскладывать, главно чтобы доли были разные.

Короче, я не ответил ни на одну задачу , кроме первой, совсем простой — как оперделить колическо бензокалонок в городе Москве, поскольку за решение подобных задач обычно в реальной жизни платят деньги, то я быстро сообразил, что и как
Зато теперь я знаю эти хитрые задачки и ответы на них...

Если есть опыт в решении подобных головоломок, то присылайте их сюда, будем делиться опытом.

Здравствуйте, Копейка, Вы писали:
К>Короче, я не ответил ни на одну задачу , кроме первой, совсем простой — как оперделить колическо бензокалонок в городе Москве, поскольку за решение подобных задач обычно в реальной жизни платят деньги, то я быстро сообразил, что и как
А можно поподробнее, лично я впервые слышу...

Эти задачи (может не все, но некоторые точно) встречались в форуме "Этюды для программистов".

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

DAS>Эти задачи (может не все, но некоторые точно) встречались в форуме "Этюды для программистов".

Соответственно отсюда 2 вывода:

1. Читайте этот форум, ибо это не просто зарядка для ума, но и возможность увеличить свои шансы при приеме на работу.
2. Те кто задавал эти вопросы, скорее всего тоже читают rsdn

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

К>Номер 3: Есть ОДНО связанный список неизвестной длинны. Как узнать есть ли в этом списке петля.
К> ОТВЕТ: запускаем 2 указателя по списку, первый движется быстрее второго и если в списке есть петля, то первый будет по ней кружить и позже в эту петлю войдет второй указатель и они пересекутся.

Отвратительное с точки зрения перформанса решение.

К>Задача 4
К> Есть 10 коробочек с таблеточками. В каждой коробочке лежит произвольное число таблеточек (это обязательно нужно подчёркивать, потому что я начал считать коробочки, а надо было таблеточки), так вот, далее таблеточки бывают 2-х видов съедобные и несьедобные, съедобная таблеточка весит 10 г. а не съедобная 9 г. Есть также весы. Задача — за ОДНО взвешивание найти и показать коробочку в которой лежат несъедобные таблетки.
К> ОТВЕТ: всё очень просто из первой коробочки берём одну таблетку из второй две и т.д. Ставим этот набор на весы, фиксируем вес, определяем на сколько он отличается от "эталонного" веса и в данном случае величина разницы в граммах укажет нам на номер коробочки с несъедобными таблетками. Вобщем по долям надо раскладывать, главно чтобы доли были разные.

Неполное условие привел. Только из ответа понятно что в конкретной коробке либо все съедобные, либо все несъедобные.

А на какую позицию претендовал?

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


AVK>Отвратительное с точки зрения перформанса решение.
Можно другое...

AVK>Неполное условие привел. Только из ответа понятно что в конкретной коробке либо все съедобные, либо все несъедобные.
а ну извеняюсь

AVK>А на какую позицию претендовал?
Не знаю... у них там много позиций, однако фирма оффшорным программированием занимается, так что я бы всё равно не пошёл бы, не хочу квалификацию терять.
Мне бы MRP, ERP...

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

PK>Здравствуйте, Копейка, Вы писали:
К>>Короче, я не ответил ни на одну задачу , кроме первой, совсем простой — как оперделить колическо бензокалонок в городе Москве, поскольку за решение подобных задач обычно в реальной жизни платят деньги, то я быстро сообразил, что и как
PK>А можно поподробнее, лично я впервые слышу...

Как я понял смысл этой задачи правильно определить зависимости, в данном случае необходимо показать от чего зависит количество бензоколонок и по возможности раскрыть связи между зависимостями. Вобщем кол-во автомобилей, средний пробег за сутки, средний расход бензина, пропускная способность бензоколонок. По теории Адама Смита рынок стремится к покою, отсюда можно сделать вывод, что потребность в бензоколонках должна быть удовлетворена, можно сюда же приплести отпускные цены на бензин у оптовиков, норму прибыли, соц опрос водителей насколько они довольны быстротой обслуживания ни колонках.

Вот собственно и всё.

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

К>>Номер 3: Есть ОДНО связанный список неизвестной длинны. Как узнать есть ли в этом списке петля.
К>> ОТВЕТ: запускаем 2 указателя по списку, первый движется быстрее второго и если в списке есть петля, то первый будет по ней кружить и позже в эту петлю войдет второй указатель и они пересекутся.

AVK>Отвратительное с точки зрения перформанса решение.
а есть ли другое решение ? что-то я такого не знаю.

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

AVK>>Отвратительное с точки зрения перформанса решение.
IS>а есть ли другое решение ? что-то я такого не знаю.

А в чем проблема? Алгоритмов поиска циклов в графе вагон и маленька тележка.

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

AVK>>>Отвратительное с точки зрения перформанса решение.
IS>>а есть ли другое решение ? что-то я такого не знаю.

AVK>А в чем проблема? Алгоритмов поиска циклов в графе вагон и маленька тележка.

в силу очень частного случая (односвязный список) — алгоритм похоже оптимальный.

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

IS>в силу очень частного случая (односвязный список) — алгоритм похоже оптимальный.

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

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

AVK>Оптимальный? Ну не знаю, смотря какой критерий. Если расход памяти то может и оптимальный,

"может" — очень интересное выражение в данном контексте

AVK>а вот насчет производительности не уверен, это ж сколько холостых прокруток будет пока счетчики встретятся.

это линейный алгоритм относительно длины петли + длины списка до начала петли (куда уж меньше). Каждый шаг — два сложения и два сравнения.

AVK> Алгоритм со счетчиками прохождений в каждом узле или с хеш-таблицей переходов будет заметно оптимальнее.

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

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

A>"может" — очень интересное выражение в данном контексте

Может значит я исследования не проводил и точно не знаю.

AVK>>а вот насчет производительности не уверен, это ж сколько холостых прокруток будет пока счетчики встретятся.

A>это линейный алгоритм относительно длины петли + длины списка до начала петли (куда уж меньше).

Дело не только в линейности. Те алгоритмы, что я предложил тоже линейны.

A>Каждый шаг — два сложения и два сравнения.

Вот только количество шагов неоптимально.

AVK>> Алгоритм со счетчиками прохождений в каждом узле или с хеш-таблицей переходов будет заметно оптимальнее.

A>Ну-ну, поэкспериментируй как-нибудь. Если на каждом шаге тебе придётся делать что-то, бОльшее двух сложений и двух сравнений

Алгоритм со счетчиками — один инкремент и одно сравнение.

A> (а ведь как минимум нужно проверять на конец списка и инкрементировать текущий элемент) — алгоритм в пролёте.

Опять неверно. Даже если алгоритм будет иметь более сложный шаг, но при этом шагов будет меньше то он в определенных условиях будет выгоднее.

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

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

A>>"может" — очень интересное выражение в данном контексте

AVK>Может значит я исследования не проводил и точно не знаю.

Для того, чтобы решить эту задачу с помощью _одного_ указателя, нужно оооочень постараться, тебе не кажется?

AVK>>>а вот насчет производительности не уверен, это ж сколько холостых прокруток будет пока счетчики встретятся.

A>>это линейный алгоритм относительно длины петли + длины списка до начала петли (куда уж меньше).

AVK>Дело не только в линейности. Те алгоритмы, что я предложил тоже линейны.

Ну я и говорю — линейный алгоритм + очень быстрый шаг. Кол-во шагов — в худшем случае длина петли + длина списка до начала петли, каждый шаг —

slow = slow->next;
fast = fast->next->next;

A>> (а ведь как минимум нужно проверять на конец списка и инкрементировать текущий элемент) — алгоритм в пролёте.

AVK>Опять неверно. Даже если алгоритм будет иметь более сложный шаг, но при этом шагов будет меньше то он в определенных условиях будет выгоднее.

Нуууууууу, условия всегда можно подогнать под ответ (например, "return false" отлично работает для списков, не содержащих циклов), но ведь мы рассуждем в терминах памяти/сложности алгоритма? Если же мы рассуждаем про реальную скорость выполнения алгоритма на конкретных компьютерах, то не будь голословен и напиши свой алгоритм/программу, не модифицирующий элементы списка и работающий быстрее вышеприведенного (так уж и быть, дадим ему O(N) памяти).

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

AVK>>Может значит я исследования не проводил и точно не знаю.

A>Для того, чтобы решить эту задачу с помощью _одного_ указателя, нужно оооочень постараться, тебе не кажется?

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

AVK>>Дело не только в линейности. Те алгоритмы, что я предложил тоже линейны.

A>Ну я и говорю — линейный алгоритм + очень быстрый шаг. Кол-во шагов — в худшем случае длина петли + длина списка до начала петли,

Не факт. Все зависит от конфигурации списка. Ты считай не только количество шагов медленного указателя, но и количество шагов быстрого. А вот второе в твоем случае будет в 2 раза больше. При длинной последовательности до петли быстрый указатель прокрутится по ней очень много раз.

A>каждый шаг —

A>slow = slow->next;
A>fast = fast->next->next;

И проверка на каждом шаге быстрого указателя.

Кроме того — на практике обычно требуется не просто обнаружить сам факт наличия петли, а найти точку начала. В такой постановке предложенный алгоритм никуда не годится.

AVK>>Опять неверно. Даже если алгоритм будет иметь более сложный шаг, но при этом шагов будет меньше то он в определенных условиях будет выгоднее.

A>Нуууууууу, условия всегда можно подогнать под ответ

При чем тут подогнать? Просто я хочу сказать что предложенный алгоритм назвать оптимальным без оговорок нельзя. Для любого конкретного соотношения скоростей быстрого и медленного указателей можно подобрать такую конфигурацию списка, что этот алгоритм будет жутким образом неоптимален. А вот алгоритм с флагом прохождения каждого узла от конфигурации списка не зависит, гарантирует поиск петли за количество шагов, равное длине списка, имеет более дешевый шаг и находит точку, в которой начинается петля.

A> то не будь голословен и напиши свой алгоритм/программу, не модифицирующий элементы списка

Опять ты сам условие придумал? Кто говорил про модификацию? Тогда и я могу условие поставить — поиск начала петли.

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

К>Вопросы а вернее задачи такие

К>1. Представьте, что мы идём по земле, глобусу и т.д. сначала 1км. на север, потом 1км. на восток, потом 1 км. на юг.
К>Назовите все точки на глобусе из которых можно начать этот маршрут и вернуться в конце этого маршрута в исходную точку.
К> ОТВЕТ: южный полюс!
К> вариант 2 — за примерно 2 км от северного полюса (прикол в том, что сначала мы идём 1 км на север, потом не доходя до северного полюса вы поворачиваем на восток и пройдя по кругу доходим до точки нашего поворота на восток, где естественно поворачиваем на юг и через 1 км. возвращаемся в исходную точку.)

вариант 2 — неправильный. Если начальная точка будет за два км от полюса, то когда мы пройдем 1 км к полюсу — значит до полюса остается 1 км. потом мы прошлись по кругу радиусом 1 км и прошли 1 км ???
мы прошли 2пи*1=6.29 км. Необходимая точка 1/2пи = 160 метров + 1 км
Итого 1,16 км от полюса!

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

К>Короче, я не ответил ни на одну задачу , кроме первой, совсем простой — как оперделить колическо бензокалонок в городе Москве,

И каково решение?

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

...blah-blah-blah skipped.
AVK>Опять ты сам условие придумал?

Короче, вернёмся к условию —
"Номер 3: Есть ОДНО связанный список неизвестной длины. Как узнать есть ли в этом списке петля."

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

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

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

A>...blah-blah-blah skipped.
AVK>>Опять ты сам условие придумал?

A>Короче, вернёмся к условию —
A>"Номер 3: Есть ОДНО связанный список неизвестной длины. Как узнать есть ли в этом списке петля."

A>Придумай хоть одно решение, отличное от приведённого, не говоря уже про оптимальность. Модифицировать элементы, очевидно, нельзя — иначе задача была бы слишком тривиальна.

вали в hashtable. дойдешь до "конца" петли и получишь исключение. заодно точно будешь знать где собака порылась

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


A>>Короче, вернёмся к условию —
A>>"Номер 3: Есть ОДНО связанный список неизвестной длины. Как узнать есть ли в этом списке петля."

A>>Придумай хоть одно решение, отличное от приведённого, не говоря уже про оптимальность. Модифицировать элементы, очевидно, нельзя — иначе задача была бы слишком тривиальна.

_MM_>вали в hashtable. дойдешь до "конца" петли и получишь исключение. заодно точно будешь знать где собака порылась
в классической инкарнации у условии задачи есть, что можно использовать 1-2 дополнитиельных переменных (имееся в виду 1-2 поинтера). Ибо как говаривал классик — "Как говаривал классик — "С деньгами и дурак купит.""

woow ! сделал поиск этой фразы в яндексе — и что получил :


http://www.yandex.ru/yandsearch?rpt=rad&text=%F1+%E4%E5%ED%FC%E3%E0%EC%E8+%E8+%E4%F3%F0%E0%EA+%EA%F3%EF%E8%F2