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

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

1. Алгоритмическая задача про острова
2. Поиск знаменитости
3. Миллион наименьших чисел
4. Сумма чисел
5. Тёплые дни: задача на стек

Алгоритмическая задача про острова

Для двумерного массива 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, мы получаем два варианта ответа:

1. Знает — человек A не знаменитость.
2. Не знает — человек 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];
}
		

Миллион наименьших чисел

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

Решение

Есть несколько способов решить поставленную задачу:

1. Сортировка
2. Минимум кучи
3. Ранжирование

Каждый из этих способов мы разобрали в нашей статье по нахождению миллиона наименьших чисел.

Сумма чисел

Такая задача нередко встречается на интервью, и в стрессовой ситуации программист действительно может сразу не сориентироваться.

Дан отсортированный массив чисел, включая отрицательные, и некое число 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;
    }
}
		

Понравились задачки? Держите ещё десять непростых задач на логику, которые часто задают программистам на собеседованиях.