Задача – 8 монет

Интересная задача, пару раз попадалась:

У вас есть чашечные весы и 8 монет. Одна из них легче чем все остальные (фальшивая). Найдите фальшивую монету за минимальное количество взвешиваний.

Удачи!

И снова интересная задача

Эту задачу я слышал от трех разных источников (собеседования в разных компаниях). Ну, так как она настолько популярна, решил предложить её и вам:

Вы находитесь в тёмной комнате, перед вами на столе лежит 100 монет. Каждая монета имеет две стороны: белую и черную. 90 из монет лежит белой стороной к верху, а остальные 10 чёрной. Вам нужно разделить эти монеты на две группы чтобы в каждой группе было одинаковое количество монет лежащих к верху черной стороной.

Удачи

Часы

Недавно мой друг послал мне фотографию часов для «гиков». Суть в них такова что каждый час от 1 до 12 представлен в виде трёх «9″ и математических операций между ними.

Попробуйте сделать это. Например 1 = (9/9) ^ 9 .

Я долго мучался над 5 =)

Удачи! Завтра выставлю саму картинку.

Интересная задача

Наткнулся в журнале у avva на интересную задачку и хочу ею с вами поделиться:

Два игрока вместе играют в игру. Есть три двери, за одной из них машина, за другой ключи, а за третей козёл. Цель первого игрока найти машину, а цель второго – ключи. Первый игрок подходит к дверям, а второго уводят за кулисы. У первого игрока есть две попытки. Если он открывает дверь а за ней нет машины, он открывает ещё одну дверь. Если в итоге он смог найти машину, его уводят, двери которые он открыл закрывают, и приводят второго игрока. Цель второго найти ключи, так же за две попытки.

Только если первый сможет найти машину, а второй ключи то они получают машину с ключами, а иначе он получают козла =)

Какой стратегии они должны придерживаться чтобы победить в 2/3 случаев?

Ответ будет через пару дней в комментах, и соответственно ссылка на источник =)

UPD. Источник: avva

Алгоритмы на графах – Часть 0: Базовые понятия

Основы

В математике, Граф – это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин, а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами).
Граф может быть ориентированным или неориентированным. В ориентированном графе, связи являются направленными (то есть пары в E являются упорядоченными, например пары (a, b) и (b, a) это две разные связи). В свою очередь в неориентированном графе, связи ненаправленные, и поэтому если существует связь (a, b) то значит что существует связь (b, a).

Новая задача

Вчера один товарищ рассказал задачу, которую предлагают решить на собеседовании в Microsoft.

Вы находитесь в комнате с тремя выключателями. На каждом из них написан их порядковый номер {1,2,3}. Все они соединены с лампочками, которые стоят на столе в другой комнате, каждая из которых тоже помечена. Вы можете зайти в комнату с лампочками всего один раз, после чего Вы должны сказать  какой лампочке соответствует каждый выключатель.

Снова задачи с собеседований

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

Первая:

Торт

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

 

 

 

 Вторая:

Листок 30 на 30

Перед вами квадратный лист белой бумаги размером 30 на 30 сантиметров. На него случайно пролили чернила. Скажите всегда ли будут существовать две точки одинакового цвета на расстоянии десяти сантиметров? Объясните свой ответ.

 

 

 

 

 

Удачи!

Задача про гномов

Опять публикую задачу (на более осмысленные посты времени пока нет, ибо сессия =)

Задача довольно старая, но многие HR любят задавать её на собеседовании. Мне её рассказал человек, который проходи собеседование в IBM.

Людоед поймал 11 гномов. И предлагает им последний шанс спастись. Он даст им 1 день договориться а потом выстроет их в ряд по росту (самый высокий в конце), и на каждого наденет шапку красного или синего цвета. То есть каждый гном видет цвета шапок всех впереди стоящих гномов. Цель каждого гнома угадать какого цвета на нём шапка. Если гном угадывает, он остается в живих, иначе людоед его съедат.

За любую попытку подсказки, или изменения интонации, людоед сразу всех съест. Можно говорить только «Красный» или «Синий» ровным, чётким голосом.

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

Удачи! Ответы как всегда, в комментариях через пару дней.

Задача

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

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

Ответ, как обычно появиться чуть позже в комментариях.

Задачи с собеседований

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

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

Начну с задачи, предложенной одному кандидату на собеседовании в Microsoft: