воскресенье, 28 февраля 2016 г.

Задача про визирей и жен

Было у султана N=12 визирей. Узнал он как-то, что у некоторых визирей неверные жены. Решил он им наказание устроить. Сделал так: каждого визиря с его женой посадили в полностью изолированные комнаты, и было им сказано, что сидеть им взаперти, пока все неверные жены не будут убиты своими супругами. Каждое утро все комнаты обходит слуга, проверяя выполнение этого условия. Как только выясняется, что все неверные жены мертвы, всех выпускают. На K=3-ий день всех выпустили, причем все верные жены остались живы. Как визири догадались? Уточнение. Все визири очень умны, и сплетней во дворце предостаточно, так что каждый визирь знает, верная или неверная жена у каждого другого визиря, но ничего не знает про свою. Никакого обмена информацией, пока они взаперти, нет.

четверг, 28 января 2016 г.

Паттерны Фаулера

После прочтения книги Мартина Фаулера Patterns of Enterprise Application Architecture у меня остались весьма двойственные впечатления. С одной стороны авторитет и опыт автора заставляет с уважением относиться к его произведению, тем более что в книги действительно можно найти не мало полезной информации по различным паттернам проектирования. Однако, многие паттерны уже давно встроены в стандартные библиотеки .Net framework и воспринимаются программистами как очевидная данность, в частности, паттерны для работы с данными. Кроме того некоторые вещи сейчас потеряли актуальность, например, паттерны, предлагающие варианты инкапсуляции создания объектов. Видимо, на момент написания книги подход Inversion of Control еще не был популярен.
Из паттернов Фаулера, которые мне понравились, и которые я хотел бы отметить, можно выделить следующие:

  1. Сценарий Транзакций vs модель предметной области
  2. Слой служб (Service Layer)
  3. MVC (Model View Controller)
  4. Интерфейс удаленного доступа (Remote Facade)
  5. Оптимистическая автономная блокировка (Optimistic Offline Lock)
  6. Пессимистическая автономная блокировка (Pessimistic Offline Lock)
  7. Блокировка с низкой степенью детализации (Coarse-Grained Lock)
  8. Неявная блокировка (Implicit Lock)

вторник, 26 января 2016 г.

Задача про заключенных и лампочку

Ниже приведена задача про заключенных и лампочку (одна из самых простых вариаций).
В тюрьме находится 100 заключенных. Начальник тюрьмы сказал им:
«Я дам вам шанс выбраться на свободу. Сначала вы поговорите друг с другом, а потом я рассажу вас по отдельным камерам, и общаться вы больше не сможете. Иногда я буду одного из вас отводить в комнату, в которой есть лампа (вначале она выключена). Уходя из комнаты, вы можете оставить лампу как включенной, так и выключенной.
Если в какой-то момент кто-то из вас скажет мне, что вы все уже побывали в комнате, и будет прав, то все вы отправитесь на свободу, а если неправ, то останетесь здесь навечно.

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

воскресенье, 17 января 2016 г.

Задача про поезд и вагоны

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

четверг, 14 января 2016 г.

Задача про числа

Петя Петров загадывает три положительных числа X, Y и Z. Вы говорите ему три коэффициента a1, b1 и c1.
Далее Петя сообщает вам значение следующего выражения:
k1 = a1*X + b1*Y + c1*Z
Затем вы снова говорите Пети три коэффициента a2, b2 и c2.
На что Петя вам опять сообщает результат выражения:
k2 = a2*X + b2*Y + c2*Z.

Ваша задача подобрать все коэффициенты таким образом, чтобы после второго ответа Пети вычислить загаданные им числа X, Y и Z.

Вопросы HR менеджеров на собеседовании


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

  1. Назовите самую интересную задачу, которую вам приходилось решать. Почему она была интересна для вас?
  2. С каким менеджером вы не хотели бы работать?
  3. Опишите ваш проект мечты, чем хотелось бы заниматься в идеальном мире?
  4. Почему ушли с предыдущего места работы?
  5. Что вас не устраивает на текущем месте работы? Если бы была возможность, то что бы вы там поменяли?
  6. Какие задачи приходится решать на текущем месте работы?
  7. Какие есть к нам вопросы?

четверг, 24 декабря 2015 г.

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

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

Структуры данных

  1. Linked List
  2. Skip List
  3. Бинарное дерево, алгоритмы балансировки
  4. Hashtable
  5. Куча
  6. Графы

Алгоритмы

  1. Динамическое программирование
  2. BIT Manipulation
  3. Сортировка: quick sort, merge sort, heap sort, radix sort
  4. Алгоритмы на графах
    1. Остовное дерево‎
    2. Алгоритм Прима
    3. Алгоритм Флойда — Уоршелла
    4. Алгоритм поиска A*
    5. Топологическая сортировка
    6. BFS
    7. DFS
    8. Поиск максимального потока
  5. *
Небольшая шпаргалка по алгоритмам от Robert Sedgewick: