В вашем распоряжении 10 тысяч серверов в дата-центре с возможностью удалённого управления и один день, чтобы получить миллион долларов. Что вы для этого сделаете?

Ответ можно давать в двух направлениях.

Обложка поста

Задача про блендер

«Вас уменьшили до размеров 5-центовой монеты и бросили в блендер. Ваш вес уменьшился так, что плотность вашего тела осталась прежней. Лезвия начнут вращаться через 60 секунд. Ваши действия?»…

Обложка поста

События и курсы

Задачка на основы криптографии с подробным разбором

Как удостовериться, что у друга есть ваш номер телефона так, чтобы никто об этом не узнал, причём нельзя спросить его напрямую? Поясним условия подробнее. Например, вы хотите удостовериться, что у…

Обложка поста

Задача про шарик с гелием в машине

Вы находитесь в автомобиле, где к полу веревочкой привязан шар, наполненный гелием. Окна закрыты. Вы нажимаете на педаль газа. Что произойдет с шаром: переместится он вперед, назад или останется в…

Обложка поста

Вакансии

Реализуйте метод сжатия строки на основе счетчика повторяющихся символов

Например, строка aabcccccaaa должна превратиться в а2b1с5аЗ. Если «сжатая» строка оказывается длиннее исходной, метод должен вернуть исходную строку.

Обложка поста

Подсчёт количества путей робота на сетке

Представьте себе робота, находящегося в левом верхнем углу сетки с координатами (X, Y). Робот может перемещаться в двух направлениях: вправо и вниз. Сколько существует маршрутов, проходящих от точки (0, 0)…

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

Первое, что приходит в голову, — выбрать случайные элементы из массива и поместить их в новый массив. Но что если мы выберем один и тот же элемент дважды? В идеале…

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

Если бы мы работали с массивом, то было бы много сложностей, связанных со смещением элементов. Со связным списком задача намного проще. Вместо того чтобы смещать и менять местами элементы, мы…

Обложка поста

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

Как вы можете получить случайное число в диапазоне от 1 до 7, используя игральную кость с пятью гранями? Иначе говоря, в вашем распоряжении устройство, которое генерирует случайное целое число от 1…

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

Вам дан большой текстовый файл, в котором содержатся слова. Необходимо написать код, который позволит найти минимальное расстояние между любыми двумя словами. Достаточно ли будет O(n) времени? Сколько памяти понадобится для…

Обложка поста

У вас есть неограниченное количество монет достоинством 25, 10, 5 и 1 цент. Напишите код, определяющий количество способов представления n центов

Это рекурсивная задача, поэтому давайте разберемся, как рассчитать makeChange(n), основываясь на предыдущих решениях (подзадачах). Пусть n = 100. Мы хотим вычислить количество способов представления 100 центов. Нам известно, что для…

Опишите, как можно использовать один одномерный массив для реализации трех стеков

Подобно многим задачам, все зависит от того, как мы собираемся поддерживать эти стеки. Если нам нужно выделить определенное пространство для каждого стека, можно так и поступить. Но в этом случае…

Обложка поста

Как рассадить необщительных посетителей в баре так, чтобы клиентов было как можно больше?

В этот бар ходят необщительные посетители. Вдоль барной стойки расположены 25 мест. Всякий раз, когда входит новый посетитель, он обязательно садится на самое дальнее, насколько это возможно, место от остальных…

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

Эту задачу также можно решить двумя способами: простым и сложным. Давайте рассмотрим оба решения. «Простое» решение: O(N4) Мы знаем, что длина стороны самого большого квадрата равна N и существует только…

Обложка поста

В каком случае добираясь до машины, вы меньше промокнете: быстро пробежав или пройдя путь спокойно?

Идет дождь, а вам надо добраться до вашей машины, которая стоит в самом дальнем конце парковки. Побежите ли вы к ней или нет, если ваша цель — как можно меньше…

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

Одно из возможных решений — использовать две кучи разных приоритетов: максимальная куча (maxHeap) для значений выше среднего и минимальная куча (minHeap) для значений ниже среднего. Это позволит разделить элементы примерно…

Найдите самую большую сумму непрерывной последовательности из массива целых чисел, как положительных, так и отрицательных

Это довольно сложная, но очень популярная задача. Давайте решим ее на примере массива: 2 3 -8 -1 2 4 -2 3 Если рассматривать массив как содержащий чередующиеся последовательности положительных и…

Обложка поста

Сколько нулей в конце факториала 100?

Факториал одной сотни записывается как 100! Это произведение всех натуральных чисел до ста включительно. Иногда запись факториала имеет такой вид: 100 х 99 х 98 х 97 х … х…

Обложка поста

По результатам исследования известно, что 70% людей любят кофе и 80% предпочитают чай. Каковы верхние и нижние границы доли людей, которые одновременно любят кофе и чай?

Не все любители чая положительно относятся к кофе; не все любители котов терпят собак, и не все фанаты одной команды одновременно являются болельщиками другой. Нарисуйте диаграмму Венна на доске или…

У вас есть 25 лошадей. Сколько забегов вам нужно устроить, чтобы определить трех самых быстрых из них?

Вы не можете пользоваться секундомером. В каждом заезде могут участвовать только пять лошадей. Вы можете начать свой ответ с уточнения: спросите интервьюера, следует ли считать «самой быстрой лошадью» ту, которая…

Обложка поста
Обложка поста

Отыщите минимальное число монет, позволяющее дать любую сдачу

Есть два способа интерпретации этого вопроса. Они приводят к разным ответам, и поэтому вам лучше спросить интервьюера, что он имеет в виду (или подготовить оба варианта ответов). Одна интерпретация заключается…

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

При правильном толковании термина «слияние» две компании отказываются от своей прежней индивидуальности и сливаются в новое образование, имеющее новый бренд. Так, фармацевтические гиганты Glaхо Wеllсоmе и SmithКlіnе Веесham в 2000…

Обложка поста

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

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

Как избежать зацикливания при разработке поискового робота

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

Обложка поста

Напишите метод, тасующий карточную колоду

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

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

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

Обложка поста
Обложка поста

Сколько дней потребуется, чтобы все голубоглазые уехали с острова?

На острове существует правило — голубоглазые люди не могут там находиться. Самолет улетает с острова каждый вечер в 20:00. Все жители собираются за круглым столом ежедневно, каждый человек может видеть…

Реализуйте алгоритм для однонаправленного списка с петлёй, возвращающий начальный узел петли

Эта задача является разновидностью классической задачи, задаваемой на собеседованиях, – определить, содержит ли связный список петлю. Давайте используем подход «Сопоставление с образцом». Часть 1. Определяем, есть ли в связном списке…

Алгоритм, демонстрирующий круг знакомств человека для социальных сетей

Предположим, что нам требуется разработать алгоритм, демонстрирующий связи человека с человеком, но при условии, что база очень большая. Например, для использования в Facebook или LinkedIn. Хороший способ решить эту задачу…

Обложка поста

Разработка алгоритма, обнаруживающего в массиве все пары целых чисел, сумма которых равна заданному значению.

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

Обложка поста

Алгоритм, реализующий следующее условие: если элемент матрицы в точке NxM равен 0, то весь столбец и вся строка обнуляются.

На первый взгляд задача очень проста – просто пройтись по матрице и для каждого нулевого элемента обнулить соответствующие строку и столбец. Но у такого решения есть один большой недостаток: на…

Проверка анаграмм

На этот раз будем изучать задачу «Проверка анаграмм» («Verify Anagrams»). Мы уже писали об этой задаче ранее, но теперь расскажем о ней немного другим способом. Анаграмма — это игра со…