Analysis of the tasks of the second stage of the School Programmers HeadHunter 2017
The second stage of selection in the School of Programmers is over. Many of those who entered the School asked to tell the algorithms for solving problems, and most importantly, to send combinations in which their program does not work. In this article, the solutions of the proposed tasks will be described, and at the end of the article you will see a link to github, where the code for the described solutions, the code for the verification program and test cases are posted. All code is written in java (although the solution to the second problem is easier to write in python). I will not argue that these are the only correct solutions, there are others, but these I like the most.
Some statistics: slightly more than 900 people submitted an application, 450 people passed the first stage, about 300 people completed the task of the second stage and 105 people came for an interview. The school enrolled 25 people. Interviews lasted 6 weeks. Approximately 15 HeadHunter employees participated in the selection of students.
Task text:
')
Suppose one day you are on a rectangular island.
The landscape of this island can be described using an integer matrix of size MxN, each element of which sets the height of the corresponding area of the island above sea level.
For example, here’s a small 3x3 island:
4 5 4
3 1 5
5 4 1
During the rainy season, the island is completely flooded with water, and water accumulates in the lowlands. Lowland will be considered such an area of the island, the cells of which are adjacent to cells that are large in height. In this case, the diagonal neighbors are not taken into account, and the sea level is taken as 0. In the example above, there is only one lowland on the island - a cell with a value of 1 in the middle of the island (it borders on 3, 5, 5, and 4 cells).
Thus, after the rain, the height of the island’s cells will change and become the following:
4 5 4
3 3 5
5 4 1
We see that in this example, the height of the lowlands changed from 1 to 3, after which the water began to overflow into neighboring cells, and then into the sea. The total volume of water accumulated on the island is 2 cubic cells.
Here is an example more complicated:
5 3 4 5
6 2 1 4
3 1 1 4
8 5 4 3
After the rain, the island’s map takes the following form:
5 3 4 5
6 3 3 4
3 3 3 4
8 5 4 3
The total volume of water accumulated after the rain on such an island is as much as 7 cubic cells!
A two-dimensional array is input to the function; the output is expected to be int - the values of the total volume of water accumulating on the island after the rainy season for each of the input examples.
Limitations:
The size of the island N and M are integers in the range [1, 50]
Heights on the island can take values from the range [1, 1000].
The simplest solution to the problem is to “drain” the island: we assume that the island is a cube filled with water, where the height of the cube is the highest point of the island.
The algorithm works as follows:
Java source code:
You can, of course, solve this problem and fill the island, but it is much more difficult and longer (especially if there are several lowlands). Most of these solutions did not work in all situations and were long processed on big data. Although several people sent such solutions that worked correctly, but still not very quickly.
Task text:
Take an infinite digital sequence formed by gluing together successive positive numbers: S = 123456789101112131415 ...
Determine the first occurrence of a given sequence A in an infinite sequence S (numbering starts with 1).
Sample input:
6789
111
Sample output:
6
12
To solve this problem, you need to take a slightly different look at the condition: we will look for a sequence of numbers in a given string, rather than a given string in an infinite sequence. Agree, if you transform the task in this way, you will have to perform significantly fewer iterations. We will search for a number in a given sequence, starting from a sequence of single-digit numbers to numbers equal to the length of the string, until we find it. If the number does not consist of any numbers, then the answer will be the position of the first digit of this number.
I will describe the sequence of actions in more detail:
The simplest case: the number 123 consists of a sequence of single-digit numbers 1, 2 and 3:
The number can not start from 0
Everything is simple: if the number starts from 0, then this is a continuation of another number.
The number that is part of the desired sequence may not have an end
For example, the number 293. The answer in the problem is not the position of the first digit of the number 293, but the position of the first digit of the number 29. At the same time, the number 30 has no end in the desired sequence.
The number that is part of the desired sequence may not have a beginning
For example, the sequence is 930. The answer in the problem will not be the position of the first digit of the number 930, but the position of the second digit of the number 29. At the same time, the number 29 has no beginning in the desired sequence.
With the passage of the sequence, we can go to the numbers of higher order
There is nothing complicated, it just needs to be taken into account in our passage, otherwise you can get the wrong result. If we reach the last number of this digit, then the next number will be 1 bit higher.
Example: sequence 8910. When we reach 9, we need to understand that the next number will be two-digit.
The first number found is not necessarily the maximum.
Example: the number 92. At the beginning it may seem that the correct answer is the first digit of the number 92. But in fact, the correct answer is the second digit of the number 19. From this we can conclude that when we found the answer in the desired sequence, you need to go to the end all iterations of numbers of a given dimension, and if several answers are found, then choose the smallest one.
The number consisting of one zeros
It is easiest to disassemble this situation separately. If the number consists of only zeros, then the answer will be the position of the second digit of the number 1 and the given number of zeros. For example, 5 zeros. Answer: the second digit of the number 100 000.
Java source code:
Some used one of the standard substring search algorithms to solve the second problem. For example, the Knut-Morris-Pratt algorithm or the Boyer-Moore algorithm. This, of course, is better than a full search for a substring in a string, but still longer than searching for a sequence of numbers in a given string.
If we consider the most difficult case, that is, when the number does not contain any subsequences and the index of the first digit of this number is the answer, then any implementation of the search for a sequence in the line will require search operations (in one form or another), if very roughly, of the order of 10 to the extent (m-1). But when searching for a pattern in the search string, we get a maximum of m in the 3rd degree of operations, where m is the length of the input string. Thus, it can be seen that the complexity of any search algorithm in the string will have an exponential order of the length of the incoming sequence, while the search for a pattern will quietly work even for large values of m.
We did not make decisions where the number is searched by brute force. And, unfortunately, the majority of those who implemented this algorithm did not pass all the tests.
The most frequent errors:
The complete code for solving problems, the verification program and, most importantly, the file for verification can be viewed here .
Some statistics: slightly more than 900 people submitted an application, 450 people passed the first stage, about 300 people completed the task of the second stage and 105 people came for an interview. The school enrolled 25 people. Interviews lasted 6 weeks. Approximately 15 HeadHunter employees participated in the selection of students.
Task 1. Tropical Island
Task text:
')
Suppose one day you are on a rectangular island.
The landscape of this island can be described using an integer matrix of size MxN, each element of which sets the height of the corresponding area of the island above sea level.
For example, here’s a small 3x3 island:
4 5 4
3 1 5
5 4 1
During the rainy season, the island is completely flooded with water, and water accumulates in the lowlands. Lowland will be considered such an area of the island, the cells of which are adjacent to cells that are large in height. In this case, the diagonal neighbors are not taken into account, and the sea level is taken as 0. In the example above, there is only one lowland on the island - a cell with a value of 1 in the middle of the island (it borders on 3, 5, 5, and 4 cells).
Thus, after the rain, the height of the island’s cells will change and become the following:
4 5 4
3 3 5
5 4 1
We see that in this example, the height of the lowlands changed from 1 to 3, after which the water began to overflow into neighboring cells, and then into the sea. The total volume of water accumulated on the island is 2 cubic cells.
Here is an example more complicated:
5 3 4 5
6 2 1 4
3 1 1 4
8 5 4 3
After the rain, the island’s map takes the following form:
5 3 4 5
6 3 3 4
3 3 3 4
8 5 4 3
The total volume of water accumulated after the rain on such an island is as much as 7 cubic cells!
A two-dimensional array is input to the function; the output is expected to be int - the values of the total volume of water accumulating on the island after the rainy season for each of the input examples.
Limitations:
The size of the island N and M are integers in the range [1, 50]
Heights on the island can take values from the range [1, 1000].
The simplest solution to the problem is to “drain” the island: we assume that the island is a cube filled with water, where the height of the cube is the highest point of the island.
The algorithm works as follows:
- We supplement everything, except extreme points, to the maximum height.
- We pass on the island, starting from the edges, and "merge" it:
- At each point we look for the minimum height of its neighboring points (we do not take diagonal points into account according to the condition of the problem).
- If the found minimum value is less than the height of the current point, then reduce the value of the current point to the minimum or to the original height of this point.
- Pass through all points until the values stop changing.
- Then we simply calculate the accumulated water: elementwise we subtract empty from the filled island and add the resulting values.
Java source code:
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(); } You can, of course, solve this problem and fill the island, but it is much more difficult and longer (especially if there are several lowlands). Most of these solutions did not work in all situations and were long processed on big data. Although several people sent such solutions that worked correctly, but still not very quickly.
Task 2. Infinite sequence
Task text:
Take an infinite digital sequence formed by gluing together successive positive numbers: S = 123456789101112131415 ...
Determine the first occurrence of a given sequence A in an infinite sequence S (numbering starts with 1).
Sample input:
6789
111
Sample output:
6
12
To solve this problem, you need to take a slightly different look at the condition: we will look for a sequence of numbers in a given string, rather than a given string in an infinite sequence. Agree, if you transform the task in this way, you will have to perform significantly fewer iterations. We will search for a number in a given sequence, starting from a sequence of single-digit numbers to numbers equal to the length of the string, until we find it. If the number does not consist of any numbers, then the answer will be the position of the first digit of this number.
I will describe the sequence of actions in more detail:
- There will be 2 cycles:
- By the digits of the number (starting with 1 and ending with the size of the number we are looking for);
- According to the shift: the coming number does not have to start from the beginning of a certain number; it can begin in the middle of one number and end in the middle of another.
- During the execution of these two cycles, we check whether the number consists of consecutive numbers of the selected digit. If not, continue searching; if yes, we go through all the possible numbers of the given digit, as it may happen that the first found is not the smallest.
The simplest case: the number 123 consists of a sequence of single-digit numbers 1, 2 and 3:
Let's take a closer look at what exceptional cases may arise.
The number can not start from 0
Everything is simple: if the number starts from 0, then this is a continuation of another number.
The number that is part of the desired sequence may not have an end
For example, the number 293. The answer in the problem is not the position of the first digit of the number 293, but the position of the first digit of the number 29. At the same time, the number 30 has no end in the desired sequence.
The number that is part of the desired sequence may not have a beginning
For example, the sequence is 930. The answer in the problem will not be the position of the first digit of the number 930, but the position of the second digit of the number 29. At the same time, the number 29 has no beginning in the desired sequence.
With the passage of the sequence, we can go to the numbers of higher order
There is nothing complicated, it just needs to be taken into account in our passage, otherwise you can get the wrong result. If we reach the last number of this digit, then the next number will be 1 bit higher.
Example: sequence 8910. When we reach 9, we need to understand that the next number will be two-digit.
The first number found is not necessarily the maximum.
Example: the number 92. At the beginning it may seem that the correct answer is the first digit of the number 92. But in fact, the correct answer is the second digit of the number 19. From this we can conclude that when we found the answer in the desired sequence, you need to go to the end all iterations of numbers of a given dimension, and if several answers are found, then choose the smallest one.
The number consisting of one zeros
It is easiest to disassemble this situation separately. If the number consists of only zeros, then the answer will be the position of the second digit of the number 1 and the given number of zeros. For example, 5 zeros. Answer: the second digit of the number 100 000.
Java source code:
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<Long> 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(); } Some used one of the standard substring search algorithms to solve the second problem. For example, the Knut-Morris-Pratt algorithm or the Boyer-Moore algorithm. This, of course, is better than a full search for a substring in a string, but still longer than searching for a sequence of numbers in a given string.
If we consider the most difficult case, that is, when the number does not contain any subsequences and the index of the first digit of this number is the answer, then any implementation of the search for a sequence in the line will require search operations (in one form or another), if very roughly, of the order of 10 to the extent (m-1). But when searching for a pattern in the search string, we get a maximum of m in the 3rd degree of operations, where m is the length of the input string. Thus, it can be seen that the complexity of any search algorithm in the string will have an exponential order of the length of the incoming sequence, while the search for a pattern will quietly work even for large values of m.
We did not make decisions where the number is searched by brute force. And, unfortunately, the majority of those who implemented this algorithm did not pass all the tests.
The most frequent errors:
- Begin the sequence with 0
- Wrong if the number was all zeros.
- Did not consider one of the exceptional situations described above.
The complete code for solving problems, the verification program and, most importantly, the file for verification can be viewed here .
Source: https://habr.com/ru/post/342942/
All Articles