Аватарка пользователя Марина Александровна
Марина Александровна

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

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

25643

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

  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;
    }
}
		

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

25643