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

В этом выпуске рассмотрим классическую задачу, известную под названием «Золотая гора». На CheckiO её реализовали в этой задаче. Представьте себе треугольник, составленный из чисел. Одно число расположено в вершине. Ниже размещено два…

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

Задача про вероятность попадания баскетбольного мяча в корзину

Вы должны выбрать одну из двух ставок. При первом варианте вы должны забросить баскетбольный мяч в корзину. Если попадёте, то получите 50 тыс. рублей. Во втором варианте вам надо попасть…

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

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

Как обнаружить дублирующиеся URL-адреса

Сложность задачи заключается в том, что адресов дано 10 миллиардов. Сколько пространства понадобится для хранения 10 миллиардов URL-адресов? Если в среднем URL-адрес занимает 100 символов, а каждый символ представляется 4 байтами…

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

У скольких целых чисел, лежащих в диапазоне от 1 до 1000, есть цифра 3?

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

Вакансии

Алгоритм, реализующий стек со стандартными функциями push и pop и дополнительной функцией min за O(1)

Итак, оценка времени работы функция push, pop и min – O(1). Экстремумы изменяются не часто. Фактически минимум может поменяться только при добавлении нового элемента. Одно из решений – сравнивать добавляемые элементы…

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

В темной комнате вам вручают колоду карт, в которой N карт лежат рубашкой вверх, а остальные — вниз. Вы не можете видеть карты. Как вы разделите колоду на две стопки, чтобы в каждой из них было одинаковое число карт, лежащих рубашкой вверх?

Эта головоломка в своё время была популярна в JP Morgan Chase. Понятное дело, оказавшись в темноте, вы просто достанете сотовый телефон и воспользуетесь экраном как фонариком. Однако эта задачка появилась…

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

Метод, определяющий, является ли одна строка перестановкой другой

Для начала нужно уточнить детали. Следует разобраться, является ли сравнение анаграмм чувствительным к регистру. То есть является ли строка «God» анаграммой «dog»? Также нужно выяснить, учитываются ли пробелы. Предположим, что для…

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

Дан кусок сыра в форме куба и нож. Сколько разрезов потребуется сделать, чтобы разделить этот кусок на 27 небольших кубиков?

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

Вывод последних K строк входного файла на C++

Можно действовать прямо — подсчитать количество строк (N) и вывести строки с N-K до N. Для этого понадобится дважды прочитать файл, что очень неэффективно. Давайте найдем решение, которое потребует прочитать…

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

Существует несколько общих способов предотвратить мертвые блокировки. Один из самых популярных — обязать процесс явно объявлять, в какой блокировке он нуждается. Тогда мы можем проверить, будет ли созданная блокировка мертвой…

Сопоставление хэш-таблицы и map в С++

Сопоставьте хэш-таблицу и mар из стандартной библиотеки шаблонов (STL). Как организована хэш-таблица? Какая структура данных будет оптимальной для небольших объемов данных? В хэш-таблицу значение попадает при вызове хэш-функции с ключом.

В книге N страниц, пронумерованных как обычно от 1 до N. Если сложить количество цифр, содержащихся в каждом номере страницы, будет 1095. Сколько страниц в книге?

У каждого числа, обозначающего страницу, имеется цифра на месте единиц. При N страниц имеется N цифр, стоящих на месте единиц. У всех, за исключением первых 9 страниц, числа являются как…

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

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

На первый взгляд кажется, что задача сложная, но фактически она очень проста. Чтобы решить ее, задайте себе вопрос: “Как узнать, какие биты в двух числах различаются?”. Ответ прост – с…

Алгоритм для поиска в односвязном списке k-го элемента с конца

Данный алгоритм можно реализовать рекурсивным и нерекурсивным способом. Рекурсивные решения обычно более понятны, но менее оптимальны. Например, рекурсивная реализация этой задачи почти в два раза короче нерекурсивной, но занимает O(n)…

Напишите функцию, меняющую местами значения переменных, не используя временные переменные

Это классическая задача, которую любят предлагать на собеседованиях, и она достаточно проста. Пусть a0 — это исходное значение a, а b0 — исходное значение b. Обозначим diff разницу а0 –…

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

Почему деструктор базового класса должен объявляться виртуальным?

Давайте разберемся, зачем нужны виртуальные методы. Рассмотрим следующий код: class Foo { public: void f(); }; class Bar : public Foo { public: void f(); } Foo *p = new…

Стакан воды на вращающемся диске

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

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

Алгоритм, выводящий все корректные комбинации пар круглых скобок

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

Алгоритм, который генерирует целое число, отсутствующее в файле

Дан входной файл, содержащий четыре миллиарда целых 32-битных чисел. Предложите алгоритм, генерирующий число, отсутствующее в файле. Имеется 1 Гбайт памяти для этой задачи. Дополнительно: а что если у вас всего 10 Мбайт?

Логическая задача на расставление костей домино на шахматной доске

Дана шахматная доска размером 8×8, из которой были вырезаны два противоположных по диагонали угла, и 31 кость домино; каждая кость домино может закрыть два квадратика на поле. Можно ли вымостить…

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

Логическая задача на взвешивание

Дано 20 баночек с таблетками. В 19 баночках лежат таблетки весом 1 г, а в одной – весом 1.1 г. Даны весы, показывающие точный вес. Как за одно взвешивание найти…

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

Безопасность потоков в С++

Допустим, вы пишете конвейер, в котором 2 потока, используя общий буфер, обрабатывают данные. Поток-producer эти данные создает, а поток-consumer их обрабатывает (Producer–consumer problem). Следующий код представляет собой самую простую модель:…

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

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

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

Работа виртуальных функций в C++

Виртуальная функция определяется vtable (виртуальной таблицей). Если какая-либо функция класса объявлена как виртуальная, создастся vtable, которая хранит адреса виртуальных функций этого класса. Для всех таких классов компилятор добавляет скрытую переменную…

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

Где вы будете плыть быстрее — в воде или сиропе?

Исаак Ньютон и Христиан Гюйгенс обсуждали этот вопрос в 1600-е годы, но так и не дали на него исчерпывающий ответ. Три столетия спустя два химика из Университета Миннесоты, Брайан Геттельфингер…

Напишите метод, который будет подсчитывать количество цифр «2», используемых в записи чисел от 0 до n (включительно)

Как всегда, сначала мы попробуем решить задачу «в лоб».

Опишите алгоритм для нахождения миллиона наименьших чисел в наборе из миллиарда чисел. Память компьютера позволяет хранить весь миллиард чисел

Существует много способов решить эту задачу. Мы остановимся только на трех — сортировка, минимум кучи и ранжирование.

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

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

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

Как далеко вы сможете доставить груз на N грузовиках

У вас есть парк из 50 грузовиков. Каждый из них полностью заправлен и может проехать 100 км. Как далеко с их помощью вы можете доставить определенный груз? Что будет, если…

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

Напишите функцию суммирования двух целых чисел без использования «+» и других арифметических операторов

Первое, что приходит в голову, — обработка битов. Почему? У нас нет выбора — нельзя использовать оператор «+». Так что будем суммировать числа так, как это делают компьютеры!

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

Вероятность встретить машину на пустынном шоссе

На пустынном шоссе вероятность появления автомобиля за 30-минутный период составляет 0.95. Какова вероятность его появления за 10 минут? Это вопрос труден только потому, что та информация, которую вы получили, не…

В чем разница между потоком и процессом?

Процессы и потоки связаны друг с другом, но при этом имеют существенные различия. Процесс — экземпляр программы во время выполнения, независимый объект, которому выделены системные ресурсы (например, процессорное время и…

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