В нашем Королевстве могущественный добрый волшебник Гэндальф объявил конкурс, чтобы найти творческих персонажей. По всем соседним королевствам разослали гонцов, чтобы они известили о предстоящем конкурсе, который состоится в Братстве кольца. Эльфы, хоббиты и гоблины начали свой трудный и извилистый путь по направлению к вершине Огненной горы.
Преодолев препятствия в подземелье Мории, древнем царстве гномов, путники созвали совет и образовалось Братство Кольца. После долгих блужданий путники стремились выйти на свет. Вслед за этим последовала битва с орками, после которой хрипло проревел рог, и путники вырвались из подземелья. По пути на Огненную Гору путники побывали в чудесном эльфийском городе Лотроиэн, обещавшему сердцу мир и покой. Отряду удалось бежать, и они направились на Огненную Гору, где состоялось собрание Братства Кольца, на которое съехались представители разных королевств. Гоблины спросили: «Как нам найти креативных людей?» Гэндальф предложил выполнить им определенные задания, рекомендованные на собеседованиях в компаниях Google, Amazon и Apple. В награду Гэндальф обещал присвоить им важные титулы в Королевстве, которые будут иметь определенные бонусы. Гэндальф пояснил, что данная серия задач предназначена преимущественно для программистов. Представляю Вашему вниманию некоторые из задачек:
Задача №1
Классическая задачка с собеседований в Google. На доске записаны числа, вам нужно ответить на вопрос: какое число идёт дальше? И
Задача №2
Задача, которая была популярна в своё время на собеседованиях в Amazon. Мы русифицировали её, но смысл остался тот же. Вам нужно продолжить последовательность.
Задача №3
Одна из самых известных задач Интернета, будоражащая многие светлые умы человечества.
Самолет стоит на взлетной полосе с подвижным покрытием типа транспортера. Покрытие может двигаться против направления взлета самолета, то есть ему навстречу. Транспортер автоматически регулирует свою скорость таким образом, чтобы самолет оставался неподвижным. Вопрос: сможет ли самолет в таких условиях взлететь?
Задача №4
Представьте себе треугольник, составленный из чисел. Одно число расположено в вершине. Ниже размещено два числа, затем три, и так до нижней грани. Вы начинаете на вершине, и нужно спуститься к основанию треугольника. За каждый ход вы можете спуститься на один уровень и выбрать между двумя числами под текущей позицией. По ходу движения вы «собираете» и суммируете числа, которые проходите. Ваша цель — найти максимальную сумму, которую можно получить из различных маршрутов.
Какой алгоритм вы предложите? Какая у него будет сложность и можно ли предложить лучший вариант?
Задача №5
У вас есть аналоговые часы с секундной стрелкой. Сколько раз в день все три стрелки часов накладываются друг на друга?
Задача №6
Вы играете в футбол на пустынном острове и хотите подбросить монетку, чтобы решить, какой команде достанется мяч. Единственная монета, что у вас есть, является гнутой, и поэтому вносит явные искажения в результат при подбрасывании. Как вы тем не менее можете использовать такую монету, чтобы принять справедливое решение?
Задача №7
На пустынном шоссе вероятность появления автомобиля за 30-минутный период составляет 0.95. Какова вероятность его появления за 10 минут?
Задача № 8
У вас есть парк из 50 грузовиков. Каждый из них полностью заправлен и может проехать 100 км. Как далеко с их помощью вы можете доставить определенный груз? Что будет, если в вашем распоряжении N грузовиков?
Не все понимают сразу о чем речь: территориально это место, где нет никаких заправочных станций. Единственное место, где можно здесь найти горючее – это топливные баки грузовиков. Пересесть из грузовика в гибридный легковой автомобиль Prius нельзя. Бросить грузовик без топлива, где бы это ни случилось, и без водителя – в порядке вещей. И единственное, что здесь важно, – доставить как можно дальше ценный груз.
Задача № 9
Вы поставили стакан воды на диск проигрывателя виниловых пластинок и медленно увеличиваете скорость вращения. Что произойдет раньше: стакан сползет в сторону, стакан опрокинется, вода расплескается?
Этот вопрос задавали ранее на собеседованиях в Apple. При ответе рассмотрите возможные варианты и укажите, от чего зависит ответ, если их несколько.
Задача № 10
В тёмной комнате вам вручают колоду карт, в которой известное количество карт N лежат рубашкой вверх, а остальные — вниз. Вы не можете видеть карты, но можете их переворачивать. Как вы разделите колоду на две стопки, чтобы в каждой из них было одинаковое число карт, лежащих рубашкой вверх?
Эта головоломка в своё время была популярна в JP Morgan Chase. Понятное дело, оказавшись в темноте, вы просто достанете сотовый телефон и воспользуетесь экраном как фонариком. Однако эта задачка появилась до эпохи сотовых телефонов, и её можно решить, даже не видя карт.
Задача № 11
На острове существует правило — голубоглазые люди не могут там находиться. Самолет улетает с острова каждый вечер в 20:00. Все жители собираются за круглым столом ежедневно, каждый человек может видеть цвет глаз других людей, но не знает цвет собственных. Никто не имеет права сказать человеку, какой у него цвет глаз. На острове находится не менее одного голубоглазого человека. Сколько дней потребуется, чтобы все голубоглазые уехали?
Задача № 12
Напишите метод, тасующий карточную колоду. Колода должна быть идеально перемешана т.е. перестановки карт должны быть равновероятными. Вы можете использовать идеальный генератор случайных чисел.
Задача № 13
У вас есть стеклянный кувшин, в котором лежат небольшие шарики, и вы в любое время можете определить их количество. Вы со своим другом играете в следующую игру: каждый из вас по очереди забирает из кувшина 1 или 2 шарика. Игрок, который забирает последний шарик, выигрывает. Какая самая лучшая стратегия в этой игре? Можете ли вы в самом начале предсказать, кто выиграет?
Задача № 14
У вас есть 25 лошадей. Сколько забегов вам нужно устроить, чтобы определить трех самых быстрых из них? Вы не можете пользоваться секундомером. В каждом заезде могут участвовать только пять лошадей.
Задача № 15
Короткая задачка на сообразительность. По результатам исследования известно, что 70% людей любят кофе, в то же время 80% любят чай. Каковы верхние и нижние границы доли людей, которые одновременно любят кофе и чай?
Задача № 16
Предположим, в некоторый бар ходят только необщительные посетители. Вдоль барной стойки расположены 25 мест. Всякий раз, когда входит новый посетитель, он обязательно садится на самое дальнее, насколько это возможно, место от остальных гостей. Ни один не сядет рядом с кем-то другим: если посетитель входит и видит, что «свободных» мест нет, он тут же разворачивается и уходит из бара. Бармену, естественно, хочется, чтобы за стойкой сидело как можно больше клиентов. Если ему разрешено усадить первого посетителя на любое место, куда выгоднее его посадить с точки зрения бармена?
Задача № 17
На одной стороне реки находятся три человека и три льва. Все они должны оказаться на другом берегу реки. Есть лишь одна лодка, в которой могут поместиться лишь два живых существа одновременно (человека или льва). Вы не можете оставлять на том или другом берегу реки больше львов, чем людей, так как в этом случае животные съедят людей, оставшихся в меньшинстве. Как вы переправите всех через реку?