В какую сторону (вправо или влево) едет автобус на рисунке, и почему? Рисунок симметричный. Автобус точно едет вправо или влево с ненулевой скоростью, поэтому ответ "стоит на месте" неправильный.
воскресенье, 10 апреля 2011 г.
Золотая цепь
Путник остановился в гостинице на неделю и договорился с хозяином, что оплатит проживание золотой цепью из семи звеньев, по звену за день. Поскольку оба не доверяли друг другу, было решено, что путник будет отдавать хозяину по одному звену каждый день.
Сколько звеньев цепи нужно разрезать, чтобы, с одной стороны, соблюсти условия договора, а с другой - сделать как можно меньше разрезов?
Сколько звеньев цепи нужно разрезать, чтобы, с одной стороны, соблюсти условия договора, а с другой - сделать как можно меньше разрезов?
четверг, 7 апреля 2011 г.
Получить 6 из 0
Как, используя единственный ноль и применяя к нему математические операции, получить в результате 6?
понедельник, 4 апреля 2011 г.
Средняя зарплата
Три программиста пошли после работы пить пиво. По ходу обсуждения тяжёлой и неказистой жизни они решили посчитать свою среднюю зарплату. К сожалению, они все подписывали NDA и не могут просто назвать свои зарплаты друг другу. Как им поступить, чтобы всё-таки посчитать среднюю зарплату?
У программистов при себе нет никаких бумажек или ручек, поэтому они вынуждены передавать информацию исключительно на словах. Впрочем, они могут говорить что-нибудь одному коллеге так, чтобы не услышал третий.
Ситуация, когда кто-то узнаёт, например, что зарплаты остальных X и Y, но не знает, у кого какая, противоречит правилам.
У программистов при себе нет никаких бумажек или ручек, поэтому они вынуждены передавать информацию исключительно на словах. Впрочем, они могут говорить что-нибудь одному коллеге так, чтобы не услышал третий.
Ситуация, когда кто-то узнаёт, например, что зарплаты остальных X и Y, но не знает, у кого какая, противоречит правилам.
воскресенье, 3 апреля 2011 г.
Список со случайными указателями
У вас есть связный список, в каждом узле которого хранятся две ссылки: обычная ссылка на следующий элемент и дополнительная ссылка на произвольный элемент того же списка. Пример такого списка показан на рисунке:
Здесь красным цветом выделены ссылки на следующий элемент, а синим - на случайный. Заметьте, что никаких ограничений на случайные ссылки нет: они могут указывать на тот же элемент, указывать назад, образовывать циклы и т.п.
Требуется скопировать такой список за линейное время и константную память. Если потребуется, Вы можете временно изменить оригинальный список, но потом Вам нужно будет вернуть его в исходное состояние.
Требуется скопировать такой список за линейное время и константную память. Если потребуется, Вы можете временно изменить оригинальный список, но потом Вам нужно будет вернуть его в исходное состояние.
Два яйца и небоскрёб
Ещё одна довольно известная задача, которую включают почти во все сборники задач с собеседований в Гугл.
У вас есть доступ в 100-этажный небоскрёб и 2 идентичных яйца неизвестной птицы. Никаких данных о прочности скорлупы нет: яйцо может разбиться, упав с первого этажа, а может остаться целым, упав с сотого.
Ваша задача - определить, начиная с какого этажа яйца начинают разбиваться, за минимальное (в худшем случае) число бросков. В ходе эксперимента Вы можете разбить оба яйца, но запасных яиц нет.
У вас есть доступ в 100-этажный небоскрёб и 2 идентичных яйца неизвестной птицы. Никаких данных о прочности скорлупы нет: яйцо может разбиться, упав с первого этажа, а может остаться целым, упав с сотого.
Ваша задача - определить, начиная с какого этажа яйца начинают разбиваться, за минимальное (в худшем случае) число бросков. В ходе эксперимента Вы можете разбить оба яйца, но запасных яиц нет.
Подписаться на:
Сообщения (Atom)