В декабре, у нас на работе, с интервалом в 1-3 дня выпадают 4 дня рождения сотрудников (коллектив небольшой, меньше 25 человек). Хотя совпадения в один день нет, я все же вспомнил про парадокс дней рождения и предложил коллегам условие этой задачи из теории вероятностей. К моему удивлению никто из них про эту задачу не слышал и многие принялись доказывать мне, что я не прав. Поэтому, я решил рассказать про этот парадокс (хотя в строгом смысле парадокса нет) в этом блоге:

В группе из 23-х и более человек вероятность того, что дни рождения совпадут хотя бы у двух из них, выше 50%.

За доказательством я отправляю вас в Википедию. Там все очень хорошо расписано.

Про этот парадокс я впервые прочитал в замечательной книге Рэймонда Смаллиана "Принцесса или тигр?" когда учился в школе. Он там упоминался вскользь, в одной из задач:

Как плохо быть рассеянным. Следующая история произошла на самом деле.
   Как хорошо известно, с вероятностью более 50% можно утверждать, что в группе, состоящей как минимум из 23 человек, всегда найдутся по крайней мере двое, у которых день рождения падает на одно и то же число. В свое время я преподавал математику в Принстонском университете и как-то занимался со студентами элементарной теорией вероятностей. Я объяснил своим слушателям, что если число людей в группе увеличить с 23 до 30, то вероятность того, что в ней окажутся по крайней мере двое, которые родились в один и тот же день, окажется близка к единице.
- Но, - продолжал я, - поскольку вас здесь всего 19, то вероятность того, что у двоих из вас дни рождения совпадают, будет гораздо меньше 50%.
Тут один из студентов поднял руку:
- Бьюсь об заклад, профессор, что по крайней мере у двоих из присутствующих здесь дни рождения должны совпасть.
- С моей стороны было бы не очень честно принимать ваше пари, - ответил я. - Ведь теория вероятностей целиком на моей стороне.
- Это не имеет значения, - упорствовал студент. - Я все-таки готов с вами поспорить!
- Ну, ладно, - согласился я, надеясь преподать юному скептику достойный урок. Затем я стал по очереди опрашивать студентов, с тем чтобы каждый назвал дату своего рождения. Не успели мы выслушать и половину присутствующих, как вдруг вся аудитория, в том числе и я, покатились со смеху по поводу моей бестолковости.
   Юноша, который так самоуверенно вступил со мной в спор, не знал даты рождения никого из присутствующих, за исключением, конечно, самого себя. Не догадаетесь ли вы, почему он был так уверен в своей правоте?

Ответ смотрите в комментариях.

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

Если у кого не хватит терпения, то ответы здесь.

Хочу поблагодарить читателя Ravlyk, оставившего совершенно правильный ответ на пятую задачу в комментариях:

5. На клетчатом поле 8х8 вырезали по клетке в противопол-х углах диагонали.. Можно ли замостить получившееся поле паркетинами 2х1? Ответ доказать.

Ответ: Нет.

Доказательство:

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

Спасибо!

Что-то я затянул с ответами на вопросы с собеседования в ABBYY. Да и вообще, давно ничего не писал в блоге. Надо срочно исправляться.

Сегодня рассмотрим вторую задачу:

2. Дан массив a[1],..a[N].. найти m,k (m<k) такие что a[m] + ..+a[k] — максимальна. Сложность алг-ма = N.

Вообще-то, не зная заранее решения, найти алгоритм, работающий за время O(N), в течение короткого времени (на собеседовании) довольно сложно. Те же, кто это действительно могут, работают не в ABBYY. Гораздо более полезное собеседование можно провести, убрав требование быстродействия O(N). Нетрудно написать алгоритм работающий со скоростью O(N³). Далее, легко его оптимизировать до O(N²). На этом этапе можно многое узнать о сообразительности кандидата. Используя подсказки, можно прийти к алгоритму O(N log N). Лично я именно так проводил бы собеседование, основанное на этой задаче.

Что касается решения O(N), то оно, наряду с другими вариантами, прекрасно описано в книге Джона Бентли "Жемчужины программирования" (глава 7). Этой замечательной книги, к сожалению, сейчас нет в продаже. Найти ее можно только в электронном виде (http://librus.ru/down.php?book=05753).

Приведу реализацию алгоритма из книги на C#:

	

		

			
            int[] a = { 1, 2, -2, 3, -5, 1, 1, 3};
		
		

			
            int N = a.Length;
		
		

			
 
		
		

			
            int maxSoFar = 0;
		
		

			
            int maxEndingHere = 0;
		
		

			
 
		
		

			
            for(int i = 0; i < N; i++)
		
		

			
            {
		
		

			
                maxEndingHere = Math.Max(maxEndingHere + a[i], 0);
		
		

			
                maxSoFar = Math.Max(maxSoFar, maxEndingHere);
		
		

			
            }
		
	

В этом примере вычисляется только максимальная сумма, без определения индексов m,k.  Заменив методы Max на конструкции if ... else с запоминанием индексов, несложно найти m и k.

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

Снова вынуждет вернуться к ответу на первую задачу. Как выяснилось, мое решение оказалось неоптимальным. Вот более правильное решение.

Пусть красный цвет соответствует 0, а белый - 1. Тогда, чиновник, который отвечает первым и видит цвета всех остальных, подсчитывает сумму по модулю 2 и называет получившийся цвет. С вероятностью 50% результат совпадет с его цветом. Далее, следующий чиновник, подсчитав сумму по модулю 2 всех, кто стоит перед ним, и зная ответ предыдущего, стопроцентно правильно называет свой цвет. И так по цепочке. Таким образом, действуя по этому алгоритму, стопроцентно выживут все, кроме первого (его вероятность выжить 50%).

Как и обещал, привожу ответ на первую задачу.

1. Царь построил своих чиновников в колонну (лицом к затылку следующего), надел по колпаку одного из цветов — красного или белого.. и сказал поочереди назвать цвет своего колпака. Кто не угадает — смерть. Первый отвечал тот кто видит всех и т.д. попорядку.. Вопрос: о чем должны договориться чиновники чтобы минимизировать кол-во смертей.

Исходим из предположения, что колпаки одеты случайным образом, а колонна достаточно длинная.

Очевидно, что если чиновники будут пытаться угадать свой цвет, то по теории вероятности половина из них не выживет. Чтобы увеличить вероятность правильного ответа каждый чиновник должен своим ответом передать информацию другим (т.к. он видит цвет всех колпаков).

Если каждый нечетный по счету чиновник (1-й, 3-й, 5-й и т.д.) будет называть цвет колпака, находящегося перед ним, а каждый четный повторять названный цвет, то выживут все четные чиновники и половина нечетных. Это становится легко понятным если расписать возможные комбинации пар (Б - белый, К - красный):

БК - 1-й убит
ББ - 1-й жив
КК - 1-й жив
КБ - 1-й убит

Т.е. выживут 75% чиновников.

На форуме RSDN человек делится неудачным опытом собеседования в ABBYY - не смог справиться с тестовыми заданиями. Вот что его спросили:

1. Царь построил своих чиновников в колонну (лицом к затылку следующего), надел по колпаку одного из цветов — красного или белого.. и сказал поочереди назвать цвет своего колпака. Кто не угадает — смерть. Первый отвечал тот кто видит всех и т.д. попорядку.. Вопрос: о чем должны договорится чиновники чтоб минимизировать кол-во смертей.
2. Дан массив a[1],..a[N].. найти m,k (m<k) такие что a[m] + ..+a[k] — максимальна. Сложность алг-ма = N.
3. Алгоритм вычисления a^N (N- целое) за log N шагов без выделения доп. памяти.
4. На турляндском языке дан перевод чисел:
23: апвып пвадлор вапр (пишу примерно)
334: пвап по пвадалл
.. (не помню)
Переведите 35, 343..
И в качестве контрольного выстрела еще дали задачу:
5. На клетчатом поле 8х8 вырезали по клетке в противопол-х углах диагонали.. Можно ли замостить получившееся поле паркетинами 2х1? Ответ доказать.

Ответы смотрите через пару дней. Постарайтесь решить сами. Задача номер 1 требует только логического мышления.

Было это уже давно, в феврале 2005 года. Но, так как меня часто просят рассказать про эту компанию, я решил написать здесь все, что знаю.

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

Первое собеседование

Не буду описывать расположение офиса, так как сейчас он находится в другом месте. Внутри офис состоит из "кубиков" - довольно удобно и для общения и собственное пространство создается. Довольно удобные кресла (говорят стоимостью $1000), ЖК мониторы, быстродействующие компьютеры. Но самое впечатляющее в офисе - это огромный стеклянный холодильник на кухне. Каждый день в него загружают продукты (соки, овощи, фрукты) и сотрудники могут их использовать по прямому назначению. Кроме холодильника на кухне есть все необходимое: микроволновка, кофеварка, мойка с краном.

Так вот, про собеседование. HR менеджер, Алевтина, которая оказалась очень приятной девушкой, подробно рассказала о компании и о том, чем она (компания) занимается. Затем, последовали хитрые вопросы наподобии таких: "Что вам нравится в компании, в которой вы сейчас работаете?", "Легко ли вас обидеть?", "Какими качествами должен обладать начальник?", "Расскажите про свою самую большую неудачу". Как я уже говорил, в то время я не занимался поисками работы, и, поэтому, был совершенно не готов к таким вопросам. Конечно, я что-то придумывал, но к таким вопросам надо быть готовым заранее и знать в общих чертах "правильный" ответ. Я, в свою очередь, задавал вопросы интересовавшие меня (в скобках ответы): режим работы (свободный график), отпуск (стандартные 24 календарных дня). Фирма предоставляет медицинскую страховку на всю семью (!), естественно, больничные оплачиваются.

Работа в компании начинается с месячного тренинга по методологиям PSP (Personal Software Process) и TSP (Team Software Process), т.к. по этим методологиям ведется вся разработка. Тренинги в конкретный момент времени проводятся в одном из филиалов (см. ниже), так что возможно, что сразу прийдется ехать в командировку. Уровень процессов компании, по словам Алевтины, соответствует 5 уровню CMMI.

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

Тестовое задание

Через пару дней после собеседования я получил письмо, в котором сообщалось, что я успешно справился с логическим тестом и мне предлагается выполнить тестовое задание (состоящее на самом деле из двух заданий).

Вообще-то к тестовым заданиям я отношусь так же, как и к любой другой работе: если кому-то надо, чтобы я что-то написал - это должно оплачиваться. К сожалению, тестовые задания в CQG не оплачиваются. Но, в данном случае я без колебаний сделал исключение: очень заманчивые условия работы, да и сами задания нетривиальны и хочется доказать самому себе, что можешь это сделать (правда, это только первое впечатление - ничего сверхсложного в задачах нет).

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

Второе задание называлось "Евродиффузия" и было взято из конкурсов по программированию (легко находится в Гугле по запросу Eurodiffusion). Самое сложное в нем для меня было выбрать способ решения, так как вариантов я придумал несколько. В итоге решил выбрать самый простой в реализации - не хотелось тратить много своего времени на тестовое задание (см. выше).

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

Второе (техническое) собеседование

Итак, успешно выполнив и отправив задания, через несколько дней я получил приглашение на техническое собеседование. Проводили его два программиста (по сути, а не по должности). Так как я позиционировался как .NET разработчик со знанием C++, то вопросы были, в основном, по .NET Windows Forms. Вопросов по ASP.NET небыло. Сразу скажу, что, поскольку, я раньше некоторое время работал на C++  ATL (и это было отражено в резюме), то был вопрос и из этой области, но, так как я на тот момент уже больше 2-х лет на ATL ничего не писал (о чем я сразу честно предупредил), я не смог на него ответить (хотя потом я перечитал соответствующий раздел и понял, что 2 года назад ответил бы без особого труда, т.е. вопрос не являлся сложным). Из области .NET вопросы были о многопоточности (мало сталкивался и мало что мог сказать на тот момент), очень подробно о сборщике мусора (читать Рихтера ), конечно же, об отличии структуры от класса и еще некоторые мелкие вопросы, которые уже не помню. Все вопросы были на знание и понимание архитектуры .NET. Вспоминать имена и параметры методов не просили. Алгоритмических вопросов, также, не было.

Кроме этого, у ребят были распечатки моего кода из тестовых заданий и они задавали вопросы по ним (тут проблем небыло, так как каждая строчка кода была написана мною). Указали на небольшой баг в реализации "Евродиффузии".

После окончания собеседования подошла Алевтина, переговорила с ребятами и сразу сказала, что собеседование пройдено положительно (хотя, наскролько я понял, итог не однобитовый и результатом собеседования является более точная оценка и отчет) и мне предстоит еще одно собеседование с директором.

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

Третье собеседование

Через несколько дней, согласовав время с Алевтиной, я пришел на третье собеседование, которое проводили директор филиала (возможно я немного ошибаюсь в его должности) и Алевтина. Сказать по правде, я считал, что предложение работать в компании у меня уже в кармане и вопрос будет только в зарплате. Директор задавал вопросы такого же плана, как и на первом собеседовании, некоторые, даже, повторялись, но из уст директора они звучали жестче. Разговаривать с ним было сложнее, чем с Алевтиной (грубости или чего-то подобного небыло, просто чувствовалось, что человек привык командовать). В конце собеседования он (к сожалению, не помню его имени) сказал, что не готов принят решение о моей кандидатуре прямо сейчас и должен некоторое время подумать.

Заключение

Примерно через неделю, я получил письмо с очень вежливым отказом. Было немного неприятно и грустно, но я особо не расстроился, т.к. сильно устал от всего процесса. Сейчас, оглядываясь назад, я больше сожалею не об упущенных бонусах, а об упущенной возможности поработать в очень сильной команде. Опыт работы со специалистами высокого уровня может дать очень много в плане собственного роста. Ну а бонусы просто помогают делать работу лучше и это понимают в руководстве CQG.

Часто спрашивают мое мнение о причине неудачи. Трудно сказать точно. Во-первых, как я уже говорил, я не был готов к западному стилю собеседования. Во-вторых, я позиционировался как разработчик на .NET со знанием C++. Компания же ищет разработчиков на C++ со знанием .NET (хотя, насколько я понял, большая часть кода пишется на .NET).

Полезная информация

Сайт компании: http://cqg.com/
Филиалы расположены в Ереване, Москве, Зеленограде, Самаре и Киеве. В Чикаго и Денвере находятся офисы в США.
Компания разрабатывает финансовое ПО, известное во всем мире.

Обсуждения CQG на форуме RSDN:
http://www.rsdn.ru/Forum/?mid=974668
http://www.rsdn.ru/Forum/?mid=959512
http://www.rsdn.ru/Forum/?mid=2037404

Блог инсайдера (почитайте дальше, там есть еще и про Microsoft)

Принцесса или тигр?

   У Фрэнка Стоктона есть сказка, которая называется "Принцесса или тигр?" В этой сказке один узник должен угадать, в какой из двух комнат находится принцесса, а в какой - тигр. Если он укажет на первую комнату, то женится на принцессе, если на вторую, то его (вполне возможно) растерзает тигр.

   В некотором царстве правил король. Однажды он тоже прочитал эту сказку.
-  В самый раз для моих заключенных! - сказал он своему министру. - Только я не хочу полагаться на случайности. Пусть на дверях каждой комнаты повесят по табличке, а заключенному будет кое-что сказано о них. Если узник не дурак и способен рассуждать логически, он сумеет сохранить себе жизнь и в придачу заполучить прелестную невесту.
-  Блестящая идея, ваше величество! - согласился министр.

Испытания первого дня

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

1. Первое испытание.

- А что, если в обеих комнатах сидят тигры? - спросил узник. - Что же мне тогда-то делать?
- Считай, не повезло, - ответил король.
- А если в обеих комнатах окажется по красавице? - поинтересовался узник.
- Считай, подфартило, - сказал король. - Уж это ты и сам бы мог сообразить!
- Ну, хорошо, а если в одной комнате принцесса, а в другую посадили тигра, что тогда? - не успокаивался узник.
- Вот тут-то уже все зависит от тебя! Не так ли?
- Да откуда же мне знать, где кто? - сокрушенно вздохнул узник.
   Тут король указал на таблички, прикрепленные к дверям каждой из комнат. На них было написано:

- А это правда, что здесь написано? - спросил узник.
- На одной - правда, - отвечал король, - на другой - нет.
   А вы на месте узника, какую бы дверь открыли? (Конечно, если вы предпочитаете принцессу тигру.)

2. Второе испытание.

   Итак, первый узник спас себе жизнь и на радостях отбыл вместе с принцессой.
   Таблички на дверях сменили, соответственно были подобраны и обитатели комнат. На этот раз на табличках можно было прочитать следующее:

- Истинны ли утверждения на табличках? -  спросил второй узник.
- Может, оба истинны, а может, оба ложны, -   ответил ему король.
   Какую из комнат следует выбрать второму узнику?

3. Третье испытание.

   Во время этого испытания король объявил, что опять утверждения на обеих табличках одновременно либо истинны, либо ложны. Надписи же были вот какие:

   Кто же обнаружится в первой комнате - принцесса или тигр? А во второй?

Ответы смотрите в комментариях.

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

Сегодня хочу продолжить эту тему, т.к. вчера знакомый прислал аналогичный тест, предлагавшийся на каком-то собеседовании (ему, в свою очередь, прислал другой знакомый, так что повествование от N-го лица):

Сегодня знакомый был на собеседовании в одной уважаемой (и уважающей себя) компании.
Получил на руки вот такой вот тест на логическое мышление, надо было ответить на 12 вопросов.
Я так понял, главная идея теста проверить человека на стрессоустойчивость, потому что знакомому очень хотелось встать, порвать листочки, дать в лицо hr-щику, поклониться и уйти. Я сам ответил верно на все вопросы, но меня, скорее всего спасло то, что, среди прочего, я по диплому имею право преподавать логику в учебных заведениях.
Мне объяснили так, если человек отвечает правильно на все 12 вопросов - это шоколад, а не сотрудник.
Меньше 6 - у этого человека вообще туго с логикой.

Внимание:

Тест на логическое мышление. Используйте только ту информацию, которая имеется в тексте вопроса, не полагайтесь на свой жизненный опыт.

1. Некоторые улитки являются горами. Все горы любят кошек.
Значит, все улитки любят кошек.
а) правильно
б) неправильно

2. Все крокодилы умеют летать. Все великаны являются крокодилами.
Значит, все великаны могут летать.
а) правильно
б) неправильно

3. Некоторые головки капусты - паровозы. Некоторые паровозы играют на рояле.
Значит, некоторые головки капусты играют на рояле.
a) правильно
б) неправильно

4. Две поляны никогда не похожи одна на другую. Сосны и ели выглядят совершенно одинаково.
Значит, сосны и ели не являются двумя полянами.
а) правильно
б) неправильно

5. Никто из людей не может стать президентом, если у него красный нос. У всех людей нос красный.
Значит, никто из людей не может стать президентом.
а) правильно
б) неправильно

6. Все вороны собирают картины. Некоторые собиратели картин сидят в птичьей клетке.
Значит, некоторые вороны сидят в птичьей клетке.
a) правильно
б) неправильно

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

8. Все воробьи не умеют летать. У всех воробьев есть ноги.
а) без ног воробьи не могут летать
б) некоторые воробьи не имеют ног
в) все воробьи, у которых есть ноги, не могут летать
г) воробьи не могут летать, потому что у них есть ноги
д) воробьи не могут летать и у них нет ног
е) ни одно из вышеперечисленных

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

10. Цветы - это зеленые звери. Цветы пьют водку.
а) все зеленые звери пьют водку
б) все зеленые звери являются цветами
в) некоторые зеленые звери пьют водку
г) Зеленые звери не пьют водку
д) зеленые звери не являются цветами
е)ни одно из вышеперечисленных

11. Каждый квадрат круглый. Все квадраты красные.
а) бывают квадраты с красными углами
б) бывают квадраты с круглыми углами
в) бывают круглые красные углы
г) углы и квадраты - круглые и красные
д) ни одно из вышеперечисленных

12. Хорошие начальники падают с неба. Плохие начальники могут петь.
а) Плохие начальники летят с неба вниз.
б) Хорошие начальники, которые умеют летать - могут петь.
в) некоторые плохие начальники не могут петь.
г) некоторые хорошие начальники -плохие, так как они умеют петь.
д) ни одно из вышеперечисленных

Ответы смотрите в комментариях.