Я иногда провожу интервью кандидатов на работу. Помимо определения профессиональных навыков кандитата в мои обязанности входит «погонять человека по задачкам».
Я бы хотел поделиться набором задач, которые были собраны мною по интервью, знакомым, интернет ресурсам, просторам собственного воображения. Хотелось бы услышать мнение о сложности/адекватности этих задач и, возможно, пополнить свою коллекцию.
1.2 Дан массив из целых чисел. Известно, что одно из чисел встречается дважды. Найти это число за O(n)
1.3 Дана строка, например thisisastringwithoutdelimiters. Каким образом перебрать все возможные разбиения её на слова?
1.4 rnd() возвращает случайное целое число от 1 до 5. Реализовать rnd2() которая пользуясь лишь rnd() возвращает случайное целое число от 1 до 7
1.5 Перемешать отсортированный массив (т.е. расположить его элементы в случайном порядке). Нужны ли дополнительные структуры? Какова сложность?
Как это сделать наиболее оптимальным способом?
2.2 Дана квадратная матрица. Вывести все элементы матрицы по спирали.Например, для матрицы
2.3 Из цельного куба произвольно вырезали маленький куб, полностью расположенный внутри большого. Требуется найти плоскость, которая разрежет получившуюся фигуру (большой куб с полостью внутри) на две фигуры одинакового объема.
2.4 Придумать структуру данных, которая работает наподобие FIFO стека, операции push() и pop() выполняются за O(1). Также определена операция max(), возвращающая наибольший элемент в структуре и выполняющаяся я за O(1).
2.5 Используя неограниченное количество стеков (FILO) реализовать очередь (FIFO)? А наоборот (из очередей сделать стек)?
Перед Вами житель острова. Задайте ему один вопрос и в зависимости от ответа определите рыцарь он или лжец.
3.2 Имеется словарь всех слов. Требуется придумать структуру данных для словаря и алгоритм который будет за наименьшее время (желательно O(1)) определять какой анаграммой является данная последовательность букв (например, «ннарагамам» есть анаграмма слова «анаграмма»)
3.3 Имеется предложение на английском языке и список плохих слов. Требуется заменить все плохие слова в предложении звездочками? А как заменять только корень слова (например «This ****ing shop-assistant is such an ***hole!»)?
3.4 У вас есть база знаменитых последовательностей (например, числа биномиальные коэффициенты, числа Каталана, потерянные «4 8 15 16 23 42» и т. п.); Каким образом организовать хранение этих последовательностей и какой алгоритм использовать, чтобы по заданной пользователем последовательности определять, что это за числа. Например, если пользователь вводит 34, 55, 89, 144, то алгоритм должен сказать, что это числа Фибоначчи.
3.5 Необходимо создать планировщик задач, удовлетворяющий следующим условиям:
(а) любая задача должна исполняться с заданной периодичностью (целое число секунд),
(б) новая задача может быть добавлена в любой момент,
(в) планировщик должен быть реализован в одной нити,
(г) планировщик просыпается каждую секунду,
(д) время задачи исполняются мгновенно.
Таким образом если добавилось 2 задачи, А и Б, А имеет периодичность 2 секунды, а Б — 3, на второй секунде планировщик выполнит А, на третьей — Б, на четвёртой — А, на пятой — ничего, на шестой А и Б, и т.д.
Сколько памяти нужно? Как оптимизировать время поиска задачи, которую надо выполнить в текущую секунду? Как можно воспользоваться фактом, что шаг планировщика — 1 секунда?
А ещё мне очень нравится статья Джоела Спольски про проведение интервью.
Я бы хотел поделиться набором задач, которые были собраны мною по интервью, знакомым, интернет ресурсам, просторам собственного воображения. Хотелось бы услышать мнение о сложности/адекватности этих задач и, возможно, пополнить свою коллекцию.
Группа 1: Устные задачки — проверка на дурака
1.1 Перевернуть предложение (было «Мама мыла раму», стало «раму мыла Мама»); сделать это без использования дополнительной памяти1.2 Дан массив из целых чисел. Известно, что одно из чисел встречается дважды. Найти это число за O(n)
1.3 Дана строка, например thisisastringwithoutdelimiters. Каким образом перебрать все возможные разбиения её на слова?
1.4 rnd() возвращает случайное целое число от 1 до 5. Реализовать rnd2() которая пользуясь лишь rnd() возвращает случайное целое число от 1 до 7
1.5 Перемешать отсортированный массив (т.е. расположить его элементы в случайном порядке). Нужны ли дополнительные структуры? Какова сложность?
Группа 2: Написать или нарисовать примерное решение на доске
2.1 Вывести центральные коэффициенты треугольника Паскаля. Например, для треугольника
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
это будет: 1, 1, 2, 3, 6, 10, 20. Как это сделать наиболее оптимальным способом?
2.2 Дана квадратная матрица. Вывести все элементы матрицы по спирали.Например, для матрицы
1 2 3
4 5 6
7 8 9
это будет 1, 2, 3, 6, 9, 8, 7, 4, 52.3 Из цельного куба произвольно вырезали маленький куб, полностью расположенный внутри большого. Требуется найти плоскость, которая разрежет получившуюся фигуру (большой куб с полостью внутри) на две фигуры одинакового объема.
2.4 Придумать структуру данных, которая работает наподобие FIFO стека, операции push() и pop() выполняются за O(1). Также определена операция max(), возвращающая наибольший элемент в структуре и выполняющаяся я за O(1).
2.5 Используя неограниченное количество стеков (FILO) реализовать очередь (FIFO)? А наоборот (из очередей сделать стек)?
Группа 3: Подумать вслух
3.1 На некотором острове живут лжецы и рыцари. Лжецы всегда говорят неправду, рыцари — правду. И те и другие умеют отвечать на бинарные вопросы словми «тик» и «так»; что обозначает да, что — нет неизвестно (может, «тик» — это да, а «так» — нет, а может и наоборот).Перед Вами житель острова. Задайте ему один вопрос и в зависимости от ответа определите рыцарь он или лжец.
3.2 Имеется словарь всех слов. Требуется придумать структуру данных для словаря и алгоритм который будет за наименьшее время (желательно O(1)) определять какой анаграммой является данная последовательность букв (например, «ннарагамам» есть анаграмма слова «анаграмма»)
3.3 Имеется предложение на английском языке и список плохих слов. Требуется заменить все плохие слова в предложении звездочками? А как заменять только корень слова (например «This ****ing shop-assistant is such an ***hole!»)?
3.4 У вас есть база знаменитых последовательностей (например, числа биномиальные коэффициенты, числа Каталана, потерянные «4 8 15 16 23 42» и т. п.); Каким образом организовать хранение этих последовательностей и какой алгоритм использовать, чтобы по заданной пользователем последовательности определять, что это за числа. Например, если пользователь вводит 34, 55, 89, 144, то алгоритм должен сказать, что это числа Фибоначчи.
3.5 Необходимо создать планировщик задач, удовлетворяющий следующим условиям:
(а) любая задача должна исполняться с заданной периодичностью (целое число секунд),
(б) новая задача может быть добавлена в любой момент,
(в) планировщик должен быть реализован в одной нити,
(г) планировщик просыпается каждую секунду,
(д) время задачи исполняются мгновенно.
Таким образом если добавилось 2 задачи, А и Б, А имеет периодичность 2 секунды, а Б — 3, на второй секунде планировщик выполнит А, на третьей — Б, на четвёртой — А, на пятой — ничего, на шестой А и Б, и т.д.
Сколько памяти нужно? Как оптимизировать время поиска задачи, которую надо выполнить в текущую секунду? Как можно воспользоваться фактом, что шаг планировщика — 1 секунда?
P. S.
Я осознаю, что скорость/качество решения задачек не полностью характеризуют кандидата.А ещё мне очень нравится статья Джоела Спольски про проведение интервью.
