У меня вопрос был: "сколько человек надо набрать в одну комнату чтоб у кого-то д.р был в тот же день что и у меня c вероятностю > 1/2". Решение содержит степень, оттуда и логарифм.
Здравствуйте, AlexMld, Вы писали:
AM>Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>>Ещё раз — это не Birthday Paradox. "Same birthday as you" в wiki находится в разделе "Other birthday problems" и там есть явное разграничение who is who: EP>>
EP>>Same birthday as you.
EP>>Note that in the birthday problem, neither of the two people is chosen in advance. [...]
Нет никакого "является частью".
AM>Блин, ну хочешь, поставь "Birthday Paradox" в кавычки. Собственно, я имел ввиду класс проблем коллизий случайных значений из диапазона. Никого не интересует, когда ты родился, интересуют вероятности коллизий значений хеш-функций. AM>Опять же, это задачи одного класса, возьми количество человек=2 и получишь одну и ту же формулу для paradox и same birthday. Вероятность того, что мы с тобой родились в один и тот же день = 1/365 как ни крути.
В случае birthday paradox кол-во человек составит 23, а в данной мне задаче 261. Мне кажется, что разница есть, и это не совсем birthday paradox, так как не вижу в числе 261 парадокс, в отличие от числа 23.
05.11.2013 19:03, kashtan пишет:
> У меня вопрос был: "сколько человек надо набрать в одну комнату чтоб у > кого-то д.р был в тот же день что и у меня c вероятностю > 1/2". Решение > содержит степень, оттуда и логарифм.
Вот что интересно, неужели существуют люди, кто может сходу решить эту
задачку на собеседовании за 15 минут.
З.Ы. Я не про вспомнить решение вчера прочитанное решение.
Здравствуйте, kashtan, Вы писали:
K>В случае birthday paradox кол-во человек составит 23, а в данной мне задаче 261. Мне кажется, что разница есть, и это не совсем birthday paradox, так как не вижу в числе 261 парадокс, в отличие от числа 23.
Блин, вот вы нудные Я нигде не говорил, что именно эта задача — birthday paradox. Я лишь привел ссылку на страничку birthday problem, которая содержит анализ в том числе и конкретно этой задачи (Same birthday as you).
Кстати, зная вероятность для одной можно получить вероятность для другой, даже не зная количество "дней в году", так что связь между задачами довольно-таки прямая, не зря их обычно рассматривают вместе.
05.11.2013 20:54, AlexMld пишет:
> Кстати, зная вероятность для одной можно получить вероятность для > другой, даже не зная количество "дней в году", так что связь между > задачами довольно-таки прямая, не зря их обычно рассматривают вместе.
Ладно, вот вам еще одна задачка из ТВ для собеседований на шарики:
Предположим, что в комнате находится N больших стеклянных урн, в каждой
из которых находится большое число разноцветных шаров. Предполагается,
что использовано M различных цветов для окраски шаров. Некий находящийся
в этой комнате демон в соответсвии с неизвестным случайным законом
выбирает начальную урну. Из этой урны также случайным образом
извлекается шар и его цвет запоминается в качестве первого наблюдения.
Затем шар возвращается в урну, из которой он извлечен. Далее по номеру
урны и некоторому вероятностному правилу выбора осуществляется переход к
новой урне, и процесс извлечения шара повторяется. В результате
порождается некоторая последовательность наблюдений, состоящая из цветов
извлекаемых шаров.
Вопросы можете сформулировать сами.
Да, к чему это я привел, что если не знаете что это, фиг даже за
несколько лет сами сделаете.
Так и с задачей на дни рождения, если есть несколько дней поразмышлять
над ней и это будет оплачено, то ее решить можно, но на собеседовании за
15 мин, только вспомнить, если читал пару дней назад.
Бред, что они этими тестами проверяют, что кандидат получил инсайдерскую
инфу о вопросах на собеседовании или то, что случайно пару дней назад
прочитал от нефиг делать.
Здравствуйте, Vzhyk, Вы писали:
V>Да, к чему это я привел, что если не знаете что это, фиг даже за V>несколько лет сами сделаете. V>Так и с задачей на дни рождения, если есть несколько дней поразмышлять V>над ней и это будет оплачено, то ее решить можно, но на собеседовании за V>15 мин, только вспомнить, если читал пару дней назад. V>Бред, что они этими тестами проверяют, что кандидат получил инсайдерскую V>инфу о вопросах на собеседовании или то, что случайно пару дней назад V>прочитал от нефиг делать.
Хешмапы — самые быстрые структуры для поиска информации, поэтому все Гуглы/Бинги на них повернуты. Меня Гугл пытал с одной задачей, бинарный поиск их по скорости не устраивал, не успокоились, пока я на хешмап ее не переделал. Так что коллизии — это один из популярных вопросов. Не обязательно помнить точно, но вывести надо уметь.
05.11.2013 21:41, AlexMld пишет:
> Хешмапы — самые быстрые структуры для поиска информации,
Бред, только в конкретных случаях.
> поэтому все > Гуглы/Бинги на них повернуты. Меня Гугл пытал с одной задачей, бинарный > поиск их по скорости не устраивал, не успокоились, пока я на хешмап ее > не переделал.
Теперь понятно, почему их продукты такое дерьмо, кроме поиска, который
написали им давно и пока они его не сломали полностью, но стремятся к этому.
> Так что коллизии — это один из популярных вопросов. Не > обязательно помнить точно, но вывести надо уметь.
Так вопрос же через жопу о вероятностях совпадения дней рождения.
V>Бред, что они этими тестами проверяют, что кандидат получил инсайдерскую V>инфу о вопросах на собеседовании или то, что случайно пару дней назад V>прочитал от нефиг делать.
Ну или насколько хорошо он не забыл (и учил) вчерашний университетский курс лекций по cs.
Я все же склоняюсь к мысли, что такой способ набора ориентирован все же на набор вчерашних студентов соответсвующей специальности.
Вообщем довольно логичный способ, но в наших реалиях он не работает, потому что многие "наши" сегодняшние разработчики — это люди для которых изучение cs не являлось профильным в силу разных причин.
В результате кто-то самостоятельно изучил какие-то одни (необходимые для своей области) куски cs, кто-то другие. Ну а потом вся "высокая математика" сама собою забылась, остался подход который позволяет быстро ознакомится и вникнуть в новую область при необходимости.
Здравствуйте, AlexMld, Вы писали:
AM>В чем бред-то, если O(1)?
Только если вы ищете по ключу, и мало коллизий.
Если вам, к примеру, нужно искать наиболее близкое значение (неточное совпадение), то получите O(N), так что структура все-таки не универсальная.
Здравствуйте, nile, Вы писали:
AM>>В чем бред-то, если O(1)? N>Только если вы ищете по ключу, и мало коллизий. N>Если вам, к примеру, нужно искать наиболее близкое значение (неточное совпадение), то получите O(N), так что структура все-таки не универсальная.
Да никто не говорит, что универсальная. Это повод называть бредом утверждение, что структура с временем поиска O(1) — самая быстрая?
Это как вам показывают самую быструю машину, а вы называете это бредом, так как "этож только, если не по бездорожью".
AM>Да никто не говорит, что универсальная. Это повод называть бредом утверждение, что структура с временем поиска O(1) — самая быстрая?
O(1) это условность. Я бы настороженно относился к индивидам которые бездумно делают выводы о быстроте из этого O(1).
Вычисление хэша зависит от размера ключа.
Поэтому там на самом деле не O(1), а O(размера ключа) ~ O(log количества ключей)
Хэшмеп действительно часто быстрее других, но O(1) это вовсе не главная причина тому.
Скорее причины в том, что можно вычислять хэш с малым кол-вом условных бранчей, плюс доступ к памяти более-менее локальный.
D>Вычисление хэша зависит от размера ключа. D>Поэтому там на самом деле не O(1), а O(размера ключа) ~ O(log количества ключей)
А ты забавный
Биг-О считают как зависимость от размера коллекции. Размер ключа по отношению к размеру коллекции считается константным, поэтому и получается О(1). При этом, естественно, всегда стоит упомянуть, что это при наличии хорошей хэш-функции, а при плохой хэш-функции можем просесть вплоть до худшего случая — О(n).
Здравствуйте, avpavlov, Вы писали:
A>А ты забавный
A>Биг-О считают как зависимость от размера коллекции. Размер ключа по отношению к размеру коллекции считается константным, поэтому и получается О(1). При этом, естественно, всегда стоит упомянуть, что это при наличии хорошей хэш-функции, а при плохой хэш-функции можем просесть вплоть до худшего случая — О(n).
Да не, в принципе он все правильно говорит. Тут как и с Радикс-сорт константная асимптотичность весьма условна. Но на деле опять получается цепляние к словам. за что я и "люблю" наши форумы.
Здравствуйте, AlexMld, Вы писали:
AM>Здравствуйте, avpavlov, Вы писали:
A>>А ты забавный
A>>Биг-О считают как зависимость от размера коллекции. Размер ключа по отношению к размеру коллекции считается константным, поэтому и получается О(1). При этом, естественно, всегда стоит упомянуть, что это при наличии хорошей хэш-функции, а при плохой хэш-функции можем просесть вплоть до худшего случая — О(n).
AM>Да не, в принципе он все правильно говорит. Тут как и с Радикс-сорт константная асимптотичность весьма условна.
06.11.2013 9:43, AlexMld пишет:
> Да никто не говорит, что универсальная. Это повод называть бредом > утверждение, что структура с временем поиска O(1) — самая быстрая?
Бред уже про O(1).
