Задачи на собеседованиях для программистов характеризуются видимой сложностью, но если спокойно разобраться, всё решается довольно просто. Мы подготовили несколько заковыристых задач и решения к ним.
Алгоритмическая задача про острова
Для двумерного массива 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];
}
Это всего лишь две задачи. В нашем материале на сайте их 5. Переходите по ссылке и попытайтесь решить другие задачки :)
Понравилась статья? Держите ещё десять непростых задач на логику, которые часто задают программистам на собеседованиях.