Разбор задач второго этапа Школы программистов HeadHunter 2017
Второй этап отбора в Школу программистов закончился. Многие из тех, кто поступал в Школу, просили рассказать алгоритмы решения задач, а главное — прислать комбинации, на которых их программа не работает. В этой статье будут описаны решения предлагаемых задач, а в конце статьи вы увидите ссылку на github, где выложен код описанных решений, код программы проверки и тестовые кейсы. Весь код написан на java (хотя решение второй задачи легче писать на питоне). Не буду утверждать, что это единственные правильные решения, существуют и другие, но эти мне нравятся больше всего.
Немного статистики: подали заявку чуть больше 900 человек, первый этап прошли 450 человек, примерно 300 человек выполнили задание второго этапа и 105 человек пришли на собеседование. Поступили в Школу 25 человек. Собеседования длились 6 недель. В отборе школьников принимали участие примерно 15 сотрудников HeadHunter.
Задача 1. Тропический остров
Текст задачи:
Предположим, в один прекрасный день вы оказались на острове прямоугольной формы.
Ландшафт этого острова можно описать с помощью целочисленной матрицы размером MxN, каждый элемент которой задаёт высоту соответствующей области острова над уровнем моря.
К примеру, вот небольшой остров размером 3×3:
4 5 4
3 1 5
5 4 1
В сезон дождей остров полностью заливает водой, и в низинах скапливается вода. Низиной будем считать такую область острова, клетки которой граничат с клетками, большими по высоте. При этом диагональные соседи не учитываются, а уровень моря принимается за 0. В приведённом выше примере на острове есть только одна низина — это клетка со значением 1 в середине острова (она граничит с клетками высотой 3, 5, 5 и 4).
Таким образом, после дождя высота клеток острова изменится и станет следующей:
4 5 4
3 3 5
5 4 1
Мы видим, что в данном примере высота низины изменилась с 1 до 3, после чего вода начала переливаться на соседние клетки, а затем — в море. Общий объём воды, скопившейся на острове, — 2 кубические клетки.
Вот пример посложнее:
5 3 4 5
6 2 1 4
3 1 1 4
8 5 4 3
После дождя карта острова принимает следующую форму:
5 3 4 5
6 3 3 4
3 3 3 4
8 5 4 3
Общий объём скопившейся после дождя воды на таком острове составляет целых 7 кубических клеток!
На вход функции подается двухмерный массив, на выходе ожидается int — значения общего объёма воды, скапливающейся на острове после сезона дождей для каждого из входных примеров.
Ограничения:
Размер острова N и M — целые числа в диапазоне [1, 50]
Высоты на острове могут принимать значения из диапазона [1, 1000].
Наиболее простое решение задачи — «сливать» остров: предполагаем, что остров — куб, заполненный водой, где высота куба — самая высокая точка острова.
Алгоритм работы такой:
- Дополняем все, кроме крайних точек, до максимальной высоты
- Проходим по острову, начиная с краев, и «сливаем» его:
- У каждой точки ищем минимальную высоту ее соседних точек (диагональные не учитываем по условию задачи).
- Если найденное минимальное значение меньше высоты текущей точки, то уменьшаем значение текущей точки до минимального или до первоначальной высоты этой точки.
- Проходим по всем точкам, пока значения не перестанут меняться.
- Далее просто вычисляем скопившуюся воду: поэлементно вычитаем из заполненного острова пустой и складываем получившиеся значения.
Исходный код на java:
public int getWaterVolume(Integer[][] island) {
// Определяем длину и ширину острова
int length = island.length;
int width = island[0].length;
// Инициируем новый осторов и заливаем (кроме краев, остров затоплен водой по самую высокую точку)
Integer[][] floodedIsland = new Integer[length][width];
int max = Arrays.stream(island).flatMap(Arrays::stream).max(Integer::compareTo).get();
for (int row = 0; row < length; row++) {
for (int col = 0; col < width; col++) {
if (row == 0 || row == length - 1 || col == 0 || col == width - 1){
floodedIsland[row][col] = island[row][col];
}else{
floodedIsland[row][col] = max;
}
}
}
// "Сливаем" остров
boolean isChange = true;
while (isChange) {
isChange = false;
for (int row = 1; row < length - 1; row++) {
for (int col = 1; col < width - 1; col++) {
if (floodedIsland[row][col] != island[row][col]) {
int minHeight = getMinHeight(floodedIsland, row, col);
if (floodedIsland[row][col] > minHeight) {
// учитываем высоту точки
if (island[row][col] < minHeight) {
floodedIsland[row][col] = minHeight;
} else {
floodedIsland[row][col] = island[row][col];
}
isChange = true;
}
}
}
}
}
int waterCnt = 0;
for (int row = 1; row < length - 1; row++) {
for (int col = 1; col < width - 1; col++) {
waterCnt += floodedIsland[row][col] - island[row][col];
}
}
return waterCnt;
}
private int getMinHeight(Integer[][] island, int row, int col) {
return Arrays.stream(new int[]{
island[row-1][col],
island[row][col-1],
island[row+1][col],
island[row][col+1]
}).min().getAsInt();
}
Можно, конечно, эту задачу решить и наполнением острова, но это значительно сложнее и дольше (особенно если есть несколько низин). Большинство таких решений работали не во всех ситуациях и долго обрабатывались на больших данных. Хотя несколько человек прислали такие решения, которые работали правильно, но все равно не очень быстро.
Задача 2. Бесконечная последовательность
Текст задачи:
Возьмём бесконечную цифровую последовательность, образованную склеиванием последовательных положительных чисел: S = 123456789101112131415…
Определите первое вхождение заданной последовательности A в бесконечной последовательности S (нумерация начинается с 1).
Пример входных данных:
6789
111
Пример выходных данных:
6
12
Для решения этой задачи нужно немного по-другому взглянуть на условие: будем искать последовательность чисел в данной строке, а не заданную строку в бесконечной последовательности. Согласитесь, если так трансформировать задачу, придется совершить значительно меньше итераций. Будем искать число в данной последовательности, начиная с последовательности из одноразрядных чисел и до чисел равных длине строки, пока не найдем. Если число не состоит ни из каких чисел, то ответом будет позиция первой цифры этого числа.
Более подробно опишу последовательность действий:
- Будет 2 цикла:
- По разрядам числа (начинается с 1 и заканчивается размером числа, которое мы ищем);
- По сдвигу: ведь пришедшее число не обязано начинаться с начала какого-то числа, оно может начинаться в середине одного числа и заканчиваться в середине другого.
- В ходе выполнения этих двух циклов проверяем, состоит ли число из последовательных чисел выбранного разряда. Если нет, продолжаем поиск; если да, проходим по всем возможным числам данного разряда, так как может получиться, что первое найденное не наименьшее.
Самый простой случай: число 123 состоит из последовательности одноразрядных чисел 1, 2 и 3:
Давайте рассмотрим подробнее, какие исключительные случаи могут возникнуть
Число не может начинаться с 0
Тут все просто: если число начинается с 0, то это продолжение другого числа.
Число, которое входит в состав искомой последовательности, может не иметь конца
Например, число 293. Ответом в задаче будет не позиция первой цифры числа 293, а позиция первой цифры числа 29. При этом число 30 не имеет конца в искомой последовательности.
Число, которое входит в состав искомой последовательности, может не иметь начала
Например, последовательность 930. Ответом в задаче будет не позиция первой цифры числа 930, а позиция второй цифры числа 29. При этом число 29 не имеет начала в искомой последовательности.
При проходе последовательности мы можем перейти к числам более высокого разряда
Тут ничего сложного, это просто нужно учесть в нашем проходе, иначе можно получить неправильный результат. Если мы доходим до последнего числа данного разряда, то следующее число будет на 1 разряд больше.
Пример: последовательность 8910. Когда доходим до 9, нужно понять, что следующее число будет двухразрядное.
Первое найденное число не обязательно максимальное
Пример: число 92. Вначале может показаться, что правильный ответ — первая цифра числа 92. Но на самом деле правильный ответ — вторая цифра числа 19. Из этого можно сделать вывод, что, когда мы нашли ответ в искомой последовательности, нужно до конца пройти все итерации чисел данной размерности, и если найдено несколько ответов, то выбрать наименьший.
Число, состоящее из одних нулей
Легче всего эту ситуацию разобрать отдельно. Если число состоит из одних нулей, то ответом будет позиция второй цифры числа 1 и данное количество нулей. Например, 5 нулей. Ответ: вторая цифра числа 100 000.
Исходный код на java:
public long findSequence(String str) {
int strLen = str.length();
int maxNumRank = strLen;
if (new BigDecimal(str).equals(BigDecimal.ZERO)) {
return getPosition(new BigDecimal("1"+str), 0, strLen) + 1;
}
for (int numLen = 1; numLen <= maxNumRank; numLen++) {
List positions = new ArrayList<>();
for (int shift = 0; shift < numLen; shift++) {
// число не может начинаться с 0
if (str.charAt(shift) == '0') {
continue;
}
BigDecimal firstNum;
if (numLen + shift <= maxNumRank) {
firstNum = new BigDecimal(str.substring(shift, shift + numLen));
} else {
String greatRanks = str.substring(shift, maxNumRank);
String lessRanksPrev = str.substring(maxNumRank - numLen, shift);
DecimalFormat df = new DecimalFormat(String.format("%0" + numLen + "d", 0));
String lessRanks = df.format(new BigDecimal(lessRanksPrev).add(BigDecimal.ONE))
.substring(numLen - lessRanksPrev.length(), numLen);
firstNum = new BigDecimal(greatRanks + lessRanks);
}
// сравниваю первое число и хвост предыдущего
String firstNumMinus1 = String.valueOf(firstNum.subtract(BigDecimal.ONE));
if (shift != 0 &&
!firstNumMinus1.substring(firstNumMinus1.length() - shift).equals(str.substring(0, shift))) {
continue;
}
boolean isFound = true;
int j = shift;
int numLenForIter = numLen;
BigDecimal firstNumForIter = firstNum;
// прохожусь по всей строке
while (j < strLen - numLenForIter) {
j += numLenForIter;
if (firstNumForIter.equals(new BigDecimal(Math.pow(10, numLenForIter) - 1))) {
numLenForIter += 1;
}
if (j + numLenForIter <= strLen) {
// сравниваю два числа
BigDecimal secondNum = new BigDecimal(str.substring(j, j + numLenForIter));
if (!firstNumForIter.add(BigDecimal.ONE).equals(secondNum)) {
isFound = false;
break;
}
firstNumForIter = secondNum;
} else {
// сравниваю число и начало следующего числа
DecimalFormat df = new DecimalFormat(String.format("%0" + numLenForIter + "d", 0));
if (!df.format(firstNumForIter.add(BigDecimal.ONE)).substring(0, strLen - j).equals(str.substring(j))) {
isFound = false;
break;
}
return getPosition(firstNum, shift, numLen);
}
}
if (isFound) {
positions.add(getPosition(firstNum, shift, numLen));
}
}
if (!positions.isEmpty()) {
return Collections.min(positions);
}
}
return -1;
}
private long getPosition(BigDecimal num, int shift, int numLen) {
int minus = 0;
for (int i = 1; i < numLen; i++) {
minus += Math.pow(10, i);
}
return num.multiply(new BigDecimal(numLen)).subtract(new BigDecimal(minus)).subtract(new BigDecimal(shift)).longValue();
}
Некоторые для решения второй задачи использовали один из стандартных алгоритмов поиска подстроки в строке. Например, алгоритм Кнута — Морриса — Пратта или алгоритм Бойера — Мура. Это, конечно, лучше полного поиска подстроки в строке, но все-таки дольше, чем искать последовательность чисел в заданной строке.
Если рассмотреть самый сложный случай, т. е. когда число не содержит никаких подпоследовательностей и ответом будет индекс первой цифры этого числа, то при любой реализации поиска последовательности в строке понадобится операций поиска (в том или ином виде), если очень грубо, порядка 10 в степени (m-1). Но при поиске паттерна в искомой строке мы получим максимум m в 3-й степени операций, где m — это длина входной строки. Таким образом, видно, что сложность любого алгоритма поиска в строке будет иметь экспоненциальный порядок от длины входящей последовательности, в то время как поиск паттерна спокойно отработает даже для больших значений m.
Мы не принимали решения, где число ищется полным перебором. И, к сожалению, у большинства реализовавших данный алгоритм, не проходили все тесты.
Наиболее частые ошибки:
- Начинали последовательность с 0
- Ошибались, если число состояло из одних нулей
- Не учитывали одну из исключительных ситуаций, описанных выше
Полный код решения задач, программы проверки и главное — файла для проверки можно посмотреть здесь.
