V>>3 технических интервью + 1 с ХР (у тех, кого сразу не признали профнепригодным).
A>Ни хрена подобного. ХР у многих был 1м, 2м или 3м, т.е. он просто как и остальные интервьюверы участвовал в ротации.
A>У некоторых, кстати, было 4 тех интервьювера (и 1 хр)
V>>Ну и кто-то получил оффер, кто-то — нет.
A>Оффер (если мы под этим словом понимаем приглашение занять должность на определённых условиях), мне кажется, никто не получил
K>Был в начале октября. Прошел 5 интервью и все технические. В итоге получил просто отказ.
Это потому что в Бинг набирали только в конце октября. А ты 5 интервью прошел куда то в другое место
05.11.2013 19:03, kashtan пишет:
> У меня вопрос был: "сколько человек надо набрать в одну комнату чтоб у > кого-то д.р был в тот же день что и у меня c вероятностю > 1/2". Решение > содержит степень, оттуда и логарифм.
Вот что интересно, неужели существуют люди, кто может сходу решить эту
задачку на собеседовании за 15 минут.
З.Ы. Я не про вспомнить решение вчера прочитанное решение.
AM>Да никто не говорит, что универсальная. Это повод называть бредом утверждение, что структура с временем поиска O(1) — самая быстрая?
O(1) это условность. Я бы настороженно относился к индивидам которые бездумно делают выводы о быстроте из этого O(1).
Вычисление хэша зависит от размера ключа.
Поэтому там на самом деле не O(1), а O(размера ключа) ~ O(log количества ключей)
Хэшмеп действительно часто быстрее других, но O(1) это вовсе не главная причина тому.
Скорее причины в том, что можно вычислять хэш с малым кол-вом условных бранчей, плюс доступ к памяти более-менее локальный.
А что именно-то "интересно"?
3 технических интервью + 1 с ХР (у тех, кого сразу не признали профнепригодным).
Те, кого отсеяли сразу, обошлись без общения с ХР.
Ну и кто-то получил оффер, кто-то — нет.
J>Здравствуйте, Anatoliy777, Вы писали:
J>Да интересно узнать
Тоже был в начале октября в image video local search. Тоже отказали.
Ответил почти на все где-то бывало тормозил. Ехал из Питера и так получилось рубашку в глаженном виде не довез. Наверно не понравился мятый вид.
Собеседовали приятные люди, понравились больше чем те что из амазона в Киеве . Задачки все про алгоритмы, кроме двух коротких вопросов про c++11 и boost ublas.
Единственно что неприятно расходы на дорогу до сих пор не компенсировали и молчат. Около 5 тыс.
В основном были алгоритмы, но попался мне дядька-математик. Спросил про вероятность совпадения д.р. с моим, посчитал до логарифмов — дядька захотел конкретное число. Ну и вспоминали мы с ним аппроксимацию логарифма
Я тоже беседовал с Амазоном, у них задачи по проще, больше на структуры данных, чем на алгоритмы.
Мне еще ни Амазон ни Майкрософт не оплатили расходы.
Здравствуйте, TarasKo, Вы писали:
TK>Тоже был в начале октября в image video local search. Тоже отказали. TK>Ответил почти на все где-то бывало тормозил. Ехал из Питера и так получилось рубашку в глаженном виде не довез. Наверно не понравился мятый вид. TK>Собеседовали приятные люди, понравились больше чем те что из амазона в Киеве . Задачки все про алгоритмы, кроме двух коротких вопросов про c++11 и boost ublas. TK>Единственно что неприятно расходы на дорогу до сих пор не компенсировали и молчат. Около 5 тыс.
Здравствуйте, kashtan, Вы писали:
K>В основном были алгоритмы, но попался мне дядька-математик. Спросил про вероятность совпадения д.р. с моим, посчитал до логарифмов — дядька захотел конкретное число. Ну и вспоминали мы с ним аппроксимацию логарифма
Birthday Paradox, вроде, один из самых популярных вопросов на собеседованиях? http://en.wikipedia.org/wiki/Birthday_problem
Только я не помню, чтоб в нем про логарифмы что-то было.
Вообще, этот вопрос имеет прямое отношение к вероятности коллизий в хеш-таблицах, поэтому они его любят.
Здравствуйте, AlexMld, Вы писали:
K>>В основном были алгоритмы, но попался мне дядька-математик. Спросил про вероятность совпадения д.р. с моим, посчитал до логарифмов — дядька захотел конкретное число. Ну и вспоминали мы с ним аппроксимацию логарифма AM>Birthday Paradox, вроде, один из самых популярных вопросов на собеседованиях? AM>http://en.wikipedia.org/wiki/Birthday_problem AM>Только я не помню, чтоб в нем про логарифмы что-то было. AM>Вообще, этот вопрос имеет прямое отношение к вероятности коллизий в хеш-таблицах, поэтому они его любят.
Это не Birthday Paradox. Я думаю вопрос был как раз рассчитан на то, чтобы отсеять тех, кто сходу будет пытаться приплетать Birthday Paradox, услышав слово Birthday
А лографим там видимо был во время поиска N для заданной вероятности.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
AM>>http://en.wikipedia.org/wiki/Birthday_problem
EP>Это не Birthday Paradox. Я думаю вопрос был как раз рассчитан на то, чтобы отсеять тех, кто сходу будет пытаться приплетать Birthday Paradox, услышав слово Birthday
Здравствуйте, AlexMld, Вы писали:
AM>>>Birthday Paradox, вроде, один из самых популярных вопросов на собеседованиях? AM>>>http://en.wikipedia.org/wiki/Birthday_problem EP>>Это не Birthday Paradox. Я думаю вопрос был как раз рассчитан на то, чтобы отсеять тех, кто сходу будет пытаться приплетать Birthday Paradox, услышав слово Birthday AM>Same birthday as you — это часть Birthday Problem
Ещё раз — это не Birthday Paradox. "Same birthday as you" в wiki находится в разделе "Other birthday problems" и там есть явное разграничение who is who:
Same birthday as you.
Note that in the birthday problem, neither of the two people is chosen in advance. [...]
Здравствуйте, 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. [...]
Нет никакого "является частью".
Блин, ну хочешь, поставь "Birthday Paradox" в кавычки. Собственно, я имел ввиду класс проблем коллизий случайных значений из диапазона. Никого не интересует, когда ты родился, интересуют вероятности коллизий значений хеш-функций.
Опять же, это задачи одного класса, возьми количество человек=2 и получишь одну и ту же формулу для paradox и same birthday. Вероятность того, что мы с тобой родились в один и тот же день = 1/365 как ни крути.
Здравствуйте, AlexMld, Вы писали:
AM>Никого не интересует, когда ты родился, интересуют вероятности коллизий значений хеш-функций.
Отчего же — случаи где применима именно "same birthday as you", а не "birthday paradox" — не так редки.
Например мы делаем серию тестов — у каждого теста есть output большого размера. Нет никакого желания хранить и распространять весь набор gold output файлов, поэтому распространяется набор gold hash'ей. Тут интересны только коллизии результата теста, с его gold hash, то есть "same birthdayhash as yougold".
И нужно уметь определять что и где неприменимо — большая разница, растёт ли количество пар линейно или квадратично
AM>Опять же, это задачи одного класса, возьми количество человек=2 и получишь одну и ту же формулу для paradox и same birthday. Вероятность того, что мы с тобой родились в один и тот же день = 1/365 как ни крути.
Это казуистика. C тем же успехом можно сказать что сложение и умножение — "это задачи одного класса", так как 2*2 и 2+2 дают одинаковый результат.
У меня вопрос был: "сколько человек надо набрать в одну комнату чтоб у кого-то д.р был в тот же день что и у меня 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.
Здравствуйте, 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) — самая быстрая?
Это как вам показывают самую быструю машину, а вы называете это бредом, так как "этож только, если не по бездорожью".
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).
06.11.2013 10:22, avpavlov пишет:
> получается О(1). При этом, естественно, всегда стоит упомянуть, что это > при наличии хорошей хэш-функции, а при плохой хэш-функции можем просесть > вплоть до худшего случая — О(n).
Как говориться, главное как продать (тьфю подать). Итого O(1) или в
промежутке от O(1) до O(n) в зависимости от много.
V>Как говориться, главное как продать (тьфю подать). Итого O(1) или в V>промежутке от O(1) до O(n) в зависимости от много.
Во многих случаях ключи известны заранее, можно проверить хэш-фунцию. В остальных случаях можно собирать статистику, так что проблема внезапного перехода от О(1) к О(n) надумана
Здравствуйте, avpavlov, Вы писали:
A>Ну, давай, покажи, как размер ключа зависит от размера коллекции, а то какой-то пустопорожний спор получается.
Количество коллизий зависит от размера коллекции и длины ключа. Соответственно для больших коллекций нужны более длинные ключи. Как ты будешь делать ресайзинг с ростом коллекции без изменения размера ключа?
Здравствуйте, AlexMld, Вы писали:
AM>Количество коллизий зависит от размера коллекции и длины ключа. Соответственно для больших коллекций нужны более длинные ключи. Как ты будешь делать ресайзинг с ростом коллекции без изменения размера ключа?
Блин, не так выразился. Это я про размер значения хеш-функции, который тоже растет.
А с ключами — Ключи должны быть уникальными? Значит, чем больше коллекция, тем длиннее нужны ключи. Длина уникального ключа должна быть минимум log от размера коллекции.
06.11.2013 11:29, avpavlov пишет:
> Во многих случаях ключи известны заранее, можно проверить хэш-фунцию.
Корректнее сказать, в тех случаях, где хеш-функции уже придуманы. А
много это или мало, зависит от области применения.
> В > остальных случаях можно собирать статистику, так что проблема внезапного > перехода от О(1) к О(n) надумана
Перешли в область верований?
З.Ы. Но, я уже понял, с хешами это новая дурь на собеседованиях (до
этого были i+++++++++i, затем виртуальные деструкторы с конструкторами,
теперь это).
Я раньше не решал эту задачу. У меня спросили точную цифру, вывести совсем было не сложно — воспользовался отрицанием событий. Но довести до конкретного числа я уже в одиночку не смог
Здравствуйте, AlexMld, Вы писали:
AM>Здравствуйте, Vzhyk, Вы писали:
V>>Да, к чему это я привел, что если не знаете что это, фиг даже за V>>несколько лет сами сделаете. V>>Так и с задачей на дни рождения, если есть несколько дней поразмышлять V>>над ней и это будет оплачено, то ее решить можно, но на собеседовании за V>>15 мин, только вспомнить, если читал пару дней назад. V>>Бред, что они этими тестами проверяют, что кандидат получил инсайдерскую V>>инфу о вопросах на собеседовании или то, что случайно пару дней назад V>>прочитал от нефиг делать.
AM>Хешмапы — самые быстрые структуры для поиска информации, поэтому все Гуглы/Бинги на них повернуты. Меня Гугл пытал с одной задачей, бинарный поиск их по скорости не устраивал, не успокоились, пока я на хешмап ее не переделал. Так что коллизии — это один из популярных вопросов. Не обязательно помнить точно, но вывести надо уметь.
Здравствуйте, dilmah, Вы писали:
D>O(1) это условность. Я бы настороженно относился к индивидам которые бездумно делают выводы о быстроте из этого O(1).
+1. Нотацию O придумали математики, информатики украли у математиков, программисты у математиков. Я понимаю, что у бедных информатиков нету ничего круче Тьюринговой машины, но (блин) у программистов имеется профайлеры, и меня удивляют программисты, которые смело говорят про O, да еще и гордятся
Здравствуйте, AlexMld, Вы писали:
AM>Здравствуйте, AlexMld, Вы писали:
AM>>Количество коллизий зависит от размера коллекции и длины ключа. Соответственно для больших коллекций нужны более длинные ключи. Как ты будешь делать ресайзинг с ростом коллекции без изменения размера ключа?
AM>Блин, не так выразился. Это я про размер значения хеш-функции, который тоже растет.
Я, думаю, что ты опять не так выразился Значение хэш-функции — это номер цепочки/bucket'а
Никуда это значение не растёт, оно просто всегда равно одному из доступных номеров
Вот число доступных корзин может меняться, если хэш-таблица достаточно умная и подстраивается под размер коллекции для уменьшения числа коллизий. Но это зависит от имплементации и не имеет никакого отношения к обсуждению абстрактной хэш-тбалицы и её О-нотации.
AM>А с ключами — Ключи должны быть уникальными? Значит, чем больше коллекция, тем длиннее нужны ключи.
Длина ключа не зависит от размеров коллекции. Длина ключа вообше не имеет отношение к хэш таблицам. Бывают маленькие коллекции с большими ключами, бывают большие коллекции с маленькими ключами.
AM>Длина уникального ключа должна быть минимум log от размера коллекции.
Коллекция на 4 млрд 32х битных интов прекрасно мэппится на 4байтные ключи. Расскажи, где ты здесь видишь "минимум лог от размера коллекции"?
06.11.2013 13:32, kashtan пишет:
> но (блин) у программистов имеется > профайлеры, и меня удивляют программисты, которые смело говорят про O, > да еще и гордятся
Это сейчас основной критерий отбора сильных программистов. И неважно,
что эта нотация означает, главное O(1) это круто O(n^n) это фуууууууу.
Здравствуйте, avpavlov, Вы писали:
AM>>Блин, не так выразился. Это я про размер значения хеш-функции, который тоже растет.
A>Я, думаю, что ты опять не так выразился Значение хэш-функции — это номер цепочки/bucket'а A>Никуда это значение не растёт, оно просто всегда равно одному из доступных номеров
Не значение растет, а его размер, т.е. диапазон. Значение хэш-функции — это типа индекса для массива. Чем больше массив, тем больший диапазон индексов тебе нужен. Скажем, байтом ты можешь адресовать 256 bucket'ов, а двумя байтами — 65536
A>Длина ключа не зависит от размеров коллекции. Длина ключа вообше не имеет отношение к хэш таблицам. Бывают маленькие коллекции с большими ключами, бывают большие коллекции с маленькими ключами.
Большие коллекции с маленькими _уникальными_ ключами? Это как?
AM>>Длина уникального ключа должна быть минимум log от размера коллекции.
A>Коллекция на 4 млрд 32х битных интов прекрасно мэппится на 4байтные ключи. Расскажи, где ты здесь видишь "минимум лог от размера коллекции"?
05.11.2013 21:17, Vzhyk пишет:
> Да, к чему это я привел, что если не знаете что это, фиг даже за > несколько лет сами сделаете.
Так что с этой задачкей по ТВ?
