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

Картинка поста

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

Картинка поста

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

Картинка поста

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

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

Картинка поста

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

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

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

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

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

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

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

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

Вызывая p->f(), мы обращаемся к Foo::f(). Это потому, что р — указатель на Foo, a f() — невиртуальная функция. Чтобы...
Читать дальше
Картинка поста

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

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


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

Картинка поста

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

Картинка поста

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

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

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

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

Картинка поста

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

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

Картинка поста

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

Самый распространенный вариант реализации функции max — проверка знака выражения a – b. В этом случае мы не можем использовать оператор сравнения, но можем использовать умножение....
Читать дальше

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

Под отсортированной матрицей будем понимать такую матрицу, строки и столбцы которой отсортированы. Чтобы найти нужный элемент, можно воспользоваться бинарным поиском по каждой строке. Алгоритм потребует O(M log(N)) времени, так как необходимо...
Читать дальше


Ключевое слово volatile информирует компилятор, что значение переменной может меняться извне. Это может произойти под управлением операционной системы, аппаратных средств или другого потока. Поскольку значение может измениться, компилятор каждый раз...
Читать дальше

Что означает Dead beef? Dead beef является формой записи некоторых слов. При отладке компьютерных программ содержание памяти должно отображаться на экране (или, как это было в давние времена, на бумаге)....
Читать дальше

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

При выполнении этого задания нельзя использовать дополнительные структуры данных. Один из очевидных вариантов решения состоит в том, чтобы сравнить каждый символ строки с любым другим символом строки. Это потребует О(n²)...
Читать дальше

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