Задачки с интервью

[Яправ]

буду тут скидывать разные задачки.

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

Вопрос: каким бы вы алгоритмом воспользовались в такой игре и какова была бы вероятность выигрыша при таком алгоритме?

[Dima424]

расказывай...

[Яправ]

расказывай...

ты чо? уже сдаешься? А подумать?

[Dima424]

я предпологаю дело не в алгоритме принятя решения, а в самом решении...

будет ли обмененна карта или нет...

[Dima424]

да, а какие карты о, как игральные? 2,3,4,5.... туз...

просто карточки?

[Яправ]

точки в трехмерном пространстве. Координаты Х и У из целых чисел. Точки соединены отрезками. Какое минимальное колличество точек нужно чтоб среди середин отрезков была гарантированно середина координаты которой из целых чисел.

[STYLE]

буду тут скидывать разные задачки.

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

Вопрос: каким бы вы алгоритмом воспользовались в такой игре и какова была бы вероятность выигрыша при таком алгоритме?

Алгоритм: выбор из двух или из трех карт.

[Яправ]

да, а какие карты о, как игральные? 2,3,4,5.... туз...

просто карточки?

какая разница? Допустим игральные карты. две шестерки и один туз. Тебе надо угодать туза. После того как ты выбираешь карту первый раз я из оставшихся карт открываю одну проигрышную(я знаю какая из карт выигрышная) и предлогаю тебе поменять выбор если ты хочешь. Придумай алгоритм который повышает твои шансы выигрыша

[Яправ]

Алгоритм: выбор из двух или из трех карт.

алгоритм который помогает тебе выиграть игру правила которой я объяснил

[Dima424]

какая разница? Допустим игральные карты. две шестерки и один туз. Тебе надо угодать туза. После того как ты выбираешь карту первый раз я из оставшихся карт открываю одну проигрышную(я знаю какая из карт выигрышная) и предлогаю тебе поменять выбор если ты хочешь. Придумай алгоритм который повышает твои шансы выигрыша

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

а если это просто [a,b,c], где выйгрышная карта [random], то алгоритм тут как бы не причем....

[STYLE]

алгоритм который помогает тебе выиграть игру правила которой я объяснил

Давай начнем с ответа на игру.
Надо менять карту.
Правильно?

[Яправ]

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

а если это просто [a,b,c], где выйгрышная карта [random], то алгоритм тут как бы не причем....

еще раз объясняю: тебе предлогают выбрать из трех карт(одинаковых) а, b и с . Допустим ты выбрал а. значит осталиь карты b и c. Я тебе не даю проверить еще выигрышная карта которую ты выбрал или нет. Вместо этого я из двух оставшихся показываю тебе одну карту которая проигрышная(допустим это b). Я предлогаю тебе поменять свой выбор. У тебя осталось только два выбора а и с так как я тебе показал что карта b проигрышная. -- таковы условия игры.

Теперь вопрос: можно ли придумать алгоритм выбора карт который повышает твои шансы.

[Яправ]

Давай начнем с ответа на игру.
Надо менять карту.
Правильно?

я не буду говорить пока правильно или нет. Вопрос: можешь ты просчитать какова вероятность выигрыша в твоем алгоритме?

[STYLE]

я не буду говорить пока правильно или нет. Вопрос: можешь ты просчитать какова вероятность выигрыша в твоем алгоритме?

Я же тебе сказал, что в первом случае ты выбираешь из 3, во втором из двух.
Честно скажу, где-то читал про эту задачу.

[elfy]

буду тут скидывать разные задачки.

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

Вопрос: каким бы вы алгоритмом воспользовались в такой игре и какова была бы вероятность выигрыша при таком алгоритме?

Нужно поменять карту, как И предлагает дилер, т.к. в таком случае вероятность выигрыша 50%, а не 33.33333%

[STYLE]

Нужно поменять карту, как И предлагает дилер, т.к. в таком случае вероятность выигрыша 50%, а не 33.33333%

А я что написал выше? :117:

[Яправ]

Дам подсказку: самый лучший алгоритм даей вам вероятность выигрыша 67% или 2/3

[STYLE]

Дам подсказку: самый лучший алгоритм даей вам вероятность выигрыша 67% или 2/3

Ты сначала скажи, наши 50% и 2/3 неправильно?

[Alex5448]

6 банок с конфетами. В 5 банках конфеты весят 15 грамм, а в шестой 14 грамм. Есть весы.
Найди банку с относительно легкими конфетами только одним взвешиванием.

[STYLE]

6 банок с конфетами. В 5 банках конфеты весят 15 грамм, а в шестой 14 грамм. Есть весы.
Найди банку с относительно легкими конфетами только одним взвешиванием.

Все конфеты или каждая в банке столько весит?

[Яправ]

6 банок с конфетами. В 5 банках конфеты весят 15 грамм, а в шестой 14 грамм. Есть весы.
Найди банку с относительно легкими конфетами только одним взвешиванием.

мне кажется что одним не возможно. двумя взвешиваниями можно определить из шести.

Первый раз ты на каждую чашу ставишь по 2 банки. Таким образом ты знаешь в какой паре банок она находится. второй раз ты уже находишь банку. Может ты условия задачи напутал?

[elfy]

А я что написал выше? :117:

То же самое, но другими словами, вот я И подумала, что Марик не понял, а оказывается, мы оба неправы

[STYLE]

То же самое, но другими словами, вот я И подумала, что Марик не понял, а оказывается, мы оба неправы

Он не ответил еще.

[Барон_Мюнхау]

буду тут скидывать разные задачки.

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

Вопрос: каким бы вы алгоритмом воспользовались в такой игре и какова была бы вероятность выигрыша при таком алгоритме?

Вероятность выигрыша = 1/2. Алгоритм роли не играет - можешь менять. можешь не менять.

[Барон_Мюнхау]

6 банок с конфетами. В 5 банках конфеты весят 15 грамм, а в шестой 14 грамм. Есть весы.
Найди банку с относительно легкими конфетами только одним взвешиванием.

Надо пронумеровать банки от 1 до 6.
Взять из первой 1 конфету, из второй 2, из третьей 3 и так далее.
Затем взвешиваем все эти конфеты.
Если бы все конфеты были по 15 грамм, то
общий вес составил бы 21х15=315 грамм
Если первая банка по 14 грамм, то вес будет на 1 грамм меньше
(т.к. мы взяли оттуда 1 конфету).
Если 14 граммовые были во второй, то на 2 грамма меньше.
И так далее.

[Яправ]

Он не ответил еще.
Вероятность выигрыша = 1/2. Алгоритм роли не играет - можешь менять. можешь не менять.

Немного поменяем условие задачи. есть 100 карт и только одна выигрышная. Вероятность угодать у вас 1%. Вероятность того что среди оставшихся карт есть выигрышная карта практически 100%, правильно?

Теперь допустим что вы выбрали карту. После этого из оставшихся я убрал 98 проигрышных карт. Какова вероятность того что вторая оставшаяся карта(которую вы не выбрали) выигрышная?

[Яправ]

Надо пронумеровать банки от 1 до 6.
Взять из первой 1 конфету, из второй 2, из третьей 3 и так далее.
Затем взвешиваем все эти конфеты.
Если бы все конфеты были по 15 грамм, то
общий вес составил бы 21х15=315 грамм
Если первая банка по 14 грамм, то вес будет на 1 грамм меньше
(т.к. мы взяли оттуда 1 конфету).
Если 14 граммовые были во второй, то на 2 грамма меньше.
И так далее.

ааа... я не понял что каждая конфета в банке весит по-другому. Я почему-то подумал что вся банка на один грам меньше весит

[elfy]

6 банок с конфетами. В 5 банках конфеты весят 15 грамм, а в шестой 14 грамм. Есть весы.
Найди банку с относительно легкими конфетами только одним взвешиванием.

Ето будет считаться одним взвешиванием, если я поставлю коробки на чаши весов по очереди - 1ую на одну чашу, затем вторую на другую, 3ю на первую чашу, И т.д.?

[elfy]

Немного поменяем условие задачи. есть 100 карт и только одна выигрышная. Вероятность угодать у вас 1%. Вероятность того что среди оставшихся карт есть выигрышная карта практически 100%, правильно?

Теперь допустим что вы выбрали карту. После этого из оставшихся я убрал 98 проигрышных карт. Какова вероятность того что вторая оставшаяся карта(которую вы не выбрали) выигрышная?
...

[реднек]

A, B, C

I choose A:
Dealer shows B, therefore B < C

Two cases:
1. B < C && A < C (C wins: 1/3)
2. B < C && A > C (A wins: 1/3)

Case 1 happens twice, therefore 66.7%

[Барон_Мюнхау]

Немного поменяем условие задачи. есть 100 карт и только одна выигрышная. Вероятность угодать у вас 1%. Вероятность того что среди оставшихся карт есть выигрышная карта практически 100%, правильно?
Теперь допустим что вы выбрали карту. После этого из оставшихся я убрал 98 проигрышных карт. Какова вероятность того что вторая оставшаяся карта(которую вы не выбрали) выигрышная?

Вероятность того что среди оставшихся карт есть выигрышная карта = 99/100

Вероятность того, что вторая оставшаяся карта(которую вы не выбрали) выигрышная = 1/2

[elfy]

Вероятность выигрыша = 1/2. Алгоритм роли не играет - можешь менять. можешь не менять.
Не, когда выбираеш 1ую карту, вероятность, что она выигрышная 1/3, того, что выигрышная одна из оставшихся - 2/3. Когда дилер убирает проигрышную из 2-х карт, вероятность того, что оставшаяся выигрышная остаётся 2/3
Нужно менять

[реднек]

точки в трехмерном пространстве. Координаты Х и У из целых чисел. Точки соединены отрезками. Какое минимальное колличество точек нужно чтоб среди середин отрезков была гарантированно середина координаты которой из целых чисел.

Для плоскости любые три точки расположеные не на дистанции 1 друг от друга будут обладать таким свойством. Значит для плоскости 5, для 3х мерного пространства 8+1 = 9.

[Барон_Мюнхау]

Не, когда выбираеш 1ую карту, вероятность, что она выигрышная 1/3, того, что выигрышная одна из оставшихся - 2/3. Когда дилер убирает проигрышную из 2-х карт, вероятность того, что оставшаяся выигрышная остаётся 2/3Нужно менять

Учи матчасть (статистику) :230:

[реднек]

A, B, C

I choose A:
Dealer shows B, therefore B < C

Two cases:
1. B < C && A < C (C wins: 1/3)
2. B < C && A > C (A wins: 1/3)

Case 1 happens twice, therefore 66.7%

Забыл написать, что надо выбирать C, т.е. ту которая не на руках и не на которую показал дилер.

[elfy]

Учи матчасть (статистику) :230:
Ето как раз ты учи:122:

[Яправ]

Вероятность того что среди оставшихся карт есть выигрышная карта = 99/100

Вероятность того, что вторая оставшаяся карта(которую вы не выбрали) выигрышная = 1/2

ты настаиваешь на 1/2 потому что думаешь что ты оба раза случайно выбираешь карту. Эта проблема на "зависимую" вероятность. Вся фишка в том что я(диллер) знаю какие карты проигрышные и убираю только их оставляя скорее всего единственную выигрышную карту из 99 оставшихся.

Ты сам сказал что вероятность того что среди 99 карт есть выигрышная 99%. Я убрал из них только проигрышные. Значит вероятность того что оставшаяся карта выигрышная 99%

Фактически алгоритм (всегда менять) означает что ты всегда выбираешь выигрышную карту при условии что ты первый раз не угадал

[Яправ]

Учи матчасть (статистику) :230:

Не, когда выбираеш 1ую карту, вероятность, что она выигрышная 1/3, того, что выигрышная одна из оставшихся - 2/3. Когда дилер убирает проигрышную из 2-х карт, вероятность того, что оставшаяся выигрышная остаётся 2/3
Нужно менять


С Эльфи лучше не спорить.


А остальным таки
http://mathhelpplanet.com/static.php?p=zavisimye-i-nezavisimye-sluchainye-sobytiya

учить матчасть :)

[elfy]

С Эльфи лучше не спорить.


А остальным таки
хттп://матххелппланет.цом/статиц.пхп?п=зависимые-и-независимые-случаиные-события

учить матчасть :)

А приз будет?

[Яправ]

А приз будет?

естественно. Ночь любви со мной

[XCNY]

буду тут скидывать разные задачки.

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

Вопрос: каким бы вы алгоритмом воспользовались в такой игре и какова была бы вероятность выигрыша при таком алгоритме?

Алгоритмом орел или решка ,воспользовалься.:115:Если я прально понил,ситуацию .

[Барон_Мюнхау]

ты настаиваешь на 1/2 потому что думаешь что ты оба раза случайно выбираешь карту. Эта проблема на "зависимую" вероятность. Вся фишка в том что я(диллер) знаю какие карты проигрышные и убираю только их оставляя скорее всего единственную выигрышную карту из 99 оставшихся.

Ты сам сказал что вероятность того что среди 99 карт есть выигрышная 99%. Я убрал из них только проигрышные. Значит вероятность того что оставшаяся карта выигрышная 99%

Тогда, ты прав. У меня вероятность выигрыша 1/100, у тебя 99/100.

[elfy]

естественно. Ночь любви со мной
Я спрашивала про приз для меня, а не для тебя:239:

[Dima424]

Не, когда выбираеш 1ую карту, вероятность, что она выигрышная 1/3, того, что выигрышная одна из оставшихся - 2/3. Когда дилер убирает проигрышную из 2-х карт, вероятность того, что оставшаяся выигрышная остаётся 2/3
Нужно менять

1/3... вторая то карта у тебя в руках может быть выйгрышная

[реднек]

Марик, признайся лучше где ты таких работодателей находишь с вопросами интересными. А то обычно вопросы на 66.7% совпадают как под копирку и являются гораздо более дебильными. Типа что такое хэш, или какие типы JOIN ов бывают. Еще и у доски отвечать как школьник, от руки рисуя код мелом, я от этого вообще выпадаю. Ну их на фиг таких. Какое интервью такая и работа будет потом.

[Dima424]

А, Б, Ц

И чоосе А:
Деалер шощс Б, тхерефоре Б < C

Two cases:
1. B < C && A < C (C wins: 1/3)
2. B < C && A > Ц (А щинс: 1/3)

Цасе 1 хаппенс тщице, тхерефоре 66.7%

4 вариант... 1 правельная карта в руках обменена И не обменена, И неправельная, тоже обмененая или нет....

[Яправ]

Марик, признайся лучше где ты таких работодателей находишь с вопросами интересными. А то обычно вопросы на 66.7% совпадают как под копирку и являются гораздо более дебильными. Типа что такое хэш, или какие типы JOIN ов бывают. Еще и у доски отвечать как школьник, от руки рисуя код мелом, я от этого вообще выпадаю. Ну их на фиг таких. Какое интервью такая и работа будет потом.

вот еще вопрос: у тебя есть язык программирования который может делать любые алгебраические вычисления, генератор случайных чисел выдающий число он нуля до единицы и sorted array с 5ю числами. придумай самый быстрый алгоритм использующий наименьшее колличество памяти который бы randomize этот array

[реднек]

4 вариант... 1 правельная карта в руках обменена И не обменена, И неправельная, тоже обмененая или нет....

Есть 100% вариант. Узнать карту со 100%.

[elfy]

1/3... вторая то карта у тебя в руках может быть выйгрышная

Нет, то, что у меня выигрышная - 1/3, у дилера оставшаяся из 2-х 2/3
Вероятность того, что хотя бы 1 из 3х выигрышная равна единице
Та, что у меня в руке - 1/3
Хотя бы Одна из 2-х оставшихся - 2/3

[Alex_3112]

самый быстрый алгоритм использующий наименьшее колличество памяти

Так по чему оптимизировать в первую очередь - по скорости или по памяти?

[реднек]

вот еще вопрос: у тебя есть язык программирования который может делать любые алгебраические вычисления, генератор случайных чисел выдающий число он нуля до единицы и sorted array с 5ю числами. придумай самый быстрый алгоритм использующий наименьшее колличество памяти который бы randomize этот array

Мля, меня бесят такими вопросами на интервью, в реальности с алгоритмическими задачами приходится сталкиватьс1 в 0.01% случаев, на практике же пишешь:
[1,2,3,4,5].shuffle

И тратишь на это 1 сек.

[Dima424]

Есть 100% вариант. Узнать карту со 100%.

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

[реднек]

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

Есть есть.

[Dima424]

Нет, то, что у меня выигрышная - 1/3, у дилера оставшаяся из 2-х 2/3
Вероятность того, что хотя бы 1 из 3х выигрышная равна единице
Та, что у меня в руке - 1/3
Хотя бы Одна из 2-х оставшихся - 2/3

перечитайте пожалуйста вопрос, вероятность выйгрыша при обмене карт 50%, таже И без обмена...

вероятность того что из 2х оставшихся карт действительно 2/3, но нам нужно сделать еще один шаг чтоб дойти до конца... а именно обменять карту или нет

[Alex5448]

Надо пронумеровать банки от 1 до 6.
Взять из первой 1 конфету, из второй 2, из третьей 3 и так далее.
Затем взвешиваем все эти конфеты.
Если бы все конфеты были по 15 грамм, то
общий вес составил бы 21х15=315 грамм
Если первая банка по 14 грамм, то вес будет на 1 грамм меньше
(т.к. мы взяли оттуда 1 конфету).
Если 14 граммовые были во второй, то на 2 грамма меньше.
И так далее.
:110:

[Бугор]

:110:

наткнулся вот
это правильный перевод?

http://www.youtube.com/watch?v=A4GVKymQu8Q

[elfy]

перечитайте пожалуйста вопрос, вероятность выйгрыша при обмене карт 50%, таже И без обмена...

вероятность того что из 2х оставшихся карт действительно 2/3, но нам нужно сделать еще один шаг чтоб дойти до конца... а именно обменять карту или нет

Перечитала
Алгоритм указывает на то, чтобы менять, при ером вероятность выигрыша 2/3, если не поменяешь, ро 1/3

[Alex5448]

наткнулся вот
это правильный перевод?

http://www.youtube.com/watch?v=A4GVKymQu8Q
Точный перевод.

[STYLE]

:110:

Если бы ты мне ответил на мой вопрос сразу, то получил бы такой же ответ от меня. :117:

[Бугор]

Точный перевод.

хера се
извиняйте мужики
знаю не по тему ссылка

[Яправ]

Так по чему оптимизировать в первую очередь - по скорости или по памяти?

Надо с чего-то начинать. Какое у тебя Big "O"?

[Alex_3112]

Какое у тебя Big "O"?

Что-то мне подсказывает, что Big O измеряется не в инчах?
:)

[Яправ]

Что-то мне подсказывает, что Big O измеряется не в инчах?
:)

http://en.wikipedia.org/wiki/Big_O_notation

фактически измерение эффективности алгоритма при наихудших условиях

[Барон_Мюнхау]

http://en.wikipedia.org/wiki/Big_O_notation

фактически измерение эффективности алгоритма при наихудших условиях

http://rinseorrepeat.files.wordpress.com/2011/07/the-big-o.jpg

[Alex_3112]

http://en.wikipedia.org/wiki/Big_O_notation

фактически измерение эффективности алгоритма при наихудших условиях

Как я понял, в задачке спрашивают про это:
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

[Бугор]

http://ic.pics.livejournal.com/gold_manaa/44544527/1431956/1431956_original.jpg

[Джентльмен]

еще раз объясняю: тебе предлогают выбрать из трех карт(одинаковых) а, b и с . Допустим ты выбрал а. значит осталиь карты b и c. Я тебе не даю проверить еще выигрышная карта которую ты выбрал или нет. Вместо этого я из двух оставшихся показываю тебе одну карту которая проигрышная(допустим это b). Я предлогаю тебе поменять свой выбор. У тебя осталось только два выбора а и с так как я тебе показал что карта b проигрышная. -- таковы условия игры.

Теперь вопрос: можно ли придумать алгоритм выбора карт который повышает твои шансы.
меняю, если a меньше или равна b

иначе - нет

[Olezhik]

буду тут скидывать разные задачки.

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

Вопрос: каким бы вы алгоритмом воспользовались в такой игре и какова была бы вероятность выигрыша при таком алгоритме?

Правельны ответ [Monty Hall problem]

http://en.wikipedia.org/wiki/Monty_Hall_problem

[Барон_Мюнхау]

http://ic.pics.livejournal.com/gold_manaa/44544527/1431956/1431956_original.jpg

Бугор, а за каждый правильный ответ, нальёшь по стакану своего фирменного первача?

[Бугор]

Бугор, а за каждый правильный ответ, нальёшь по стакану своего фирменного первача?

без пол-литра тут не обойтись :111:

[Барон_Мюнхау]

без пол-литра тут не обойтись :111:

71377

[Alex_3112]

Бугор, а за каждый правильный ответ, нальёшь по стакану своего фирменного первача?

Второклассникам? ;)

[реднек]

Для плоскости любые три точки расположеные не на дистанции 1 друг от друга будут обладать таким свойством. Значит для плоскости 5, для 3х мерного пространства 8+1 = 9.

Яправ, я прав?