Lecture
Это продолжение увлекательной статьи про .
...
corner.
85 must be in one of the two white areas.
Thus, we divide our grid into four quadrants and perform the search in the bottom left and top right quadrants. These, too, can be split into quadrants and the search continued.
Notice that the diagonal is sorted, which means we can effectively use binary search.
The code below implements this algorithm:
public Coordinate findElement(int[][] matrix, Coordinate origin, Coordinate dest, int x) {
if (!origin.inbounds(matrix) || !dest.inbounds(matrix)) {
return null;
}
if (matrix[origin.row][origin.column] == x) {
return origin;
} else if (!origin.isBefore(dest)) {
return null;
}
/* Set start to the beginning of the diagonal, and end to the end
* of the diagonal. Since the grid may not be square, the end
* of the diagonal may not equal dest. */
Coordinate start = (Coordinate) origin.clone();
int diagDist = Math.min(dest.row - origin.row, dest.column - origin.column);
Coordinate end = new Coordinate(start.row + diagDist, start.column + diagDist);
Coordinate p = new Coordinated(0, 0);
/* Perform a binary search along the diagonal, looking for the first
* element greater than x */
while (start.isBefore(end)) {
p.setToAverage(start, end);
if (x > matrix[p.row][p.column]) {
start.row = p.row + 1;
start.column = p.column + 1;
} else {
end.row = p.row - 1;
end.column = p.column - 1;
}
}
/* Split the grid into quadrants. Search the lower left and upper
* right quadrants */
return partitionAndSearch(matrix, origin, dest, start, x);
}
public Coordinate partitionAndSearch(int[][] matrix,
Coordinate origin. Coordinate dest, Coordinate pivot, int elem) {
Coordinate lowerLeftOrigin = new Coordinate(pivot.row, origin.column);
Coordinate lowerLeftDest = new Coordinate(dest.row, pivot.column - 1);
Coordinate upperRightOrigin = new Coordinate(origin.row, pivot.column);
Coordinate upperRightDest = new Coordinate(pivot.row - 1, dest.column);
Coordinate lowerLeft = findElement(matrix, lowerLeftOrigin, lowerLeftDest, elem);
if (lowerLeft == null) {
return findElement(matrix, upperRightOrigin, upperRightDest, elem);
}
return lowerLeft;
}
public static Coordinate findElement(int[][] matrix, int x) {
Coordinate origin = new Coordinate(0, 0);
Coordinate dest = new Coordinate(matrix.length - 1, matrix .length - 1);
return findElement(matrix, origin, dest, x);
}
public class Coordinate implements Cloneable {
public int row;
public int column;
public Coordinate(int r, int c) {
row = r;
column = c;
}
public boolean inbounds(int[][] matrix) {
return row >= 0 && column >= 0 &&
row < matrix.length && column < matrix .length;
}
public boolean isBefore(Coordinate p) {
return row <= p.row && column <= p.column;
}
public Object clone() {
return new Coordinate(row, column);
}
public void setToAverage(Coordinate min, Coordinate max) {
row = (min.row + max.row) / 2;
column = (min.column + max.column) / 2;
}
}
This code is fairly difficult to write correctly on the first try.
Remember that you'll make your life easier by breaking code out into methods. When writing programs, focus on the key parts. Putting it all together is something you can always do afterward.
Analysis taken from the book by Gayle L. McDowell, "Cracking the Coding Interview" (available in translation).
Original article.
Write a method that finds the maximum of two numbers without using if-else operators or any other comparison operators.
Show answer
The most common way to implement the max function is to check the sign of the expression a - b. In this case we can't use a comparison operator, but we can use multiplication.
Let's denote the sign of the expression a - b as k. If a - b >= 0, then k = 1, otherwise k = 0. Let q be the inverted value of k.
The code will look like this:
/* Flip 1 to 0 and 0 to 1 */
int flip(int bit) {
return 1^bit;
}
/* Return 1 if the number is positive, and 0 if negative*/
int sign(int a) {
return flip((a >> 31) & 0x1);
}
int getMaxNaive(int a, int b) {
int k = sign(a - b);
int q = flip(k);
return a * k + b * q;
}
This is almost working code (you can check). Problems start with overflow. Suppose a = INT_MAX - 2 and b = -15. In this case a - b will no longer fit into INT_MAX and will cause overflow (the value becomes negative).
We can use the same approach but come up with a different implementation. We need k = 1 to hold when a > b. For this we'll have to use somewhat more complex logic.
When does overflow of a - b occur? Only when a is a positive number and b is negative (or vice versa). It's hard to detect the fact of overflow, but we are able to tell that a and b have different signs. If a and b have different signs, then let k = sign(a).
The logic will be as follows:
The following code implements this algorithm using multiplication instead of comparison operators (check it):
int getMax(int a, int b) {
int c = a - b;
int sa = sign(a); // 1 if a >= 0, otherwise 0
int sb = sign(b); // 1 if a >= 1, otherwise 0
int sc = sign(c); // depends on overflow of a - b
/* Goal: find k, which = 1 if a > b, and 0 if a < b.
* if a = b, k doesn't matter */
// If a and b have different signs, then k = sign(a)
int use_sign_of_a = sa ^ sb;
// If a and b have the same sign, then k = sign(a - b)
int use_sign_of_c = flip(sa ^ sb);
int k = use_sign_of_a * sa + use_sign_of_c * sc;
int q = flip(k); // flip of k
return a * k + b * q;
}
Note that for the sake of clarity we split the code into methods and introduce variables. This is not the most compact or efficient way of writing code, but it makes the code more understandable.
Analysis taken from the book by Gayle L. McDowell, "Cracking the Coding Interview" (available in translation).
Original article.
On a deserted highway, the probability of a car appearing over a 30-minute period is 0.95. What is the probability of a car appearing over 10 minutes?
Show answer
This question is difficult only because the information you were given is not the information you'd like to have. However, this happens often in real life.
You'd like to determine the probability relating to 10 minutes, given the probability for 30 minutes. You can't simply divide 0.95 by three (although, admittedly, some people try to do this). Knowing the probability that a car will pass within 30 minutes isn't of much help, since this could happen at any time. A car could pass in the first 10-minute segment, or the second, or the third. During each of these periods, two cars could pass, or five, or a thousand, but that all still counts as a car passing.
What you'd actually like to know is the probability that no car passes at all during the 30-minute period. That's fairly easy to find out. Since there is a 95% chance that at least one car will pass in 30 minutes, the probability that there will be no car at all during that time period must be 0.05.
For there to be no car during the 30-minute segment, three things must happen (or, rather, not happen). First, there must be no car during 10 minutes. Then another 10 minutes must pass with no cars at all. And finally, the third 10 minutes must also be without cars. The question asks for the probability of a car appearing during a 10-minute period. Let's call it X. The probability of no cars during these 10 minutes is 1 - X. Multiply this value by itself three times. It must equal 0.05, that is
(1 - X)³ = 0.05
Let's take the cube root of both sides.
1 - X = ³?0.05
Let's solve this equation for X.
X = 1 - ³?0.05
No one expects you to be able to extract cube roots in your head. A computer will tell you the answer is about 0.63. This result makes sense. The probability of a car appearing in a 10-minute period should be lower than its probability of appearing, 0.95, over a 30-minute period.
Analysis taken from the book "Are You Smart Enough to Work at Google?".
Original article.
Write a function that sums two integers without using «+» or any other arithmetic operators.
Show answer
The first thing that comes to mind is bit manipulation. Why? We have no choice — we cannot use the «+» operator. So let's sum the numbers the way computers do!
Now we need to figure out how summation works. Additional problems allow us to develop new skills, learn something interesting, and create new patterns.
So let's consider an additional problem. We'll use the decimal number system.
To sum 759 + 674, I usually add the digits of both numbers, carry the one, then move on to the next digit, carry, and so on. The same approach can be applied to bits: sum all the digits and carry ones as needed.
Can the algorithm be simplified? Yes! Suppose I want to separate «summing» and «carrying». I would have to do the following:
Perform the operation 759 + 674, ignoring carrying. The result is 323.
Perform the operation 759 + 674, but only carry (without summing digits). The result is 1110.
Now we need to add the results of the first two operations (using the same mechanism described in steps 1 and 2): 1110 + 323 = 1433.
Now let's go back to the binary system.
If a pair of binary numbers is summed without accounting for carrying, then the i-th summed bit can be zero only if the i-th bits of numbers a and b matched (both had a value of 0 or 1). This is the classic XOR operation.
If a pair of numbers is summed performing only carrying, then the i-th bit of the sum is assigned a value of 1 only if the (i-1)-th bits of both numbers (a and b) had a value of 1. This is an AND operation with a shift.
These steps must be repeated until no carries remain.
The following code implements this algorithm.
public static int add(int a, int b) {
if (b == 0) return a;
int sum = a ^ b; // add without carry
int carry = (a & b) << 1; // carry without summing
return add(sum, carry); // recursion
}
Problems related to implementing basic operations (addition, subtraction) are quite popular. To solve such a problem, you need to understand how the operations are normally implemented, and then find a way to write code that takes the constraints into account.
Analysis taken from Gayle L. McDowell's book «Cracking the Coding Interview» (available in translation).
Original article.
You have a fleet of 50 trucks. Each of them is fully fueled and can travel 100 km. How far can you deliver a given load using them? What if you have N trucks at your disposal?
Not everyone immediately understands what's being asked: geographically, this is a place with no gas stations whatsoever. The only place where fuel can be found here is in the trucks' fuel tanks. You cannot switch from a truck to a hybrid Prius passenger car. Abandoning a truck without fuel, wherever that may happen, and without a driver, is perfectly acceptable. And the only thing that matters here is delivering the valuable cargo as far as possible.
Show answer
There is enough fuel to send each of the 50 trucks a distance of 100 km, that is, a distance of 50*100 = 5000 km. But can 5000 km be considered the answer? No, unless you have a way to teleport fuel from the tank of one truck to another. Remember that each truck is fully fueled, and until the fuel is used up, no more can be added.
Start with a simple step. Imagine you have not 50 trucks, but just one. Load it, get into the cab, and hit the road. After 100 km, the road ends for you.
Now suppose you have two trucks. You load the first one and can go 100 km without worrying about anything. But then what? Can the second truck help you? No. It is 100 km away from you. It would have to follow you, so its tank would also run out after the same 100 km.
Perhaps the first truck should tow the second? When the first truck runs out of fuel, the cargo could be transferred to the second truck, whose tank is full, and you could continue on. Yes, that gives you another 100 km.
And how far would the first truck be able to travel in such a coupling? Hardly 100 km. It would have to haul twice the normal weight. The laws of physics say that, at best, it would travel only half the previous distance. In real life, the fuel consumption per km for a heavier vehicle increases more sharply than its weight.
What if we look at it differently? Suppose the two trucks set out at the same time, each on its own. After 50 km, each tank will be half empty, but you can fill one tank to the top. Transfer the fuel from one tank to the other. Leave the empty truck behind and drive another 100 km on the full tank. The total distance covered would be 150 km. Unlike towing, there is no theoretical limit here, and this approach can be fully applied in practice.
With three trucks, the towing option becomes questionable, but the idea of transferring fuel still works well. Send all three trucks out at once. Have them stop at a third of the 100 km distance, that is, after driving about 33.33 km. Each tank has 2/3 of its fuel left. Transfer the fuel from one truck into the tanks of the other two — they are full again. Then send these two trucks on their way. We already know that the maximum distance for them is 150 km. If you add the first 33.33 km to that, the total distance is a little over 183 km.
The pattern becomes clear. One truck can travel 100 km. A second truck lets you increase the total distance by 100/2 = 50 km. A third truck increases the total distance by 100/3 km. A fourth truck adds 100/4 km. For N trucks, the total distance would be: 100*(1/1+1/2+1/3+1/4+1/5+…1/N)
The fractional part in this case is known as the harmonic series. The sum of the terms of the harmonic series can easily be calculated. If N equals 50, the sum of this progression is 4.499… Multiply it by 100 km, and you'll see that with 50 trucks at your disposal, you can deliver the load 449.9 km.
As N increases, the sum grows. With enough trucks, you can take the load anywhere you want. However, as N increases, the distance grows very slowly, and the energy efficiency becomes very low. The thousandth truck will add only 1/100 km to the total distance the load travels (but it will pollute the atmosphere with carbon dioxide emissions just like all the other vehicles). The millionth truck will increase the entire distance by only a few centimeters.
The answer given above is a valid one. Is there another? There is, if fuel can be transported, and if the load is not very heavy.
The question refers to trucks designed to carry large and heavy loads. Suppose you have GMC or Ford trucks. The empty weight of such a fully fueled and equipped vehicle is about 2250 kg. It is designed to safely carry such a heavy load, unless you're transporting packaged peanuts or cotton candy.
A truck's tank holds about 30 gallons of fuel, a volume equivalent to roughly 120 liters.
The key question: does the fuel weigh less than the truck itself? Less, since 200/5000 is 1/25 of the weight of the truck without cargo but fully fueled.
It would be foolish to tow or carry a 2250 kg truck when all you're interested in is the 120 liters of fuel in its tank. Wouldn't it be better to carry the fuel in the truck's bed along with the cargo being delivered? (Perhaps you could find containers for the fuel, or remove the fuel tanks from other trucks and use them as such containers.) A truck can carry fuel equivalent to a full tank of 25 trucks, provided the useful load weighs little.
This means that a single such truck can carry half the fuel of a fleet of 50 vehicles. It could travel 25*100, or 2500 km. However, it is unlikely to do so, because the cargo it's carrying will reduce this distance. Nevertheless, let's assume that this option would allow it to travel around 1500 km. This is more than three times the 450 km achieved with the fuel-transfer option, and requires only one truck and one driver.
Analysis taken from the book «Are You Smart Enough to Work at Google?».
Original article.
Describe an algorithm for finding the million smallest numbers in a set of a billion numbers. The computer's memory is enough to store the entire billion numbers. If you come up with a solution, evaluate its time efficiency. Is there a more efficient solution?
Show answer
There are many ways to solve this problem. We will focus on only three — sorting, min-heap, and ranking.
Solution 1. Sorting
You can sort the elements in ascending order and then take the first million numbers. This will require O(n log(n)) time.
Solution 2. Min-heap
To solve this problem, you can use a min-heap. We first build a heap of the first million numbers with the largest element on top.
Then we go through the rest of the list. When inserting an element into the list, we remove the largest element.
In the end we get a heap containing the million smallest numbers. The efficiency of the algorithm is O(n log(m)), where m — is the number of values to be found.
Solution 3. Ranking (if modifying the original array is allowed)
This algorithm is very popular and allows you to find the i-th smallest (or largest) element in an array.
If the elements are unique, finding the i-th smallest element requires O(n) time. The basic algorithm will be as follows:
Choose a random element in the array and use it as the "pivot." Partition the elements around the pivot, keeping track of the number of elements to the left.
If there are exactly i elements to the left, you need to return the largest element.
If there are more elements to the left than i, then repeat the algorithm, but only for the left part of the array.
If there are fewer elements to the left than i, then repeat the algorithm on the right side, but look for the element with rank i - leftSize.
The following code implements this algorithm.
public int partition(int[] array, int left, int right, int pivot) {
while (true) {
while (left <= right && array[left] <= pivot) {
left++;
}
while (left <= right && array[right] > pivot) {
right--;
}
if (left > right) {
return left - 1;
}
swap(array, left, right);
}
}
public int rank(int[] array, int left, int right, int rank) {
int pivot = array[randomIntInRange(left, right)];
/* Partition and return the end of the left partition */
int leftEnd = partition(array, left, right, pivot);
int leftSize = leftEnd - left + 1;
if (leftSize == rank + 1) {
return max(array, left, leftEnd);
} else if (rank < leftSize) {
return rank(array, left, leftEnd, rank);
} else {
return rank(array, leftEnd + 1, right, rank - leftSize);
}
}
Once the smallest i-th element has been found, you can go through the array and find all values that are less than or equal to this element.
If elements repeat (they are unlikely to be "unique"), you can slightly modify the algorithm to accommodate this condition. But in this case it will be impossible to predict its running time.
There is an algorithm that guarantees we will find the smallest i-th element in linear time, regardless of the "uniqueness" of the elements. However, this problem is somewhat more complex. If you are interested in this topic, this algorithm is given in the book by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, "CLRS" Introduction to Algorithms" (available in translation).
Analysis taken from the translation of the book by G. Lakman McDowell and intended solely for informational purposes.
Original article.
Write a method that will count the number of digits "2" used in the decimal representation of integers from 0 to n (inclusive). A picture is given as a hint toward one of the possible solutions.
Show answer
As always, we will first try to solve the problem "head-on."
/* Count the number of '2's between 0 and n */
int numberOf2sInRange(int n) {
int count = 0;
for (int i = 2; i <= n; i++) { // We can start from 2
count += numberOf2s(i);
}
return count;
}
/* count the number of '2's in a single number */
int numberOf2s(int n) {
int count = 0;
while (n > 0) {
if (n % 10 == 2) {
count++;
}
n = n / 10;
}
return count;
}
The only interesting part of this algorithm is extracting numberOf2s into a separate method. This is done for the sake of code cleanliness.
We can look at the problem not in terms of ranges of numbers, but in terms of digit positions — digit by digit.
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
...
110 111 112 113 114 115 116 117 118 119
We know that in a consecutive sequence of ten numbers, the last digit takes the value 2 only once. And in general, any digit position can equal 2 once out of every ten.
Although here we should use the word "approximately," because boundary conditions must be taken into account. Counting the number of twos for the ranges 1-100 and 1-37 will differ.
The exact number of twos can be computed by considering each digit position separately: digit < 2, digit = 2, and digit > 2.
Case: digit < 2
If x = 61523 and d = 3, then x[d] = 1 (this means that the d-th digit of x equals 1). Consider the twos located in the 3rd digit position, in the ranges 2000-2999, 12000-12999, 22000-22999, 32000-32999, 42000-42999, and 52000-52999. We will not count the range 62000-62999. These ranges contain 6000 twos located in the 3rd digit position. The same number of twos can be obtained by counting all the twos in the 3rd digit position in the range of numbers from 1 to 6000.
In other words, to calculate the number of twos in the d-th digit position, it is enough to round the value down to the nearest 10d+1, and then divide by 10.
if x[d] < 2: count2sInRangeAtDigit(x, d) =
let y = round down to the nearest 10d+1
return y / 10
Case: digit > 2
Let us consider the case where the value of the d-th digit is greater than 2 (x[d] > 2). Using the same logic, it becomes clear that the number of twos in the 3rd digit position of the range 0-63525 will be the same as in the range 0-7000. Thus, instead of rounding down, we will round up.
if x[d] > 2: count2sInRangeAtDigit(x, d) =
let y = round up to the nearest 10d+1
return y / 10
Case: digit = 2
The last case is the hardest, but we can use the same logic. Let x = 62523 and d = 3. We know that the ranges have not changed (2000-2999, 12000-12999, ..., 52000-52999). How many twos can appear in the 3rd digit position in the range 62000-62523? This is easy to count — 524 (62000, 62001, ..., 62523).
if x[d] > 2: count2sInRangeAtDigit(x, d) =
let y = round down to 10d+1
let z = the right side of x (i.e. x % 10d)
return y / 10 + z + 1
Now we need to go through each digit in the number. The implementation of this code is relatively simple:
public static int count2sInRangeAtDigit(int number, int d) {
int powerOf10 = (int) Math.pow(10, d);
int nextPowerOf10 = powerOf10 * 10;
int right = number % powerOf10;
int roundDown = number - number % nextPowerOf10;
int roundUp = roundDown + nextPowerOf10;
int digit = (number / powerOf10) % 10;
if (digit < 2) { // if digit is less than 2
return roundDown / 10;
} else if (digit == 2) {
return roundDown / 10 + right + 1;
} else {
return roundUp / 10;
}
}
public static int count2sInRange(int number) {
int count = 0;
int len = String.valueOf(number).length();
for (int digit = 0; digit < len; digit++) {
count += count2sInRangeAtDigit(number, digit);
}
return count;
}
This problem requires careful testing. Make sure you know all the edge cases and have checked each one of them.
Analysis taken from the translation of the book by G. Lakman McDowell and intended solely for informational purposes.
Original article.
Where will you swim faster — in water or in syrup?
This is a classic problem with a long history, discussed in his time even by Isaac Newton. At one point it was used in IT interviews at Google (not anymore). Nevertheless, we invite you to reason through the solution.
Expand answer
Isaac Newton and Christiaan Huygens discussed this question back in the 1600s, but never gave an exhaustive answer to it. Three centuries later, two chemists from the University of Minnesota, Brian Gettelfinger and Edward Cussler, carried out an experiment to compare syrup and water. Perhaps it's not surprising that conducting it took a long time. Cussler said that he had to obtain 22 approvals, including permission to eventually pour a large volume of syrup into the sewer system. He had to turn down an offer of 20 truckloads of free corn syrup, since university management decided it would be hazardous to the Minneapolis sewer system. Instead, Cussler used a food thickener used in the production of ice cream, shampoos, and salad dressings. About 300 kg of this substance was poured into a swimming pool. «To tell the truth, the mixture resembled mucus», Cussler remarked. And yet it wasn't mucus, but a slurry roughly twice as dense as water.
Brian Gettelfinger, a promising swimmer and Olympic hopeful, got a unique opportunity to try swimming in this new liquid. The results were published in 2004 in the American Institute of Chemical Engineers Journal. The following year, Gettelfinger and Cussler received the 2005 Ig Nobel Prize in Chemistry. The Ig Nobel Prize is a humorous counterpart to the better-known awards presented in Stockholm, but thanks to wide news coverage of this prize, many people are familiar with it. Perhaps it is precisely this media attention to the syrup problem that explains its recurring appearance on lists of sadistic interview questions.
In the experiment described here, the viscosity of the syrup-like liquid was approximately twice that of ordinary water, while the densities of both liquids were approximately the same. This matters, because, as swimmers have long known, people swim faster in denser salt water. Like a ship, a swimmer's body sits higher in salt water, which reduces the resistance to its forward movement.
Gettelfinger and students from Minnesota swam for speed in both water and «syrup» using standard strokes: backstroke, breaststroke, butterfly, freestyle. But not once did the swimming speed in the two liquids differ by more than a few percentage points. It was not possible to identify any general pattern that would favor either syrup or water.
This meant that Newton was wrong: he believed that the viscosity of the syrup would slow the swimmers' movement. Huygens correctly predicted that there would be no noticeable difference in speed. The paper by Gettelfinger and Cussler confirmed the validity of Huygens's views. Recall how smoke rises from a cigarette: at a distance of a few centimeters from the cigarette it appears as a smooth vertical column, but higher up its shape becomes more complex, as eddies and swirls begin to appear. The eddies are the result of turbulence. Turbulence hinders jet aircraft, high-speed boats, and any body that wants to move faster through a flow. Since the human body is not optimized for swimming, when we swim we create a ridiculous amount of turbulence, which we then have to fight in order to move through the water. Turbulence creates far greater resistance to movement than viscosity does. Moreover, viscosity here hardly matters at all. Since turbulence arises in both water and syrup, the swimming speed in these liquids is approximately the same.
The flow of water is much less turbulent for fish, and especially for bacteria, which would swim slower in syrup.
Can this interview question be considered fair? Cussler said that answering the question about swimming in syrup «probably doesn't require good knowledge of computer science», adding that «anyone with basic knowledge of physics can answer it». Anyone who seriously studies physics may see that this is an overly optimistic view. In any case, most candidates who are asked this question in job interviews do not know physics deeply enough. Therefore, good answers involve using simple intuitive analogies that explain why the solution needs to be obtained through experimentation. Here are four arguments.
1. Some liquids are too thick to swim in.
Ask mastodons to swim in tar pits. Imagine trying to swim in liquid cement or quicksand. Of course, in very thick liquids, although the buoyant force here is greater, you will swim significantly slower than in water, if you manage to swim at all.
2. The term «syrup» can refer to a very wide range of liquids.
The question does not mention tar or quicksand, only syrup. And syrups come in very different kinds, for example, maple syrup, cough syrup, chocolate syrup, high-fructose corn syrup, and liquids with various consistencies, ranging from a watery drink to the thick sediment remaining at the bottom of a bottle. The question as posed cannot be answered until you know exactly which syrup is being discussed, or until you can prove that swimming will be slow in any liquid thicker than water.
3. Suppose there is an optimal viscosity level at which swimming speed is maximal. Is there any reason to believe that this optimal liquid for swimming would be H?O?
Perhaps you would agree with this statement if you were a very perceptive fish. Evolution has ensured that fish are well «suited» to their environment, namely water, which flows smoothly around their sleek bodies. Humans are not very much like fish, and the way we swim doesn't much resemble how fish do it. Neither humans nor our closest ancestors have spent enough time in pools, rivers, lakes, and oceans to develop a set of genes strongly oriented toward swimming. Of course, we sometimes swim and even occasionally go paragliding, but we are not built for these activities. A creature honed for swimming the Australian crawl is simply too unlike a human. Edward Cussler put it this way: «The ideal swimmer should have the body of a snake and the arms of a gorilla».
No wonder, then, that one can find people capable of swimming faster in a liquid with a different viscosity than water. Nor would it be surprising to discover that swimming speed is the same in liquids with very different viscosities.
4. Swimming is a chaotic process.
The motion of liquids and gases is a textbook example of chaos. Too much depends on the smallest details to allow prediction of the outcome. That is why aircraft designers need wind tunnels to test their designs. The human body, poorly adapted to swimming, with its relatively clumsy movements in water, complicates the answer even further. That is precisely why this is one of those questions that requires experiments to be carried out – with a specific type of syrup.
The speech Cussler gave when accepting his Ig Nobel Prize was brief: «The reasons for this are complex».
MythBusters, the episode about swimming in syrup.
Analysis taken from the book «Are You Smart Enough to Work at Google?».
Original article.
Write methods for multiplying, subtracting, and dividing integers, using only the addition operator among the arithmetic operations. The implementation language doesn't matter, and you also don't need to worry too much about optimizing speed or memory usage. The main thing is that only addition can be used. In problems like this, it is useful to recall the essence of mathematical operations.
Expand answer
In this problem, only addition can be used. In problems like this, it is useful to recall the essence of mathematical operations and how they can be implemented using addition (or other operations).
How do you implement subtraction using addition? This is extremely simple. The operation a – b is the same as a + (-1) * b. Since we cannot use the multiplication operator, we'll need to create a negate function.
public static int negate(int a) {
int neg = 0;
int d = a < 0 ? 1 : -1;
while (a != 0) {
neg += d;
a += d;
}
return neg;
}
public static int subtract(int a, int b) {
return a + negate(b);
}
A negative value k is obtained by summing the number -1 k times.
The relationship between addition and multiplication is also fairly obvious. To multiply a and b, you need to add a to itself b times.
public static int multiply(int a, int b) {
if (a < b) {
return multiply(b, a); // the algorithm will be faster if b < a
}
int sum = 0;
for (int i = abs(b); i > 0; i--) {
sum += a;
}
if (b < 0) {
sum = negate(sum);
}
return sum;
}
public static int abs(int a) {
if (a < 0) {
return negate(a);
} else {
return a;
}
}
When multiplying, we need to pay special attention to negative numbers. If b is a negative number, then the sign of the sum must be taken into account:
multiply(a, b) < — abs(b) * a * (-1 if b < 0).
In addition, to solve this problem we created a simple abs function.
The most complex of the mathematical operations is division. A good idea is to use the multiply, subtract, and negate methods to implement the divide method.
We need to find x, given that x = a / b. Let's reformulate the problem: find x, given that a = bx. Now we have changed the condition so that the problem can be solved using an operation we already know — multiplication.
Note that x can be computed as the result of summing b until a is obtained. The number of instances of b needed to obtain a will be the sought value x.
Of course, this solution cannot be called full-fledged division, but it works. You should understand that this implementation does not produce a remainder from the division.
The code below implements this algorithm:
public int divide(int a, int b)
throws java.lang.ArithmeticException {
if ( b == 0) {
throw new java.lang.ArithmeticException("ERROR");
}
int absa = abs(a);
int absb = abs(b);
int product = 0;
int x = 0;
while (product + absb <= absa) {
product += absb;
x++;
}
if ((a < 0 && b < 0) || (a > 0 && b > 0)) {
return x;
} else {
return negate(x);
}
}
Analysis taken from a translation of the book by G. Laakmann McDowell and intended for informational purposes only
Original article.
Suppose you are writing a pipeline in which 2 threads process data using a shared buffer. The producer thread creates the data, and the consumer thread processes it (Producer–consumer problem). The following code represents the simplest model: using std::thread we spawn a consumer thread, and we will create data in the main thread.
Let's leave aside the synchronization mechanisms of the two threads and focus on the main() function. Try to guess what's wrong with this code and how to fix it.
void produce() {
// create a task and put it in the queue
}
void consume() {
// read data from the queue and process it
}
int main(int , char **) {
std::thread thr(consume); // spawn a thread
produce(); // create data to process
thr.join(); // wait for the consume() function to finish
return 0;
}
Show answer
In C++, unless stated otherwise, it is assumed that any function may throw an exception.
Suppose the consume() function throws an exception. Since this exception is generated in the child thread, it cannot be caught and handled in the main thread1 . If, during stack unwinding in the child thread, no suitable exception handler is found, the std::terminate() function will be called, which by default calls the abort() function. In other words, if an exception is not handled in the thread spawned by the object thr, the program will terminate with an error.
Things are a bit more complicated with the produce() function. Suppose this function throws an exception. The first thing you'd want to do is wrap the body of main() in a try-catch block:
try {
std::thread thr(consume);
produce(); // throws an exception
thr.join();
} catch (...) {
}
It seems the problem is solved, but if you try to run this code, the program will crash regardless. Why does this happen? Let's find out.
As you may have already guessed, the problem has nothing to do with the pipeline, but rather concerns the correct use of standard library execution threads in general. In particular, the following generalized function is equivalent and has the same problems:
void run(function f1, function f2) {
std::thread thr(f1);
f2();
thr.join();
}
...
run(consume, produce);
...
Before moving on to the solution of our problem, let's briefly recall how std::thread works.
1) Constructor for initialization:
template explicit thread (Fn&& fn, Args&&... args);
When a std::thread object is initialized, a new thread is created, in which the function fn is started with the possible arguments args. Upon its successful creation, the specific instance of the object begins to represent this thread in the parent thread, and the joinable flag is set in the object's properties.
Remember: joinable ~ the object is associated with a thread.
2) Waiting for the end of execution of the spawned thread:
void thread::join();
This method blocks further execution of the parent thread until the child thread has finished. After successful execution, the thread object no longer represents it, since our thread no longer exists. The joinable flag is reset.
3) Immediately “detach” the object from the thread:
void thread::detach();
This is a non-blocking method. The joinable flag is reset, and the child thread is left to itself and will finish its work at some point later.
4) Destructor:
thread::~thread();
The destructor destroys the object. If this object has the joinable flag set, the std::terminate() function is called, which by default calls the abort() function.
Attention! If we created an object and a thread, but did not call join or detach, the program will crash. In principle, this is logical – if the object is still associated with a thread, something must be done with it. And even better – to do nothing, and terminate the program (at least, that's what the standards committee decided).
Therefore, when an exception occurs in the produce() function, we attempt to destroy the thr object, which is joinable.
Why did the standards committee decide to do it this way and not otherwise? Wouldn't it have been better to call join() or detach() in the destructor? It turns out, not better. Let's examine both of these cases.
Suppose we have a joining_thread class that calls join() in its destructor like this:
joining_thread::~joining_thread() {
join();
}
Then, before handling the exception, we would have to wait for the child thread to finish, since join() blocks further execution of the program. And what if the spawned thread ended up in an infinite loop?
void consume() {
while(1) { ... }
}
...
try {
joining_thread thr(consume);
throw std::exception();
} catch (...) {
// may happen not soon, or even never
}
Alright, we've established that it's better not to call join() in the destructor (unless you're sure this is the correct way to handle the event), since it's a blocking operation. What about detach()? Why not call this non-blocking method in the destructor, letting the main thread continue working? Suppose we have such a class, detaching_thread.
But then we could end up in a situation where the spawned thread tries to use a resource that no longer exists, as in the following situation:
try {
int data;
detaching_thread th(consume, &data); // in this case consume takes a pointer to an int as an argument
throw std::exception()
} catch (...) {
// correctly handle the exception
// consume continues to execute, but references an already deleted data object
}
Thus, the creators of the standard decided to shift the responsibility onto the programmer – after all, they know best how the program should handle such cases. Based on all this, it turns out that the standard library contradicts the RAII principle – when creating a std::thread, we ourselves must take care of correct resource management, that is, explicitly call join or detach. For this reason, some programmers advise against using std::thread objects directly. Just like new and delete, std::thread provides the ability to build higher-level tools on top of it.
One such tool is the class from the Boost library, boost::thread_joiner. It corresponds to our joining_thread from the example above. If you can afford to use third-party libraries for working with threads, it is better to do so.
Another solution – take care of it yourself in RAII style, for example like this:
class Consumer {
public:
Consumer()
: exit_flag(false)
, thr( &Consumer::run, this )
{
// after creating the thread, do not do anything here that throws an exception,
// because in that case the Consumer object's destructor will not be called,
// the thread will not be terminated, and the program will crash
}
~Consumer() {
exit_flag = true; // tell the thread to stop
thr.join();
}
private:
std::atomic exit_flag; // flag for synchronization (optional)
std::thread thr;
void run() {
while (!exit_flag) {
// do something
}
}
};
If you are going to detach the thread from the object in any case, it is better to do so immediately:
std::thread(consume).detach(); // create the thread, and immediately release the object associated with it
1In fact, an exception can be explicitly passed to another thread using move semantics.
Alexander Petrov specially for "The Typical Programmer."
Original article.
You are given 20 jars of pills. 19 of them contain pills weighing 1 g, and one contains pills weighing 1.1 g. You are given a scale that shows the exact weight. How can you find the jar with the heavy pills in a single weighing?
Expand answer
Sometimes "tricky" constraints can serve as a hint. In our case, the hint is hidden in the information that the scale can be used only once.
We have only one weighing, which means we will have to weigh many pills at the same time. In fact, we must weigh all 19 jars simultaneously. If we skip two (or more) jars, we will not be able to check them. Do not forget: only one weighing!
How, then, can we weigh several jars and figure out which of them contains the "defective" pills? Let's imagine that we have only two jars, one of which contains the heavier pills. If we take one pill from each jar and weigh them together, the total weight will be 2.1 g, but we will not know which of the jars contributed the extra 0.1 g. So we need to weigh them differently.
If we take one pill from jar #1 and two pills from jar #2, what will the scale show? The result depends on the weight of the pills. If jar #1 contains the heavier pills, the weight will be 3.1 g. If jar #2 has the heavy pills, it will be 3.2 grams. An approach to solving the problem has been found.
We can generalize our approach: take one pill from jar #1, two pills from jar #2, three pills from jar #3, and so on. Weigh this set of pills. If all the pills weigh 1 g, the result will be 210 g. The "excess" will be contributed by the jar with the heavy pills.
Thus, the number of the jar can be found by a simple formula: (weight – 210) / 0.1. If the total weight of the pills is 211.3 g, then the heavy pills were in jar #13.
The analysis is taken from a translation of the book by G. Lakmann McDowell and is intended solely for informational purposes.
Original article.
You are given a chessboard measuring 8×8, from which two diagonally opposite corners have been cut out, and 31 domino pieces; each domino piece can cover two squares on the board. Can the board be fully tiled with the dominoes? Justify your answer.
Expand answer
At first glance it seems possible. The board is 8?8, so there are 64 squares; we exclude two, leaving 62. It would seem that 31 dominoes should fit, right?
When we try to lay out the dominoes in the first row, we only have 7 squares available, so one piece spills over into the second row. Then we place dominoes in the second row, and again one piece spills over into the third row.
In every row there will always remain one piece that needs to be carried over to the next row, and no matter how many layout variants we try, we will never manage to lay out all the pieces.
A chessboard is divided into 32 black and 32 white squares. Removing opposite corners (note that these squares are the same color), we are left with 30 squares of one color and 32 squares of the other. Suppose we now have 30 black and 32 white squares.
Every domino we place on the board will occupy one black and one white square. Therefore, 31 dominoes will occupy 31 white and 31 black squares. But our board has only 30 black and 32 white squares in total. Therefore, it is impossible to lay out the pieces.
The analysis is taken from a translation of the book by G. Lakmann McDowell and is intended solely for informational purposes.
Original article.
You are given an input file containing four billion 32-bit integers. Propose an algorithm that generates a number not present in the file. You have 1 GB of memory available for this task. Additionally: what if you only have 10 MB? The number of passes over the file should be minimal.
Expand answer
We have at our disposal 232 (or 4 billion) integers. We have 1 GB of memory, or 8 billion bits.
8 billion bits — a perfectly sufficient volume to map all the integers. What needs to be done?
Create a bit vector with 4 billion bits. A bit vector is an array that compactly stores boolean variables (either int or another data type can be used). Each int-type variable can be treated as 32 bits, or 32 boolean values.
Initialize the bit vector with zeros.
Scan all the numbers (num) from the file and call BV.set(num, 1).
Scan the bit vector once more, starting from index 0.
Return the index of the first element with value 0.
The following code implements our algorithm:
byte[] bitfield = new byte [0xFFFFFFF/8];
void findOpenNumber2() throws FileNotFoundException {
Scanner in = new Scanner(new FileReader("file.txt"));
while (in.hasNextInt()) {
int n = in.nextInt ();
/* Find the corresponding number in bitfield, using
* the OR operator to set the n-th bit of the byte
* (that is, 10 will correspond to the 2nd bit of index 2
* in the byte array). */
bitfield [n / 8] |= 1 << (n % 8);
}
for (int i = 0; i < bitfield.length; i++) {
for (int j = 0; j < 8; j++) {
/* Retrieves individual bits of each byte. When a
* 0 bit is found, we find the corresponding value. */
if ((bitfield[i] & (1 << j)) == 0) {
System.out.println(i * 8 + j);
return;
}
}
}
}
The missing number can be found using a double pass over the data. Let's divide the integers into blocks of some size (we will discuss further how to choose the size correctly). For now let's assume we use blocks of 1000 numbers. So, block0 corresponds to numbers from 0 to 999, block1 — 1000 — 1999, and so on.
We know how many values can be present in each block. Now we analyze the file and count how many values fall within the specified range: 0-999, 1000-1999, and so on. If 998 values are found in a range, the "defective" interval has been found.
On the second pass, we will look for the missing number within that range. We can use the idea of the bit vector considered in the first part of the problem. After all, we don't need numbers that don't fall within the specific range.
How should we choose the block size? Let's introduce a few variables:
Let rangeSize — the size of the ranges of each block on the first pass.
Let arraySize — the number of blocks on the first pass. Note that arraySize = 232/rangeSize.
We need to choose the value of rangeSize so that there is enough memory for both the first pass (array) and the second pass (bit vector).
On the first pass, an array can fit 10 MB, or 223 bytes, of memory. Since each element in the array is of type int, and a variable of type int takes 4 bytes, we can store approximately 221 elements.
We need space to store rangeSize bits. Since 223 bytes fit in memory, we can fit 226 bits in memory. Thus:
We get enough room to "maneuver," but the closer we get to the midpoint we choose, the less memory will be used at any given moment.
The code below provides one implementation of this algorithm:
int bitsize = 1048576; // 2^20 bits (2^17 bytes)
int blockNum = 4096; // 2^12
byte[] bitfield = new byte[bitsize/8];
int[] blocks = new int[blockNum];
void findOpenNumber() throws FileNotFoundException {
int starting = -1;
Scanner in = new Scanner (new FileReader ("file.txt"));
while (in.hasNextInt()) {
int n = in.nextInt();
blocks[n / (bitfield.length * 8)]++;
}
for (int i = 0; i < blocks.length; i++) {
if (blocks[i] < bitfield.length * 8) {
/* if the value < 2^20, then at least 1 number
* is missing in this section. */
starting = i * bitfield.length * 8;
break;
}
}
in = new Scanner(new FileReader("input_file.txt"));
while (in.hasNextInt()) {
int n = in.nextInt();
/* If the number is inside the block that is missing numbers,
* we record it */
if (n >= starting && n < starting + bitfield.length * 8) {
bitfield[(n - starting) / 8] |= 1 << ((n - starting) % 8);
}
}
for (int i = 0 ; i < bitfield.length; i++) {
for (int j = 0; j < 8; j++) {
/* Get the individual bits of each byte. When bit 0
* is found, we find the corresponding value. */
if ((bitfield[i] & (1 << j)) == 0) {
System.out.println(i * 8 + j + starting); return;
}
}
}
}
What if you need to solve the problem under more severe memory constraints? In that case you'll have to make several passes. First go through "million" blocks, then thousand-blocks. Finally, on the third pass you can use a bit vector.
Analysis taken from a translation of the book by G. Lakeman McDowell and is intended solely for informational purposes.
Original article.
Propose an algorithm that generates all valid combinations of pairs of round brackets. By valid combinations of pairs we mean correctly opened and closed brackets. The input is the number of bracket pairs, and the output should be all their possible combinations as a set of strings.
Show answer
The first thought is to use a recursive approach that builds the solution for f(n) by adding pairs of round brackets to f(n-1). This is, of course, the right idea.
Let's consider the solution for n = 3:
(()()) ((())) ()(()) (())() ()()()
How do we get this solution from the solution for n = 2?
(()) ()()
We could insert pairs of brackets into every existing pair of brackets, as well as one pair at the beginning of the string. Other places we could insert brackets, for example at the end of the string, will come out on their own.
So, we have the following:
(()) -> (()()) /* brackets inserted after the first left bracket */
-> ((())) /* brackets inserted after the second left bracket */
-> ()(()) /* brackets inserted at the beginning of the string */
()() -> (())() /* brackets inserted after the first left bracket */
-> ()(()) /* brackets inserted after the second left bracket */
-> ()()() /* brackets inserted at the beginning of the string */
But wait! Some of the pairs are duplicated! The string ()(()) is mentioned twice! If we use this approach, we'll need to check for duplicates before adding a string to the list. An implementation of such a method looks like this:
public static Set generateParens(int remaining) {
Set set = new HashSet();
if (remaining == 0) {
set.add("");
} else {
Set prev = generateParens(remaining - 1);
for (String str : prev) {
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
String s = insertInside(str, i);
if (!set.contains(s)) {
set.add(s);
}
}
}
if (!set.contains("()" + str)) {
set.add("()" + str);
}
}
}
return set;
}
public String insertInside(String str, int leftIndex) {
String left = str.substring(0, leftIndex + 1);
String right = str.substring(leftIndex + 1, str.length();
return left + "()" + right;
}
The algorithm works, but not very efficiently. We spend a lot of time on duplicate strings.
We can avoid the duplication problem by building the string from scratch. This approach involves adding left and right brackets as long as our expression remains valid.
At each recursive call, we get the index of a particular character in the string. Now we need to choose a bracket (left or right). When should we use a left bracket, and when a right one?
Left bracket: as long as we haven't used up all the left brackets, we can insert a left bracket.
Right bracket: we can add a right bracket if doing so won't cause a syntax error. When does a syntax error occur? When there are more right brackets than left ones.
Thus, we need to keep track of the number of opening and closing brackets. If a left bracket can be inserted into the string, we add it and continue the recursion. If there are more left brackets than right ones, we insert a right bracket and continue the recursion.
public void addParen(ArrayList list, int leftRem, int rightRem, char[] str, int count) {
if (leftRem < 0 || rightRem < leftRem) return; // invalid state
if (leftRem == 0 && rightRem == 0) { /* no more left brackets */
String s = String.copyValueOf(str);
list.add(s);
} else {
/* Add a left bracket if any left brackets remain */
if (leftRem > 0) {
str[count] = '(';
addParen(list, leftRem - 1, rightRem, str, count + 1);
}
/* Add a right bracket if the expression stays valid */
if (rightRem > leftRem) {
str[count] = ')';
addParen(list, leftRem, rightRem - 1, str, count + 1);
}
}
}
public ArrayList generateParens(int count) {
char[] str = new char[count * 2];
ArrayList list = new ArrayList();
addParen(list, count, count, str, 0);
return list;
}
Since we add left and right brackets for each index in the string, the indices don't repeat, and each string is guaranteed to be unique.
Analysis taken from a translation of the book by G. Lakeman McDowell and is
продолжение следует...
Часть 1 Algorithm Quizzes
Часть 2 Limitations - Algorithm Quizzes
Часть 3 Solution 1. The size of the linked list is known
Часть 4 Simple solution - Algorithm Quizzes
Часть 5 «Simple» Solution: O(N4) - Algorithm Quizzes
Часть 6 Analysis of problems from the first qualifying round - Algorithm
Comments