Задачи на собеседованиях для программистов характеризуются видимой сложностью, но если спокойно разобраться, всё решается довольно просто. Мы подготовили несколько заковыристых задач и решения к ним.
- Алгоритмическая задача про острова
- Поиск знаменитости
- Миллион наименьших чисел
- Сумма чисел
- Тёплые дни: задача на стек
Алгоритмическая задача про острова
Для двумерного массива M x N, состоящего из единиц, которые обозначают сушу, и нулей, обозначающих воду, верните количество островов.
Остров окружён водой и образован соединением соседних земель по горизонтали и вертикали. Вы можете предположить, что все четыре края матрицы окружены водой.
Примечание Если островов нет, возвращаем 0.
Решение
Для начала нам нужно найти в матрице хотя бы одну единицу: начинаем построчный обход с нулевого индекса [0,0]. Когда мы находим единицу, помечаем её, как просмотренную, и также просматриваем соседние клетки по направлениям вправо, вниз, влево, вверх.
Если предыдущая ячейка была сушей, а следующая оказалась водой, мы возвращаемся к суше и просматриваем ячейки по перечисленным направлением в том же порядке.
Код
class Islands {
//Метод принимает 2-хмерный массив символов
public int howMuchlands(char[][] matrix) {
//Проверяем величину массива
if(matrix == null || matrix.length == 0)
return 0;
//Переменная, хранящая кол-во островов
int numIslands = 0;
//Начинаем обход с верхнего левого угла:
//перебор строк
for(int i = 0; i < matrix.length; i++){
//перебор столбцов
for(int j = 0; j < matrix[i].length; j++){
//Если 1,
if(matrix[i][j] == '1'){
//увеличиваем кол-во островов
numIslands++;
//и проходим по периметру
markIsland(matrix, i, j);
}
}
}
return numIslands;
}
//Метод обхода острова: принимает матрицу и координаты
private void markIsland(char[][] matrix, int i, int j){
//Условие выхода за край матрицы
if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[i].length || matrix[i][j] == '0')
return;
//Если не вышли за границу, помечаем ячейку как 0
matrix[i][j] = '0';
//Осматриваемся:
markIsland(matrix, i, j + 1); //вправо
markIsland(matrix, i + 1, j); //вниз
markIsland(matrix, i, j - 1); //влево
markIsland(matrix, i - 1, j); //вверх
}
}Поиск знаменитости
А эта задача с собеседований встречалась программистам при трудоустройстве в Amazon.
Дана группа людей из K человек, и эти люди могут знать друг друга, необязательно взаимно. Среди них есть знаменитость. Знаменитость — это человек, который не знает никого в компании, зато каждый из компании знает его. Изначально мы не владеем информацией о том, кто кого знает, но мы можем спросить у каждого участника, знает ли он других людей из группы. Нужно определить знаменитость, используя минимальное количество вопросов.
Решение
Для начала определимся с тем, что знаменитость всего одна. Чтобы понять следующий алгоритм решения, давайте посмотрим на двух людей из группы. Обозначим их как A и B.
Когда мы спрашиваем у A, знает ли он B, мы получаем два варианта ответа:
- Знает — человек A не знаменитость.
- Не знает — человек B не знаменитость.
Так, задав всего один вопрос, мы избавляемся от одного кандидата на статус знаменитости. Именно этот алгоритм мы и используем в программе: опрашивается пара человек, после чего один из них вычёркивается из списка, и так пока не останется один кандидат.
Но наличие одного кандидата ещё не означает, что он знаменитость, ведь её может не быть вовсе. Поэтому последние два действия состоят в том, чтобы спросить у остальных, знают ли они кандидата, а у кандидата — знает ли он всех остальных.
Код
//Функция, которая принимает массив и возвращает один элемент либо null
Person findCelebrity(Person[] persons) {
//Используем метод двух указателей: начало массива и конец массива
int l = 0, r = persons.length - 1;
//Двигаемся от начала и конца к середине массива
while (l != r){
if(persons[l].knows(persons[r])) {
l++;
} else{
r--;
}
}
//Когда остаётся один кандидат, проходим по всему массиву
for(int i = 0; i < persons.lenth; i++) {
//Проверяем, что кандидат не знаменитость с такими условиями
if(i != l && (!persons[i].knows(persons[l]) || persons[l].knows(persons[i]))) {
return null;
}
}
//Если кандидат прошёл проверки, возвращаем его как ответ
return persons[l];
}Миллион наименьших чисел
Опишите алгоритм для нахождения миллиона наименьших чисел в наборе из миллиарда чисел. Память компьютера позволяет хранить весь миллиард чисел.
Решение
Есть несколько способов решить поставленную задачу:
- Сортировка
- Минимум кучи
- Ранжирование
Каждый из этих способов мы разобрали в нашей статье по нахождению миллиона наименьших чисел.
Сумма чисел
Такая задача нередко встречается на интервью, и в стрессовой ситуации программист действительно может сразу не сориентироваться.
Дан отсортированный массив чисел, включая отрицательные, и некое число K. Нужно найти два числа из массива, которые в сумме дадут число K. Если таких чисел нет, в результате возвращаем пустой массив. Если комбинаций чисел, дающих нужную сумму, несколько, возвращаем любую из них.
Есть несколько вариантов решения задачи:
- перебор всех пар — временная сложность алгоритма O(n²);
- HashSet — O(n);
- бинарный поиск — O(n log n);
- два указателя — O(n).
Давайте решим задачу с помощью HashSet.
Примечание Хоть метод HashSet и работает за один проход по массиву, он тратит дополнительную память, так как в худшем случае мы перенесём все элементы из входного массива в наш сет.
Решение
Создаём пустой сет и смотрим первый элемент массива. Добавляем его в сет. Далее смотрим второй элемент и то, даёт ли он в сумме с вынесенным в сет первым элементом K. Если нет, просто переносим его в сет. Так мы продолжаем до тех пор, пока не найдём число, которое в сумме с другим числом из сета даст число K. Выводим массив из этих двух элементов в качестве ответа.
Код
//Функция принимает массив чисел, число k и возвращает массив чисел
int[] sumK(int[] numbers, int k) {
//Создаём пустой сет
Set numSet = new HashSet<>();
//Идём по массиву слева направо
for(int i = 0; i < numbers.length; i++) {
//Определяем, каким должно быть второе число из пары
int secondNumber = k - numbers[i];
//Проверяем, встречалось ли нам это число ранее
if(numSet.contains(secondNumber)) {
//Возвращаем новый массив
return new int[]{secondNumber, numbers[i]}
}
//Если не встречалось, просто добавляем число в наш сет
numSet.add(numbers[i]);
}
//Если ответа нет, возвращаем пустой массив
return new int[0];
}Тёплые дни: задача на стек
Дан массив чисел, состоящий из N элементов. Эти числа обозначают температуру в конкретный день. Для каждого дня нужно найти количество суток до наступления более тёплого дня.
Вот пример того, как это можно изобразить:
//Температура:
17 16 19 15 13 18 20
//Количество суток до более тёплого дня:
2 1 4 2 1 1 0Решение
Используем два цикла. В первом мы будем идти по всем дням, для которых хотим определить ответ, а во втором пробегать направо до тех пор, пока не наткнёмся на более тёплый день.
Код
class WarmDays {
//Метод, принимающий массив температур
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
//Массив ответов по длине равен массиву температур
int[] answer = new int[n];
//Идём по дням, для которых ищем ответ
for (int day = 0; day < n; day++) {
//Идём по всем дням после нашего
for (int futureDay = day + 1; futureDay < n; futureDay++) {
//Если температура следующего дня больше текущего,
if (temperatures[futureDay] > temperatures[day]) {
//проставляем ответ
answer[day] = futureDay - day;
break;
}
}
}
return answer;
}
}Понравились задачки? Держите ещё десять непростых задач на логику, которые часто задают программистам на собеседованиях.
