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

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

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

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

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

Нехрен трогать 2-й паровоз ...
Первый пусть как маятник с увеличением амплитуды, пока не столкнется со вторым

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

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

А если в коробочках только по 2 таблетки ?

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

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


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

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

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

в классической инкарнации — да. в приведенной автором — всё что угодно.

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

IS>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

дивно :))

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


KGP>Нехрен трогать 2-й паровоз ...
KGP>Первый пусть как маятник с увеличением амплитуды, пока не столкнется со вторым

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

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

Ещё никому это не удавалось...

К>>Задача 4
К>> Есть 10...

KGP>А если в коробочках только по 2 таблетки ?
Тогда всё, туши свет

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

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

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

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

_MM_>в классической инкарнации — да. в приведенной автором — всё что угодно.

Выделенный мной текст ("неизвестной длины") подразумевает использование О(1) памяти. Ишь, какие умные

KGP>>Нехрен трогать 2-й паровоз ...
KGP>>Первый пусть как маятник с увеличением амплитуды, пока не столкнется со вторым

К>Программа запускается одновременно на обоих паравозах, пойми, исходный код один для всех паравозов.
Ну здрасте! А скорость поровозов тогда тоже одновременно в 2 раза увеличится? Тогда никто никогда не встретится нис кем. А про решение с амплитудой — значит даны лишние условия (насчет определения начального момента).

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

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

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

Хм.. странно — раньше она называлась Microsoft

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

К>Программа запускается одновременно на обоих паравозах, пойми, исходный код один для всех паравозов.

А они знают о существовании второго ?
Если нумеруются, то =2 стоит.

К> Ещё никому это не удавалось...
Тогда и второй в другую петлю может угодить и опять кердык !
Хрень формулировка

К>>>Задача 4
К>>> Есть 10...

KGP>>А если в коробочках только по 2 таблетки ?
К>Тогда всё, туши свет
Хрень формулировка

Мой вывод — задачки сформулированны ХРЕНОВО !

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

_>Ну здрасте! А скорость поровозов тогда тоже одновременно в 2 раза увеличится? Тогда никто никогда не встретится нис кем.

Советую внимательно прочитать при каком условии скорость возрастает.....

_>Я так понимаю тут не цикл, а петля — типа как лассо. Так что из нее не выйти. Вообще, кривые как видно формулировки.

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

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

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

К>>Программа запускается одновременно на обоих паравозах, пойми, исходный код один для всех паравозов.

KGP>А они знают о существовании второго ?
KGP>Если нумеруются, то =2 стоит.

нет не знают.

К>> Ещё никому это не удавалось...
KGP>Тогда и второй в другую петлю может угодить и опять кердык !
KGP>Хрень формулировка

Хорош прикалываться, в какую ещё вторую?

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

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

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

C>Хм.. странно — раньше она называлась Microsoft
Ты это серьёздно?

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

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

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

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

C>>Хм.. странно — раньше она называлась Microsoft
К>Ты это серьёздно?
Серьезно. Все эти тесты (английском языке, разумеется) можно найти, задав в гугле поиск по "microsoft interview questions". Ну разве что в вопросе про бензоколонки вместо Москвы — Лос Анджелес. Я одно время увлекался этим делом. Предание гласит, что майкрософтовцы таким образом оценивают способность кандидата _думать_вообще_ и _думать_нестандартно_. Что оценивает славная контора rapidsoft — непонятно.

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

C>Серьезно. Все эти тесты (английском языке, разумеется) можно найти, задав в гугле поиск по "microsoft interview questions". Ну разве что в вопросе про бензоколонки вместо Москвы — Лос Анджелес. Я одно время увлекался этим делом. Предание гласит, что майкрософтовцы таким образом оценивают способность кандидата _думать_вообще_ и _думать_нестандартно_. Что оценивает славная контора rapidsoft — непонятно.

Хм... странно, как можно думать нестандартно над задачей с конечным числом решений? Притом числом небольшим. Я думал это просто надо знать, и вообще по хорошему для таких нестандартных подходов лучше завести справочник, есть проблема, заглянул в справочник, а тебе 2-3 подходящих способа решения оттуда и всё пучком. Нафига себя в грудь пяткой бить? Непонятно мне это. Можект я мыслю стандартно?

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

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

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

К>>>Программа запускается одновременно на обоих паравозах, пойми, исходный код один для всех паравозов.

KGP>>А они знают о существовании второго ?
KGP>>Если нумеруются, то =2 стоит.

а shared ресурс ... и узнают через InterlockedIncrement или как там (рельсы же общие)

К>>> Ещё никому это не удавалось...
KGP>>Тогда и второй в другую петлю может угодить и опять кердык !
KGP>>Хрень формулировка

К>Хорош прикалываться, в какую ещё вторую?
одна с одной староны, куда первый поедет, другая с другой куда второй поедет ...

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

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

C>>Серьезно. Все эти тесты (английском языке, разумеется) можно найти, задав в гугле поиск по "microsoft interview questions". Ну разве что в вопросе про бензоколонки вместо Москвы — Лос Анджелес. Я одно время увлекался этим делом. Предание гласит, что майкрософтовцы таким образом оценивают способность кандидата _думать_вообще_ и _думать_нестандартно_. Что оценивает славная контора rapidsoft — непонятно.

К>Хм... странно, как можно думать нестандартно над задачей с конечным числом решений? Притом числом небольшим. Я думал это просто надо знать, и вообще по хорошему для таких нестандартных подходов лучше завести справочник, есть проблема, заглянул в справочник, а тебе 2-3 подходящих способа решения оттуда и всё пучком. Нафига себя в грудь пяткой бить? Непонятно мне это. Можект я мыслю стандартно?

А в чем практический смысл в выучивании рещения задачи про таблетки? Ну, можно конечно классифицировать это как применение некоего приема "внесение нелинейности", только это уже из области ТРИЗ или подобных методик. Справочник нестандартных подходов IMHO есть нонсенс, т.к. нестандартный подход не может по определению быть классифицирован / генерализирован — иначе это стандартный подход. "Справочник стандартных подходов" для программирования называется Design Patterns — знание, а главное — умение грамотно применять эти Patterns тоже ценится многими работодателями. Я бы даже сказал, что это, если хотите, часть "инженерной культуры". Проблема в том, что в любой инженерной практике приходится сталкиваться с задачами, которые плохо рещаются стандартными методиками. Если позиция подразумевает рещение таких задач, то на интервью вполне естественно желание работодателя протестировать умение кандидата находить нешаблонные рещения.

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

C>А в чем практический смысл в выучивании рещения задачи про таблетки? Ну, можно конечно классифицировать это как применение некоего приема "внесение нелинейности", только это уже из области ТРИЗ или подобных методик.

Нелинейности? Где это там нелинейность? По моему всё даже очень линейно.

C> Справочник нестандартных подходов IMHO есть нонсенс, т.к. нестандартный подход не может по определению быть классифицирован / генерализирован — иначе это стандартный подход. "Справочник стандартных подходов" для программирования называется Design Patterns — знание, а главное — умение грамотно применять эти Patterns тоже ценится многими работодателями. Я бы даже сказал, что это, если хотите, часть "инженерной культуры".

Назовите это справочником стандартных подходов.

C> Проблема в том, что в любой инженерной практике приходится сталкиваться с задачами, которые плохо рещаются стандартными методиками. Если позиция подразумевает рещение таких задач, то на интервью вполне естественно желание работодателя протестировать умение кандидата находить нешаблонные рещения.

А что понимать под понятием "стандартные методики"? Скажем 2 способа доказательства теоремы Пифагора — это стандартные методики, а 3-й нестандартный? Это просто софистика и манипулирование понятиями, определениями в чистом виде. Я считаю, что нестандартный способ это способ который редко применяется на практике. Таким образом под решение поставленных задач нельзя подвести определение "нестандартно", так как другими способами указанные задачи просто не решаются, что следует из условия таких задач. Я бы посоветовал авторам заменить определение "нестандартное мышление" на "оптимальное решение". ИМХО было бы понятнее, что имеется ввиду.


Стандарт —
— утверждаемый компетентным органом нормативно-технический документ, устанавливающий комплекс норм, правил по отношению к предмету стандартизации;
- типовой образец, эталон, модель, принимаемые за исходные для сопоставления с ними других предметов.
http://encycl.yandex.ru/cgi-bin/art.pl?art=glossary/173/173_271.HTM&encpage=glossary&mrkp=/yandbtm7%3Fq%3D-1719969238%26p%3D0%26g%3D0%26d%3D2%26ag%3Denc_abc%26tg%3D1%26p0%3D0%26q0%3D435645703%26d0%3D0%26script%3D/yandpage%253F

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

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

C>>А в чем практический смысл в выучивании рещения задачи про таблетки? Ну, можно конечно классифицировать это как применение некоего приема "внесение нелинейности", только это уже из области ТРИЗ или подобных методик.

К>Нелинейности? Где это там нелинейность? По моему всё даже очень линейно.

Пусть будет линейно, я не настаиваю. Я не имел в виду математическое определение линейности (я не математик и не готов дискутировать на околоматематические темы)

C>> Справочник нестандартных подходов IMHO есть нонсенс, т.к. нестандартный подход не может по определению быть классифицирован / генерализирован — иначе это стандартный подход. "Справочник стандартных подходов" для программирования называется Design Patterns — знание, а главное — умение грамотно применять эти Patterns тоже ценится многими работодателями. Я бы даже сказал, что это, если хотите, часть "инженерной культуры".

К>Назовите это справочником стандартных подходов.

C>> Проблема в том, что в любой инженерной практике приходится сталкиваться с задачами, которые плохо рещаются стандартными методиками. Если позиция подразумевает рещение таких задач, то на интервью вполне естественно желание работодателя протестировать умение кандидата находить нешаблонные рещения.

К>А что понимать под понятием "стандартные методики"? Скажем 2 способа доказательства теоремы Пифагора — это стандартные методики, а 3-й нестандартный? Это просто софистика и манипулирование понятиями, определениями в чистом виде. Я считаю, что нестандартный способ это способ который редко применяется на практике. Таким образом под решение поставленных задач нельзя подвести определение "нестандартно", так как другими способами указанные задачи просто не решаются, что следует из условия таких задач. Я бы посоветовал авторам заменить определение "нестандартное мышление" на "оптимальное решение". ИМХО было бы понятнее, что имеется ввиду.

Мы, наверно, говорим о разных вещах. Доказательства теорем не является инженерной работой, и задачи, и методики там другие. Про софистику и манипулирование понятиями я не совсем понял, что Вы имеете в виду. В любом случае я не специалист в этих понятиях и обсуждать их не буду. Типовые решения (стандартные методики) основаны на том, что в некоей инженерной предметной области можно классифицировать ограниченное число часто встречающихся задач с указанием опробованных решений для каждой такой задачи. disclaimer: не претендую на точность данной формулировки, просьба к словам не придираться

К>
К>Стандарт —
К>- утверждаемый компетентным органом нормативно-технический документ, устанавливающий комплекс норм, правил по отношению к предмету стандартизации;
К>- типовой образец, эталон, модель, принимаемые за исходные для сопоставления с ними других предметов.
К>http://encycl.yandex.ru/cgi-bin/art.pl?art=glossary/173/173_271.HTM&encpage=glossary&mrkp=/yandbtm7%3Fq%3D-1719969238%26p%3D0%26g%3D0%26d%3D2%26ag%3Denc_abc%26tg%3D1%26p0%3D0%26q0%3D435645703%26d0%3D0%26script%3D/yandpage%253F
К>

Я не понимаю, с какой целью Вы привели вышеуказанное определение стандарта.

Вообще, предлагаю оставаться в рамках топика. Меньше всего хочется развивать разговор в стиле "Хаджа Насреддин vs. Мудрецы Падишаха"

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

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

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

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

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

C>>>Хм.. странно — раньше она называлась Microsoft
К>>Ты это серьёздно?
C>Серьезно. Все эти тесты (английском языке, разумеется) можно найти, задав в гугле поиск по "microsoft interview questions".

Вот перевод статейки про интервью, там вопрос про бензоколонки тоже упоминается:
http://russian.joelonsoftware.com/Articles/Interviewing.html

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

C>Пусть будет линейно, я не настаиваю. Я не имел в виду математическое определение линейности (я не математик и не готов дискутировать на околоматематические темы)

C>...В любом случае я не специалист в этих понятиях и обсуждать их не буду.
...не претендую на точность данной формулировки, просьба к словам не придираться[/i]


C>Я не понимаю, с какой целью Вы привели вышеуказанное определение стандарта.

Про коробочки надо указать, что среди них находиться только одна с несъедобными, потому что вот что получается, если таких коробочек несколько:
Допустим из 10 у нас 4 не съедобные: допустим 1, 4,5,7, но пока мы этого не знаем
Берём из певрой 1 таблеточку, из второй 2, из третей три и т.д. Получаем общую массу: 397. Из 550 — 397 = 153/9 = 17 несьедобных таблеток.
Это число можно получить например, если сложить например 10+7, тоесть получается неоднозначность.



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

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

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

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

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

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

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

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

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

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

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

А>Про коробочки надо указать, что среди них находиться только одна с несъедобными, потому что вот что получается, если таких коробочек несколько:
А>Допустим из 10 у нас 4 не съедобные: допустим 1, 4,5,7, но пока мы этого не знаем
А>Берём из певрой 1 таблеточку, из второй 2, из третей три и т.д. Получаем общую массу: 397. Из 550 — 397 = 153/9 = 17 несьедобных таблеток.
А>Это число можно получить например, если сложить например 10+7, тоесть получается неоднозначность.

Стандартно вы как то мыслите, шаблонно!
Фи, противный!