Lecture
Our problem-solving section already has 80 questions with detailed solution breakdowns. We decided to collect them all into a single list to make it more convenient for you to prepare and work through them.
There is a singly linked list of structures. In it, random points to some other element of the same list. You need to write a function that copies this list while preserving the structure (i.e. if in the old list the random pointer of the first node pointed to the 4th node, then in the new list the same should hold – the random pointer of the first node points to the 4th node of the new list). O(n), constant extra memory + memory for the elements of the new list.
You cannot allocate memory for all the data in one single chunk, i.e. the list must be a genuine one, scattered across separate pieces, rather than a single block like an array.
Expand answer Implementation option
Here is one possible solution. We traverse the list, create duplicates of the nodes and insert them via next, obtaining 2*N elements, where each odd one refers to its own duplicate. We make a second pass through the list, and in each even node random = random.next. We make a third pass through the list, and in each node next = next.next.
There is another variant by Pashka Dzhioev.
Node *copyList(Node *head)
{
for (Node* cur = head; cur != NULL; cur = cur->next) {
Node* dup = (Node*)malloc(sizeof(Node));
dup->data = cur->data;
dup->next = cur->random;
cur->random = dup;
}
Node* result = head->random;
for (Node* cur = head; cur != NULL; cur = cur->next) {
Node* dup = cur->random;
dup->random = dup->next->random;
}
for (Node* cur = head; cur != NULL; cur = cur->next) {
Node* dup = cur->random;
cur->random = dup->next;
dup->next = cur->next ? cur->next->random : NULL;
}
return result;
}
Implementation option.
Original article.
A classic question from Google interviews. Numbers are written on a board, and you need to answer the question: which number comes next?
Expand answer
Most often, everyone tries – unsuccessfully – to find some pattern in the series of numbers, which seems completely meaningless. But here you need to forget about math. Say these numbers out loud in English (see the picture), and it turns out that they are arranged in order of increasing number of letters contained in their spelling.
Now look even more closely at this series. 10 – is not the only three-letter number. 1, 2, and 6 (one, two, and six) could also occupy this spot. The same can be said about 9, where 0, 4, and 5 (zero, four, and five) would fit. Thus we can conclude that the list includes the largest numbers among those that can be expressed with words of a given number of letters.
So what is the correct answer? Obviously, the number following 66 must have nine letters (not counting a possible hyphen), and it must be the largest of its kind. After a little thought, we can say the answer is 96 (ninety-six). You understand that numbers exceeding 100 do not fit here, since «one hundred» already needs ten letters.
You might wonder why the list does not have hundred, million, or billion in the place of 70, since these also need seven letters to write. Most likely because in proper English one does not say «hundred», but «one hundred», and the same applies to the other two cases.
It would seem that's it, here is the correct answer. Google considers it acceptable, but not the most perfect one. There is a bigger number:
10 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000,
which is written as «one googol» (nine letters).
However, even this is not the best option. The ideal answer: «ten googol», ten googols.
Want to learn the history of this answer? Google it ;)
Puzzle breakdown from the book «Are You Smart Enough to Work at Google?»
Original article.
Suppose you fly from Moscow to Vladivostok, and then back, in perfectly calm weather. Then you make exactly the same flight, but this time, throughout the whole flight, a constant westerly wind blows: a tailwind in one direction, a headwind in the other.
How will the total round-trip flight time change?
View poll results
Expand answer
Usually, after reading the problem, one is tempted to claim that the overall effect of the wind is zero. A headwind will slow movement in one direction, but on the return trip it will blow at your back, letting you cover the distance faster. Overall this is true, but will the flight time be the same?
Imagine a plane flying at a speed of 800 km/h. Suppose that, due to a weather anomaly, a stream of air arose blowing from the west, also at a speed of 800 km/h. On the eastward flight this creates an additional force and you would be able to reach Vladivostok twice as fast. But on the return flight, even if the plane takes off, its speed relative to the ground will be zero. The plane will never return, and the total flight time will be infinite.
If we focus on this limiting case, it is easy to see where the difficulty lies. On a 5-hour flight, a tailwind can save you at most 5 hours, but a headwind can cost an entire eternity. This basic principle holds for any wind. A wind blowing at 400 km/h will shorten the flight time in one direction by about 1.67 hours, but will add 5 hours to the flight in the other direction.
Conclusion: a constantly blowing wind always increases the total round-trip flight time.
A tricky question for subscribers: how would the time change on the same flight if the wind blew from the north, i.e. at a right angle to the direction of flight?
Puzzle breakdown from the book «Are You Smart Enough to Work at Google?»
Original article.
What is wrong with this piece of C++ code?
operator int() const {
return *this;
}
Expand answer
Here is the full code for testing.
class Foo {
public:
operator int() const {
return *this;
}
};
int main() {
Foo foo;
int i = foo;
return 0;
}
It will compile, although some compilers may throw a warning that immediately explains the essence of the error. But when you run it, you will get a stack overflow. The point is that operator int will try to cast the returned value to type int, which is entirely possible to do, since for the current object we have a wonderful operator int that does exactly that. That is, the function calls itself and keeps doing so recursively until the stack overflows.
Original article.
A problem that was popular at one time in Amazon interviews. We localized it, but the meaning remains the same. You need to continue the sequence.
Expand answer
Here is one of the possible answers to this problem. The sequence maps letters of the alphabet to a set of «P» and «C» — certain characteristics. You need to find something of which there are three in the letter A, two in B, and so on. What fits here is the number of straight strokes and curves. Then it is not hard to guess that the letter D corresponds, for example, to «PPPPP», if it is written as shown in the given picture.
The sequence maps letters of the alphabet to a set of «P» and «C» — certain characteristics. You need to find something of which there are three in the letter A, two in B, and so on. What fits here is the number of straight strokes and curves. Then it is not hard to guess that the letter D corresponds, for example, to «PPPPP», if it is written as shown in the given picture.
In the comments to the post with the problem, many interesting solutions could be found, which are listed below.
Markov's algorithms?
Both algorithms operate by traversing the string from the end.
{KK -> T; T -> K}
Answer: TK, KK, T, K
{TT -> TK; KK -> T}
Answer: TK
Binary number system
T — is 1, K — is 0.
Then the pattern in the decimal number system will look like this:
which means the following come next
Answer: T, K.
Cycle
There is a cycle of filling the string with the letter K from the end, and when only a single T remains (obviously, on the left), the entire string is transformed into a string of T letters, but one shorter, i.e.:
we fill in with the letter K from the end
only one T remains, we shorten the length
we shorten again
Answer: TK, T
Bracket sequence
A fun variant: T — let it be, K — end, then we can build an analogy with opening and closing brackets :) No pattern found.
UPD. A variant was proposed to treat the entire sequence of letters as a single bracket sequence:
or
Answer: KKKKK (in various versions: KK, KKK or KKK, KK, and so on)
Non-composite numbers
Let's count the number of «holes in the letters»:
Note that all of these are prime (i.e., non-composite) numbers below 10. Note that there is only one other non-composite number less than 10 — that is one.
Answer: T
Product of 1 and -1
T — is -1. K — is 1. The reverse assignment would, of course, also work. Let's then consider their products:
there are several possible continuations, the author suggested this one:
Answer: TK, KK, T, K
Sum
T = 15, K = 10. Naturally, any other numbers such that T:K = 3:2 would also work. Let's consider the sequence:
the following continuation suggests itself:
Answer: TK, KK, T, K
Russian language to the rescue
A version with a chronology of device releases:
Answer: TS
Morse code
Unfortunately, no one has been able to find the pattern. Maybe you'll manage it?
What's entertaining is that with different solution approaches, the answer TK, KK, T, K often appeared…
Original article.
How would you calculate this without a calculator? Can you give an approximate answer?
Expand answer
Let's give one of the possible lines of reasoning. Any engineer knows that 210 = 1024. Let's consider this to be approximately 1000. Multiply 210 by itself six times and we get 260. This is about 1000 to the sixth power, or 1013, also known as a quintillion. All that remains is to multiply it by 24 (16) to obtain the desired 264. Thus, a very rough but quick answer would be 16 quintillion.
In fact, it's a bit more than that, since 1024 is 2.4% greater than 1000. We use this approximation 6 times, and so the answer should be more than 12% greater. That adds another 2 quintillion. So a more accurate answer would be 18 quintillion.
Exact value: 18,446,744,073,709,551,616
There's one more quick hack. Many people know that the maximum value of a 32-bit unsigned int is something around 4 billion, i.e., 232 ≈ 4x109. All that remains is to multiply this by itself to get about 16–17 quintillion.
Analysis of the puzzle from the book «Are You Smart Enough to Work at Google?»
Original article.
«You've been shrunk to the size of a nickel and thrown into a blender. Your mass is reduced so that your density remains the same as your original density. The blades start moving in 60 seconds. What do you do?»
This is a classic Google puzzle, a good breakdown of which is not so easy to find. We've prepared one for you. There is no absolutely correct answer, but there are some that are clearly better than others.
Expand answer
Let's start by classifying the most popular answers, then talk about the one considered the best among Google interviewers.
Many candidates give one amusing answer: «Since the blender will soon be turned on, it can be assumed that some food will be placed in it, so it might be better for me to put my neck under the blade than to suffocate from the fumes of the slurry that will soon appear in the blender.» If we're talking about frequently encountered serious answers, then the following are the leaders.
First. Lie as close to the bottom as possible, so the blades spin above me.
Second. Stand on the side of the blender where the blades are mounted. There might be a gap the width of a nickel between the wall and the mounting mechanism.
Third. Climb up the blade to the axis of rotation and find a spot where you can maintain balance while the blades are spinning. Hold on tightly. In this case, the resulting centripetal force will be close to zero, which will allow you to hold on.
The first three options give some chance of survival, but what if the blades spin for a long time? Or the design is such that you'll be hit by the blade edge anyway? And really, come to think of it, who threw you into a blender, and why? If it's some hostile creatures preparing a human sauce, then your long-term chances of survival will be very small in any scenario.
Here are the standard answers interviewers give to clarifying questions: «Don't worry about hostile creatures». «No liquid will be added». «There is no lid on the blender». «Assume the blades will spin until you die».
The fourth approach is different — you need to get out. The interviewer will ask how you would do that. One of the most striking answers was: given your very small mass, you could climb up the wall much like a fly does.
The fifth, not the most optimistic, option — use a phone and call or send an sms asking for help. This all depends on whether your phone has also shrunk, whether it can still work with a base station (which remained the same size), and how fast the emergency services would respond (and whether they would respond at all?).
The sixth option: tear your clothes into strips to make a rope out of them and use it to climb out. But is that really feasible in one minute? How would you attach the rope at the top? And even if you succeed, how would you then climb down?
There's also a seventh: use your clothes and your own efforts to somehow block (or even break) the blades or the motor. But problems could arise here too.
None of the listed answers will earn you many points at Google. Interviewers have said that the best answer they've heard was — jump out of the blender.
Really? The question gives an important clue — the word «density». This hint suggests that weight and body volume are important (and you don't need to worry about other «unrealistic aspects»), and that a suitable answer should be based on the simplest laws of physics.
In short: the interviewer wants you to focus on the consequences associated with a change in size. You have probably heard that an ant can lift a weight 50 times greater than its own body weight. This is explained not by the fact that its muscles are better than a human's, but by the fact that the ant is small. The weight of any living creature is proportional to the cube of its height. The strength of the muscles and of the skeleton supporting them depends on their cross-sectional area, which is proportional to the square of the height. If you were shrunk to 1/10 of your height, the strength of your muscles would decrease a hundredfold, but your weight would decrease even more — a thousandfold. All else being equal, small creatures are "stronger."
In the mid-1600s, Giovanni Alfonso Borelli, a contemporary of Galileo, suggested that everything that jumps rises to roughly the same height. Think carefully about this. If you are in good physical shape, you can probably jump about 70 centimeters. This height is no obstacle for other living creatures either: a horse, a rabbit, a frog, a grasshopper, or a flea. There are, of course, variations, but the general rule is exactly this: even the top NBA basketball players can raise their center of gravity by roughly the same height as a flea.
Muscular energy is ultimately determined by chemical processes: glucose and hydrogen circulating in the blood, as well as ATP present in muscle cells. The quantity of any chemical substance is proportional to the volume of your body, that is, if you shrink to 1/n of your size, muscular energy will decrease by a factor of n³.
Fortunately, weight decreases in the same way. Therefore, at the size of a coin, the height of your jump (if we disregard air resistance) will not change at all. The height of a blender is about 30 cm. If you can currently jump over an obstacle of that height, then escaping from a blender will not be a problem for you.
You may ask, how would you not break your bones falling from such a height afterward? The surface area you now occupy will amount to 1/n² compared to your normal self, while your weight will decrease even more, to 1/n³ of the original. The ratio of surface area to weight will increase by a factor of n, so when you land, you will suffer no injuries at all. This explains why any creature the size of a mouse or smaller need not worry and can fall from any height.
Puzzle analysis from the book "Are You Really Smart Enough to Work at Google?"
Original article.
A question about C++. What is the "pure virtual function call" error? In what situation can it be generated? Provide the minimal code that leads to it.
Expand the answer
Those who have encountered this error in a live project and did not know about it beforehand have surely spent quite a lot of time hunting down this bug. Let's break it down step by step.
See the results of the poll "Have you ever caught the pure virtual function call error at least once in your project?".
How does the virtual function mechanism work? It is usually implemented through a "vtbl" (virtual table) — a table of pointers to functions. Every instance of a class containing at least one virtual function has a __vtbl pointer to the vtbl table for its class. In the case of an abstract class and a pure virtual function, the pointer is still present, but it points to the standard handler __pure_virtual_func_called(), which is what leads to this error. But how can it be called, given that a direct attempt would already be caught at the compilation stage?
#include
class Base
{
public:
Base() { init(); }
~Base() {}
virtual void log() = 0;
private:
void init() { log(); }
};
class Derived: public Base
{
public:
Derived() {}
~Derived() {}
virtual void log() { std::cout << "Derived created" << std::endl; }
};
int main(int argc, char* argv[])
{
Derived d;
return 0;
}
Let's examine what happens when an instance of a descendant class object, which contains a vtbl, is instantiated.
Step 1. Construct the top-level base part:
a) Set the __vtbl pointer to the vtbl of the parent class;
b) Construct the instance variables of the base class;
c) Execute the body of the base class constructor.
Step 2. The inherited part(s) (recursively):
a) Change the __vtbl pointer to the vtbl of the descendant class;
b) Construct the variables of the descendant class;
c) Execute the body of the descendant class constructor.
Now let's look at the example in the picture. It is not hard to guess that when an object of class Derived is created, at the step of executing the base class constructor, it will itself still be considered a base class object, and its vtbl will be that of the base class. Compilers usually do not detect this in advance, and the error is only caught at runtime.
Conclusion: avoid calling virtual functions in constructors and destructors, both explicitly and through other functions.
You can read more about this at artima.com or in Scott Meyers's book "Effective C++," item number 9.
Original article.
You have at your disposal 10 thousand servers in a data center with remote management capability, and one day to make a million dollars. What would you do?
Expand the answer
The answer can be given along two lines.
The first is to take the opportunity to make a positive impression on the interviewer — to offer them your favorite, but not yet implemented, business plan. At Microsoft, for example, you would most likely be listened to attentively and politely, and then asked: "Yes, that's interesting, but are you sure you can earn a million dollars already on the first day?".
And here is the Google-style answer: sell the servers, for at least 100 dollars each. This will bring you 1 million dollars, or, more likely, even more — 10 million. Then, if you have some brilliant business plan, use that money as starting capital. This will allow you to keep going long enough to succeed in interesting one of the venture capitalists (who is savvy enough to understand that great ideas do not let you earn a million dollars on the very first day).
Puzzle analysis from the book "Are You Really Smart Enough to Work at Google?"
Original article.
You have an analog clock with a second hand. How many times a day do all three hands of the clock overlap each other?
Expand the answer
This problem is a variant of the classic question asked in Microsoft interviews, when candidates were asked how many times a day the hour and minute hands meet each other. Since this question has now become widely known, interviewers have begun using a variation of it.
Let us first consider the most expected solution, the mathematical one. First, imagine the situation when the hour and minute hands have overlapped. Everyone knows this happens at midnight, then approximately at 1:05, 2:10, 3:15, and so on. In other words, they overlap each other every hour, except for the period from 11:00 to 12:00. At 11:00, the faster minute hand is at 12, while the slower hour hand is at 11:00. They will not meet each other before 12:00 noon, and so there will be no overlap around the 11 o'clock hour.
Thus, 11 overlaps occur during each 12-hour period. They are evenly distributed in time, since both hands move at a constant speed. This means that the intervals between overlaps amount to 12/11 hours. This is equivalent to 1 hour, 5 minutes, and 27 and 3/11 seconds. Therefore, in each 12-hour cycle, overlaps occur at the periods shown in the picture.
Let's return to the second hand. Its overlap with the minute hand is possible when the number of minutes matches the number of seconds. The exact overlap occurs at 00:00:00. In general, the minute and second hands overlap only for a fraction of a second. For example, at 12:37:37 the second hand will be pointing at 37, lagging behind the minute hand, which at that time will be between 37 and 38 and lagging behind the hour hand. A moment later, the minute and second hands will overlap, but the hour hand will not be near them. That is, an overlap of all three hands will not occur.
The second hand will not overlap in any of the variants shown in the picture, except at midnight and noon. This means that the final answer to the question is: twice a day.
Here is the answer favored by Google. The second hand is meant to show short time intervals, not to tell time to the nearest second. If it is not synchronized with the other two hands, that is quite normal. Here, "synchronization" means that at midnight and noon all three hands point exactly to 12. Most analog clocks of any kind do not let you set the second hand precisely. You would need to remove the battery, or, in the case of a mechanical clock, wait until the mainspring runs down, and then, once the second hand has stopped, synchronize the minute and hour hands with each other, after which you would wait until the time shown on the clock arrives in order to put the battery back in or wind the clock.
To do all this, you would have to be a maniac or a stickler for punctuality. But if you don't do all this, the second hand will not show "real" time. It will differ from the exact seconds by some amount within a random interval of up to 60 seconds. Given the random discrepancies, there is no chance that all three hands will ever coincide. This never happens.
Puzzle analysis from the book "Are You Really Smart Enough to Work at Google?"
Original article.
What is the difference between string and String in C#?
Show answer
The answer is actually very simple: string — is simply an alias for System.String, i.e. technically, there is no difference at all. Just as there is no difference between int and System.Int32.
As for coding style, there are a few tips here.
It is generally recommended to use string when you mean an object:
string name = "Jessica";
As opposed to the case when you need to refer specifically to the class, for example:
string msg = String.Format("Hi, {0}!", name);
At least, this is the style that Microsoft follows in its examples.
The picture shows the full list of aliases. The only type that has no alias — is System.IntPtr, it must always be written exactly like that.
However, there is one case where you must use aliases: in explicit type declarations for enums:
public enum Foo : UInt32 {} // Wrong
public enum Bar : uint {} // Correct
We also recommend that you treat types with caution when implementing any API that may be used by clients in other languages. For example, the method ReadInt32 is quite unambiguous, whereas ReadInt — is not. Whoever uses your API may work in a language where int is 16- or 64-bit, which does not match your implementation. .Net Framework developers follow this advice excellently; good examples can be found in the classes BitConverter, BinaryReader, and Convert.
Original article.
You are playing soccer on a desert island and want to flip a coin to decide which team gets the ball. The only coin you have is bent, and therefore introduces a clear bias into the outcome when flipped. How can you nevertheless use such a coin to make a fair decision?
Show answer
There are two options for solving this problem.
The first is to flip the coin many times to determine the percentage of heads and tails. After you establish, for example, that the coin comes up heads in 54.7% of cases (with an established margin of error), you use this fact to work out a wager involving multiple flips, in which the chances of getting the desired outcome will be close to what you want.
The second answer is much simpler: flip the coin twice. Four outcomes are possible: HH, HT, TH, and TT (T — tails, H — heads). Since the coin is "biased" toward one side, the chances of getting HH are not equivalent to the chances of getting TT. On the other hand, the probabilities of getting HT and TH must be equal, regardless of the degree of the coin's "bias." One team bets on HT, the other — on TH. If HH or TT comes up, ignore the results and flip twice more.
Besides being simpler, this scheme is also, unquestionably, fair. The first option, in terms of accuracy, only approximates fifty-fifty odds.
Puzzle analysis from the book "Are You Really Smart Enough to Work at Google?"
Original article.
How many golf balls would fit in a school bus?
For reference: the 1995 U.S. National School Transportation Standards specify the maximum dimensions of a school bus as 40 feet long and 8.5 feet wide. The standard diameter of a golf ball is 1.69 inches, with a tolerance of 0.005 inches.
Show answer
Obviously, this is a Fermi problem, where you are required to make an approximate estimate that is plausible in order of magnitude. Let us give an example of such reasoning.
A school bus, like any other vehicle, must conform in its dimensions to the roadway, i.e. not be much wider than passenger cars. In movies, we've seen that it has seats for four children per row (are such buses used anywhere in Russia? — ed. note), as well as an aisle down the middle. And there is a place where the teacher can stand. Let us assume that the width of the bus is about 2.5 meters, and the height is about 2 meters. Recall that exact figures are not so important; the order of magnitude is what matters. How many rows of seats are there in the bus? Let's say 12. Each row needs about a meter or a bit less; let's take the length as 11 meters. In total, the overall volume will be about 55 cubic meters.
The diameter of a golf ball is approximately 3 cm. Let's take it as ~3.3 cm, so that 30 such balls placed in a row would make up 100 cm. A cubic arrangement of 30x30x30 such balls, i.e. 27,000 balls, would fit into a cubic meter. Multiplying this by 55 gives something around 1.5 million.
Note that many Fermi questions involve spherical sports objects filling buses, pools, airplanes, or stadiums. You can get extra points if you mention Kepler's conjecture. In the late 1500s, Sir Walter Raleigh asked the English mathematician Thomas Harriot to come up with a more efficient way of stacking cannonballs on British navy ships. Harriot told his friend, the astronomer Johannes Kepler, about this problem. Kepler suggested that the densest way of packing spheres was already in use — in the stacking of cannonballs and fruit. The first layer is simply laid side by side in a hexagonal shape, the second in the depressions at the junctions of the balls of the lower layer, and so on. In a large container, with this arrangement, the maximum density would be about 74%. Kepler believed this was the densest possible packing, but he was unable to prove it.
Kepler's conjecture, as it later came to be called, remained a great unsolved problem for several centuries. In 1900, David Hilbert compiled a famous list of 23 unsolved mathematical problems. Some people claimed to have proved this conjecture, but upon inspection all of their solutions turned out to be flawed and among the incorrect ones. This continued until 1998, when Thomas Hales proposed a complex computer-assisted proof that confirmed Kepler was right. Most experts are confident that his result will ultimately prove correct, although its verification has not been completed.
Above we assumed that each golf ball actually sits inside a cube of very thin transparent plastic such that the edges of the cube equal the ball's diameter. This means that the balls occupy about 52% of the space (Pi/6, to be more precise, you can calculate it yourself). If you remove the balls from the imaginary cube, you can fit many more balls into the given volume; this is an empirically verified fact. Physicists have conducted experiments, filling large flasks with steel balls and calculating the packing density. The result ranged from 55% to 64% space utilization. This is a denser arrangement than the one we used, although it still falls short of Kepler's maximum of approximately 74%. Moreover, the spread of results is fairly large.
What should we do? We won't be able to pack the balls with strict ideal precision in reality, that's too absurd even for an answer to an absurd question. A much more realistic goal is the density achieved by periodically shaking or stirring the container. You can achieve it by distributing the balls more evenly with a stick. This raises the density by approximately 20% compared to a cubic lattice arrangement. This would allow the initial estimate to be increased to 1.8 million balls.
Analysis of the puzzle from the book «Are You Smart Enough to Work at Google?»
Original article.
Imagine a spinning disc, such as a DVD. You have black (B) and white (W) paint available. A small sensor is mounted at the edge of the disc, which detects the color beneath it and outputs the result as a signal. How would you color the disc so that it would be possible to determine the direction of rotation from the sensor readings?
Expand answer
Let's give a brief clarification of the problem. The first thing to keep in mind is that you cannot observe the disc itself. For example, you're sitting in an office, while the disc is spinning in a closed laboratory. The only way to determine the direction of rotation is to use the digitized sensor readings, and nothing else.
The sensor records the color of a point at its fixed location at successive moments in time. The readings are presented as a sequence like «BBBWW...». The problem reduces to coloring the disc in such a way that the sequence of readings differs when rotating forward versus backward, that is, the sequence must not be a palindrome.
Palindromes are words or phrases that read the same backward as forward. For example: "level", "rotor", "was it a car or a cat I saw". Coming up with a palindrome is not so easy, whereas it's very simple to give an example of an asymmetric phrase. It might seem just as easy to come up with such a coloring for the disc, but two difficulties arise. First, in the problem statement we are limited to only 2 colors, B and W. Second, we need to get rid of a cyclic palindrome, just as we do with an ordinary one.
For example, you cannot paint half the disc white and the other half black. The readings would be like «WBWBWBWBWB». In the ordinary sense this is not a palindrome, but it is a cyclic palindrome. That is, if you connect the beginning and end of the sequence, you get identical readings when rotating either clockwise or counterclockwise. When observing an infinite stream of readings, you cannot tell in which direction such a disc is rotating.
Not all regular sequences are cyclic palindromes. If we had access to 3 colors: black (B), white (W), and red (R), we could draw 3 sectors of equal area in different colors. Then clockwise the readings would be something like «BBBRRRWWW», and counterclockwise «BBBWWWRRR». In this case they are easily distinguishable. In the first readings, red immediately follows black, while in the second readings, red follows white.
The original problem statement does not allow the use of a third color, but it does allow using a «zebra» coloring instead. One of the three sectors can be painted with a multitude of thin stripes alternating black and white. Then it is easy to notice when the frequent stripes come after the black sector (clockwise) or after the white sector (counterclockwise).
This solution can be improved. After all, you aren't told how fast the disc rotates or at what frequency the sensor is able to register color changes (roughly speaking, the exposure delay). The disc may rotate so fast that the sensor will only register the color of one spot on the disc and skip all the others. This could lead to misinterpretation of the resulting readings.
There is an obvious desire to make the number of stripes smaller and the stripes themselves as wide as possible. In fact, 2 stripes in the «striped sector» are enough, as long as, of course, they are of the opposite color relative to the adjacent sectors.
With this coloring, and assuming it is possible to take 6 readings per revolution, rotating clockwise would give a sequence like «BBWBWW», and counterclockwise this sequence would go in reverse order.
Also of interest is a similar problem, where the disc is already colored in two halves, black and white. It is permitted to install an unlimited number of fixed sensors at the edge of the disc. Question: how many sensors need to be installed to determine the direction of rotation?
All that we can get from a single sensor (in this new problem statement) is the ratio of black to white in the coloring, which is already known (50/50). If we take 2 sensors and place them diametrically opposite each other, we again get nothing useful, since the second sensor will always give the opposite reading.
Instead, we can place 2 sensors close together, for example the first sensor at an arbitrary location, and the second at 10 degrees clockwise from the first. Most of the time both sensors will give the same reading, however, when the colors change, one sensor will notice the change earlier than the other.
The sensor readings might look like this:
Sensor 1: BBWWW
Sensor 2: BBBWW
Such observations mean that the B-W transition is registered by the first sensor earlier than by the second. In this case, the B-W transition, and the disc itself, must be rotating clockwise. If this change is instead registered by the second sensor before the first, then the rotation is counterclockwise.
Analysis taken from the book «Are You Smart Enough to Work at Google?».
Original article.
You have the source code of an application written in C, which crashes after launching. After ten runs in the debugger, you find that the program crashes in a different place each time. The application is single-threaded and uses only the standard C library. What errors could cause the application to crash? How would you check for each one?
Expand answer
The answer largely depends on the type of application being diagnosed. However, we can give some general causes of random failures.
A «random» variable: the application may use some «random» value or a component variable that does not have a specific, exact value. Examples: user input, a random number generated by the program, time of day, etc.
An uninitialized variable: the application may use an uninitialized variable, which in some programming languages can by default take on any value. Thus, the code may execute differently each time.
A memory leak: the program may have exhausted all available resources. Other causes are random in nature and depend on the number of processes running at a given time. This can also include heap overflow or data corruption on the stack.
External causes: the program may depend on another application, machine, or resource. If there are many such dependencies, the program may «crash» at any moment.
To find the problem, you need to study the application as thoroughly as possible. Who runs it? What do the users do? What does the application itself do?
Although the application does not crash in any particular place, the crash itself may be related to specific components or scenarios. For example, the application might remain operational right after launch, and the failure occurs only after a file is loaded. Or the failure occurs within the area of responsibility of low-level components, for example during file I/O.
You can perform selective testing. Close all other applications. Very carefully monitor all available resources. If it's possible to disable parts of the program, do so. Run the program on a different machine and see whether the error occurs. The more we can change, the easier it is to find the problem.
In addition, you can use special tools to check specific situations. For example, to investigate the cause of type-2 errors, you can use debuggers that check for uninitialized variables. Tasks like these let you demonstrate not only your mental abilities, but also your working style. Do you keep jumping from one thing to another and making random guesses? Or do you approach problem-solving logically? Hopefully the latter.
This analysis is taken from Gayle L. McDowell's book «Cracking the Coding Interview» (available in translation).
Original article.
Find the errors in the following code.
unsigned int i;
for (i = 100; i >= 0; --i)
printf("%d\n", i);
Show answer
There are two errors in the code.
The first is that the type unsigned int is used, which only works with values greater than or equal to zero. Therefore the for loop's condition will always be true, and the loop will run forever.
Correct code that prints the values of all numbers from 100 to 1 should use the condition i > 0. If we actually need to print the zero value, then an additional printf statement should be added after the for loop.
unsigned int i;
for (i = 100; i > 0; --i)
printf("%d\n", i);
printf("%d\n", i);
The second error is that %u should be used instead of %d, since we are printing unsigned integer values.
unsigned int i;
for (i = 100; i > 0; --i)
printf("%u\n", i);
Now this code will correctly print the list of numbers from 100 to 1, in descending order.
This analysis is taken from Gayle L. McDowell's book «Cracking the Coding Interview» (available in translation).
Original article.
Explain what this code does.
((n & (n – 1)) == 0)
Show answer
Let's go back to «basics».
What does A & B == 0 mean?
It means that A and B don't have set bits in the same positions. If n & (n - 1) == 0, then n and n - 1 have no common set bits.
What does n - 1 look like (compared to n)?
Try doing the subtraction by hand (in binary or decimal).
What happens?
When you subtract one, look at the least significant bit. A 1 gets replaced with a 0. But if there's a 0 there, you have to borrow from a higher bit. You change every bit from 0 to 1 until you reach a 1. Then you flip that one bit to zero — and you're done.
So we can say that n - 1 will match n in some bits, except that the trailing zeros in n correspond to ones in n - 1, and the last set bit in n becomes a zero in n - 1.
What does n & (n - 1) == 0 mean?
n and n - 1 share no common set bits. Suppose they look like:
abcde must be zero bits, meaning n has the form 000001000. Thus, the value of n is a power of two.
So, our answer: the boolean expression ((n & (n-1)) == 0) is true if n is a power of two or equal to zero.
This analysis is taken from Gayle L. McDowell's book «Cracking the Coding Interview» (available in translation).
Original article.
Given a 100-story building. If an egg is dropped from the Nth floor (or higher), it will break. If it is dropped from any lower floor, it will not break. You have two eggs. Find N using the minimum number of drops.
Show answer
Note that regardless of which floor we drop egg #1 from, when dropping egg #2 we need to use a linear search (from the lowest to the highest floor) between the «breaking» floor and the next highest floor from which the egg survived. For example, if egg #1 survives drops from the 5th through the 10th floor, but breaks when dropped from the 15th floor, then egg #2 will have to be dropped (in the worst case) from the 11th, 12th, 13th, and 14th floors.
Suppose we drop the egg from the 10th floor, then the 20th…
If egg #1 breaks on the first drop (10th floor), then in the worst case we need to make no more than 10 drops.
If egg #1 breaks on the last drop (100th floor), then in the worst case we have 19 drops ahead (floors 10, 20, …, 90, 100, then from 91 to 99).
That's good, but let's pay attention to the worst case. Let's perform load balancing to identify the two most likely cases.
In a well-balanced system, the value Drops(Egg1) + Drops(Egg2) will be constant, regardless of which floor egg #1 breaks on.
Suppose that with each drop, egg #1 «takes» one step (floor), while egg #2's range of possible remaining drops decreases by one.
We need to reduce, each time, the number of drops potentially needed for egg #2 by one. If egg #1 is dropped first from the 20th floor, and then from the 30th floor, egg #2 will need no more than 9 drops. When we drop egg #1 the next time, we should reduce the number of drops for egg #2 to 8. To do this, it's enough to drop egg #1 from the 39th floor.
We know that egg #1 must start at floor X, then descend by X-1 floors, then by X-2 floors, until the number 100 is reached.
We can derive a formula describing our solution: X + (X – 1) + (X – 2) + … + 1 = 100 -> X = 14.
Thus, we first land on the 14th floor, then the 27th, then the 39th. So 14 steps is the worst case.
As with other maximization/minimization problems, the key to the solution is «balancing the worst case».
This analysis is taken from Gayle L. McDowell's book «Cracking the Coding Interview» (available in translation).
Original article.
Continuing with C/C++ problems. What does the keyword volatile mean and in what situations can it be used? Even if you remember the formal definition, try to give an example of a situation where volatile would actually be useful.
Show answer
The keyword volatile tells the compiler that the value of a variable can change from outside the program. This can happen under control of the operating system, hardware, or another thread. Since the value can change, the compiler loads it from memory every time.
A volatile integer variable can be declared as:
int volatile x;
volatile int x;
To declare a pointer to this variable, you need to do the following:
volatile int *x;
int volatile *x;
A volatile pointer to non-volatile data is rarely used, but is allowed:
int *volatile x;
If you want to declare a volatile pointer to a volatile memory area, you need to do the following:
int volatile *volatile x;
Volatile variables are not optimized, which can be useful. Imagine the following function:
int opt = 1;
void Fn(void) {
start:
if (opt == 1)
goto start;
else
break;
}
At first glance it seems the program will loop forever. The compiler might optimize it as follows:
void Fn(void) {
start:
int opt = 1;
if (true)
goto start;
)
Now the loop will definitely become infinite. However, an external operation would allow writing 0 to the variable opt and breaking the loop.
You can prevent this kind of optimization using the volatile keyword, for example by declaring that some external element of the system changes the variable:
volatile int opt = 1;
void Fn(void) {
start:
if (opt == 1)
goto start;
else
break;
}
Volatile variables are used as global variables in multithreaded programs — any thread can change shared variables. We don't want to optimize away these variables.
This analysis is taken from Gayle L. McDowell's book «Cracking the Coding Interview» (available in translation).
Original article.
You have a sorted matrix of size MxN. Propose an algorithm for searching for an arbitrary element in it. By a sorted matrix we mean a matrix whose rows and columns are sorted (see example).
Expand answer
To find the required element, you can use binary search on each row. The algorithm will require O(M log(N)) time, since M columns must be processed, each taking O(log(N)) time. It is also possible to do without complex binary search. We will consider two methods.
Before we start developing the algorithm, let's look at a simple example:
| 15 | 20 | 40 | 85 |
| 20 | 35 | 80 | 95 |
| 30 | 55 | 95 | 105 |
| 40 | 80 | 100 | 120 |
Suppose we are looking for the element 55. How do we find it?
If we look at the first elements of a row and a column, we can begin to search for the location of the desired element. Obviously, 55 cannot be located in a column that begins with a value greater than 55, since the minimum element is always at the top of a column. We also know that 55 cannot be located further to the right, since the value of the first element of each column increases from left to right. Therefore, if we find that the first element of a column is greater than x, we need to move left.
A similar check can be used for rows. If we started with a row whose first element is greater than x, we need to move up.
Similar reasoning can be used when examining the last elements of columns or rows. If the last element of a column or row is less than x, then, to find x, we need to move down (for rows) or right (for columns). This is because the last element is always the maximum.
Let's use all these observations to build a solution:
Let's start with the columns.
We must start with the rightmost column and move left. This means that the first element for comparison will be [c-1], where c is the number of columns. Comparing the first element of a column with x (in our case, 55), it is easy to see that x could be in columns 0, 1, or 2. Let's start with .
This element may not be the last element of a row in the full matrix, but it is the end of the row in the submatrix. And the submatrix is subject to the same conditions. The element has a value of 40, that is, it is less than our element, which means we know we need to move down.
Now the submatrix takes the following form (gray cells are discarded):
| 15 | 20 | 40 | 85 |
| 20 | 35 | 80 | 95 |
| 30 | 55 | 95 | 105 |
| 40 | 80 | 100 | 120 |
We can use our search rules again and again. Notice that we use rules 1 and 4.
The following code implements this algorithm:
public static boolean findElement(int[][] matrix, int elem) {
int row = 0;
int col = matrix .length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == elem) {
return true;
} else if (matrix[row][col] > elem) {
col--;
} else {
row++;
}
}
return false;
}
Another approach to solving the problem is binary search. We will get more complex code, but it will be built on the same rules.
Let's turn once again to our example:
| 15 | 20 | 70 | 85 |
| 20 | 35 | 80 | 95 |
| 30 | 55 | 95 | 105 |
| 40 | 80 | 100 | 120 |
We want to improve the efficiency of the algorithm. Let's ask ourselves: where could the element be located?
We are told that all rows and columns are sorted. This means that element [i][j] is greater than the elements in row i located between columns 0 and j, and the elements in row j between rows 0 and i-1.
In other words:
a[i] <= a[i] <= ... <= a[i][j-i] <= a[i][j]
a [j] <= a [j] <= ... <= a[i-1][j] <= a[i][j]
Look at the matrix: the element located in the dark gray cell is greater than the other highlighted elements.
| 15 | 20 | 70 | 85 |
| 20 | 35 | 80 | 95 |
| 30 | 55 | 95 | 105 |
| 40 | 80 | 100 | 120 |
The elements in the white cells are ordered. Each of them is greater than both the element to the left and the element above it. Thus, the highlighted element is greater than all the elements located in the square.
| 15 | 20 | 70 | 85 |
| 20 | 35 | 80 | 95 |
| 30 | 55 | 95 | 105 |
| 40 | 80 | 100 | 120 |
We can formulate a rule: the bottom right corner of any rectangle highlighted in the matrix will contain the largest element.
Similarly, the top left corner will always be the smallest. The colors in the diagram below reflect information about the ordering of the elements (light gray < white < dark gray):
| 15 | 20 | 70 | 85 |
| 20 | 35 | 80 | 95 |
| 30 | 55 | 95 | 105 |
| 40 | 80 | 100 | 120 |
Let's return to the original problem. Suppose we need to find the element 85. If we look at the diagonal, we see the elements 35 and 95. What information about the location of the element 85 can we extract from this?
| 15 | 20 | 70 | 85 |
| 20 | 35 | 80 | 95 |
| 30 | 55 | 95 | 105 |
| 40 | 80 | 100 | 120 |
85 cannot be located in the dark gray area, since the element 95 is located in the top left corner and is the smallest element in that square.
85 cannot belong to the light gray area, since the element 35 is located in the bottom right
продолжение следует...
Часть 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