Lecture
Это продолжение увлекательной статьи про .
...
given condition. The only thing you can control is the time of movement. To stay as dry as possible, you should run as fast as you can. Running will result in you getting less wet, of course, provided you don't have an umbrella with you.
If you had an umbrella, and it were the size of a city block, and if you were able to hold it, then it wouldn't matter at all whether you crawled like a turtle or dashed like a sprinter. Either way, with such an umbrella you'd stay dry, like a slice of bread in a toaster.
Most umbrellas are large enough that a person, if standing under ordinary vertically falling rain, doesn't get wet. But, as you know, in practice you'll still get a little wet anyway.
Umbrellas create obstacles for the rain and form a zone where there are no raindrops. With vertically falling drops and a round umbrella, the protective zone from the rain resembles a cylinder. If the rain falls at an angle, the protective zone becomes a slanted cylinder. Therefore, as every experienced "user" knows, it's best to tilt the umbrella in the direction the rain is falling from. This will cause the protective zone to become a proper cylinder again, though tilted at some angle relative to vertical.
A standing human body does not fit into a tilted cylinder. If the rain is also accompanied by a strong wind that directs the drops at you horizontally, you will have to hold the umbrella horizontally, and an umbrella three feet in diameter (about 90 cm) will only protect half of your body. The other half will get wet.
From wind, as from motion, you will get wetter. A professional knows that the umbrella should be tilted forward in the direction of movement in order to provide maximum protection. In fact, even if the umbrella is in the optimal position, wind and the person's motion will still negate all of it. Running at ten miles per hour with no wind in vertical rain requires the same tilt as standing in the rain with a ten-mile-per-hour wind. In either case, in addition to their normal falling speed, the raindrops will also act on you horizontally, at a speed of 10 miles per hour.
In vertical rain, the best option for you is to walk slowly. You won't have to tilt the umbrella much, and you will find yourself in a «dry pocket». Ideally, you should walk at a speed such that your legs do not end up outside this zone. Then you will stay dry.
Of course, in real life everything is much more complicated. There are gusts of wind, splashes from drops hitting the pavement, and drops running down the umbrella itself. Rain that falls on the umbrella does not evaporate anywhere. The drops run down and fall off — along the same cylindrical surface that your umbrella creates. And it is precisely there, at the edges of the umbrella, that there is more rain than anywhere else. This means that any part of your body that sticks out beyond this protective edge will get wet faster than if you were walking without an umbrella at all.
With sharp gusts of wind, the advantages of moving slowly disappear. You will have to tilt the umbrella so that the lower half of your body is left outside its cover. So no matter what, you will definitely get half wet.
However, forget all these intricate calculations and remember your mother's advice: walk if you have an umbrella, and run if you don't.
You can also watch the «MythBusters» investigation starting at minute 15.
Discussion based on the book «Are You Really Smart Enough to Work at Google?».
Original article.
Imagine that there is a square matrix, each pixel of which can be black or white. Design an algorithm to find the maximum subsquare whose sides are all black.
Discussion of two solutions with complexity O(N^4) and O(N^3). Can you find other approaches?
Expand answer
This problem, too, can be solved in two ways: a simple one and a complex one. Let's look at both solutions.
We know that the side length of the largest square equals N, and there is only one square of size N*N. We can check whether that square is the one we're looking for, and report if it is.
If a square of size N*N is not found, we can try to find the next square: (N-1)*(N-1). By checking all squares of this size, we return the first square found. Then the same operations are repeated for N-2, N-3, and so on. Since each time we decrease the size of the square, the first square found will be the largest.
Our code works like this:
Subsquare findSquare(int[][] matrix) {
for (int i = matrix.length; i >= 1; i--) {
Subsquare square = findSquareWithSize(matrix, i);
if (square != null) return square;
}
return null;
}
Subsquare findSquareWithSize(int[][] matrix, int squareSize) {
/* On a side of size N there are (N - sz + 1) squares
* of length sz. */
int count = matrix.length - squareSize + 1;
/* Iterate over all squares with side squareSize. */
for (int row = 0; row < count; row++) {
for (int col = 0; col < count; col++) {
if (isSquare(matrix, row, col, squareSize)) {
return new Subsquare(row, col, squareSize);
}
}
}
return null;
}
boolean isSquare(int[][] matrix, int row, int col, int size) {
// Check the top and bottom sides
for (int j = 0; j < size; j++){
if (matrix[row][col+j] == 1) {
return false;
}
if (matrix[row+size-l][col+j] == 1){
return false;
}
}
// Check the left and right sides
for (int 1=1; i < size - 1; i++){
if (matrix[row+i][col] == 1){
return false;
}
if (matrix[row+i][col+size-1] == 1){
return false;
}
}
return true;
}
The sluggishness of the «simple» solution is due to the fact that we must perform O(N) operations for each check of a candidate square. By doing preprocessing, we can reduce the time of isSquare to O(1), so the algorithm will then require O(N3) time.
isSquare tries to find out whether squareSize cells located to the right (and below) certain cells are zero. And this information can be known in advance.
We will perform the check from right to left and from bottom to top. For each cell we need to calculate:
if A[r][c] is white, A[r][c].zerosRight = 0 and A[r][c].zerosBelow = 0
else A[r][c].zerosRight = A[r][c + 1].zerosRight + 1
A[r][c].zerosBelow = A[r + 1][c].zerosBelow + 1
Look at the values for a certain matrix.
NOW, INSTEAD OF ITERATING OVER O(N) ELEMENTS, THE ISSQUARE METHOD CHECKS THE CORNERS FOR ZEROSRIGHT AND ZEROSBELOW.
Below is the code for this algorithm. Note that findSquare and findSquare — WithSize are the same, except for the call to processMatrix and the subsequent work with the new data type:
public class SquareCell {
public int zerosRight = 0;
public int zerosBelow = 0;
/* declarations, getters and setters */
}
Subsquare findSquare(int[][] matrix) {
SquareCell[][] processed = processSquare(matrix);
for (int i = matrix.length; i >= 1; i--) {
Subsquare square = findSquareWithSize(processed, i);
if (square != null) return square;
}
return null;
}
Subsquare findSquareWithSize(SquareCell[][] processed,
int squareSize) {
/* equivalent to the first algorithm */
}
boolean isSquare(SquareCell[][] matrix, int row, int col,
int size) {
SquareCell topLeft = matrix[row][col];
SquareCell topRight = matrix[row][col + size - 1];
SquareCell bottomRight = matrix[row + size - l][col];
if (topLeft.zerosRight < size) { // Check the top side
return false;
}
if (topLeft.zerosBelow < size) { // Check the left side
return false;
}
if (topRight.zerosBelow < size) { // Check the right side
return false;
}
if (bottomRight.zerosRight < size) { // Check the bottom side
return false;
}
return true;
}
SquareCellf][] processSquare(int[][] matrix) {
SquareCell[][] processed =
new SquareCell[matrix.length][matrix.length];
for (int r = matrix.length - 1; r >= 0; r--) {
for (int c = matrix.length - 1; c >= 0; c--) {
int rightZeros = 0;
int belowZeros = 0;
// only needs processing if the cell is black
if (matrix[r][c] == 0) {
rightZeros++;
belowZeros++;
// next column in this row
if (c + 1 < matrix.length) {
SquareCell previous = processed[r][c + 1];
rightZeros += previous.zerosRight;
}
if (r + 1 < matrix.length) {
SquareCell previous = processed[r + 1][c];
belowZeros += previous.zerosBelow;
}
}
processed[r][c] = new SquareCell(rightZeros, belowZeros);
}
}
return processed;
}
Discussion based on the book «Cracking the Coding Interview: How to Get a Job at Google, Microsoft, or Another Leading IT Company».
Original article.
Suppose only unsociable patrons frequent a certain bar. There are 25 seats along the bar counter. Whenever a new patron comes in, he always sits at the seat farthest, as much as possible, from the other guests. No one will sit next to anyone else: if a patron comes in and sees that there are no "free" seats, he immediately turns around and leaves the bar. The bartender, naturally, wants as many customers as possible to be seated at the counter. If he's allowed to seat the first patron at any seat, where would it be most advantageous for him to seat that person, from the bartender's point of view?
Expand the answer
The densest possible arrangement is an alternation of customers and empty seats, in which both end seats are occupied. This would allow the remaining patrons to sit in all the odd-numbered seats, including the end seats numbered 1 and 25, and leave all even-numbered seats empty. In this case, 13 customers could fit at the counter.
However, this arrangement doesn't always work. Suppose the first customer sits down at seat No. 1. The next "hermit" chooses seat No. 25, since it's located at the greatest possible distance from No. 1. The third customer will have to sit in the middle of the bar counter, at seat No. 13. The next two patrons will fill the gaps and sit down at seats No. 7 and No. 19, respectively. So far so good.
Eventually, someone will want to sit between the customers occupying seats No. 1 and No. 7. He'll choose No. 4, since this gives him two empty seats between himself and his nearest neighbors. But none of the following guests will sit next to him. The rest of the bar counter will fill up the same way, and so there will be gaps of two seats between two patrons, which makes this arrangement the least efficient possible (with it, only nine customers end up at the counter instead of the optimal number — 13).
Many problems, including this one, are best solved by working backward from the end to the beginning. We know what the desired seating plan should look like, and we need to determine how to arrive at it.
As shown in the diagram, this arrangement is characterized by a great deal of symmetry, reminiscent of crystal growth. Small portions of the bar counter fill up in exactly this way. Pay attention to the part of the counter with the first numbers. We need patrons to occupy seats No. 1 and No. 5, since this will allow another customer to sit at No. 3.
How do you get a person who comes into the bar to sit at seat No. 5? Answer: you need customers to already be sitting at seats No. 1 and No. 9. Then the fifth seat will be in the middle between them, since it's at the maximum distance from both No. 1 and No. 9.
How do you get a person to sit at No. 9? For this, the previous customers must occupy No. 1 and No. 17. And how do you make a patron go to No. 17? Well, let's say the bar counter isn't long enough to seat customers at No. 1 and No. 33. So the bartender will simply have to ask the first patron to sit at No. 17. There's the answer.
Let's rewind the tape. The first customer sits down at No. 17 (top row in the diagram). The second patron sits as far from him as possible, at seat No. 1.
The third patron has two choices: seat No. 9 or No. 25. Both are at a distance of seven empty seats from any other customer. Given the reclusive nature of this bar's patrons, the third customer will most likely choose seat No. 25, since in that case he'll have only one neighbor at a distance, rather than two, between whom he'd have to sit, and so No. 9 is left for the fourth customer.
The next three patrons will choose seats between the first four and will occupy, respectively, seats No. 5, No. 13, and No. 21. At each of these seats, three empty seats will separate them from their nearest neighbor.
And finally, the next six patrons will occupy the six remaining seats that have no nearest neighbors, namely: No. 3, No. 7, No. 11, No. 15, No. 19, and No. 23.
The bartender could equally well have asked the first patron to sit at seat No. 9, in which case the diagram would become a mirror image of the one presented above.
This analysis is based on the book "Are You Smart Enough to Work at Google?".
Original article.
Describe how a single one-dimensional array can be used to implement three stacks.
Expand the answer
Like many problems, it all depends on how we plan to maintain these stacks. If we need to allocate a fixed amount of space for each stack, we can do just that. But in that case, one of the stacks might run out of space while the others remain practically empty.
Of course, we could use a more flexible space-division scheme, but that makes the task considerably more complex.
We can divide the array into three equal parts and allow the stacks to grow within a limited space. Note that below we will describe the boundaries of the ranges using brackets: square brackets [] mean that the boundary values are included in the range, while round brackets mean the values are not included.
Stack 1: [0, n/3).
Stack 2: [n/3, 2n/3).
Stack 3: [2n/3, n].
The code for this solution is given below:
int stackSize = 100;
int[] buffer = new int [stackSize * 3];
int[] stackPointer = {0,0,0}; //pointers for tracking the top elements
void push(int stackNum, int value) throws Exception {
/* Check whether there is space */
if (stackPointer[stackNum] >= stackSize){
throw new Exception("Not enough space.");
}
/* find the index of the top element of the array + 1,
* and increment the stack pointer */
int index = stackNum * stackSize + stakPointer[stackNum] + 1;
stackPointer[stackNum]++;
buffer[index] = valuse;
}
int pop(int stackNum) throws Exception {
if (stackPointer[stackNum] == 0) {
throw new Exception("Attempt to use an empty stack");
}
int index = stackNum * stackSize + stackPointer[stackNum];
stackPointer[stackNum]--;
int value = buffer[index];
buffer[index] = 0;
return value;
}
int peek(int stackNum) {
int index = stackNum * stackSize + stackPointer[stackNum];
return buffer[index];
}
boolean isEmpty(int stackNum) {
return stackPointer[stackNum] ==0;
}
If we have additional information about the purpose of the stacks, we can modify the algorithm. For example, if stack 1 is expected to have more elements than stack 2, we can reallocate space in favor of stack 1.
The second approach is flexible allocation of space for stack blocks. When one of the stacks stops fitting in its original space, we increase the amount of resource needed and shift elements as necessary.
In addition, we can build the array so that the last stack begins at the end of the array and ends at the beginning — "wrapping" the array into a ring.
However, in an interview you won't be made to write such complex code, so we'll limit ourselves to a simplified version (pseudocode).
/* StackData - a simple class that stores a set of data about each stack
* The class does not contain the stack elements! */
public class stackData{
public int start;
public int pointer;
public int size = 0;
public int capacity;
public stackData(int _start, int _capacity){
start = _start;
pointer = _start -1;
capacity = _capacity;
}
public boolean isWithinStack(int index, int total_size){
if(start + capacity <= total_size) { // normal size
if(start <= index && index <= start + capacity) {
return true;
} else {
return false;
}
} else { // the stack wraps around the beginning of the array
int shifted_index = index + total_size;
if (start <= shifted_index &&
shifted_index <= start + capacity){
return true;
} else {
return false;
}
}
}
}
public class Question B {
static int number_of_stack = 3;
static int default_size = 4;
static int total_size = default_size * number_of_stack;
static StackData [] stacks = {new StackData(0, default_size),
new StackData(default_size, default_size),
new StackData(default_size * 2, default_size)};
static int [] buffer = new int [total_size];
public static void main(String [] args) throw Exception {
push(0,10);
push(1,20);
push(2,30);
int v = pop(0);
...
}
public static int nextElement(int index) {
if (index + 1 == total_size) return 0;
else return index + 1;
}
public static int previousElement(int index) {
if (index ==0) return total_size - 1;
else return index - 1;
}
public static void shift(int stackNum) {
StackData stack = stacks[stackNum];
if (stack.size >= stack.capacity) {
int nextStack = (stackNum + 1) % number_of_stacks;
shift(nextStack); // perform the shift
stack.capacity++;
}
//Shift the elements in reverse order
for (int i = (stack.start + stack.capacity -1) % total_size;
stack.isWithinStack(i, total_size);
i=previousElement(i)) {
buffer[i] = buffer[previousElement(i)];
}
buffer[stack.start] = 0;
stack.start = nextElement(stack.start); //move the start of the stack
stack.pointer = nextElement(stack.pointer); // move the pointer
stack.capacity--; // restore the original size
}
/* Expand the stack, shift the remaining stacks */
public static void expand(int stackNum) {
shift((stackNum + 1) % number_of_stacks);
stacks[stackNum].capacity++;
}
public static void push(int stackNum, int value)
throws Exception {
StackData stack = stacks[stackNum];
/* Check whether there is room */
if (stack.size >= stack.capacity) {
if (numberOfElements() >= total_size) { // Totally full
throw new Exception("Not enough space.");
} else { // Need to perform a shift
expand(stackNum);
}
}
/* Find the index of the top element in the array +1,
* and increment the stack pointer */
stack.size++;
stack.pointer = nextElement(stack.pointer);
buffer[stack.pointer] = value;
}
public static int pop(int stackNum) throws Exception{
StackData stack = stacks[stackNum];
if (stack.size == 0) {
throw new Exception("Attempt to use an empty stack");
}
int value = buffer[stack.pointer];
buffer[stack.pointer] = 0;
stack.pointer = previousElement(stack.pointer);
stack.size--;
return value;
}
public static int peek(int stackNum) {
StackData stack = stacks[stackNum];
return buffer[stack.pointer];
}
public static boolean isEmpty(int stackNum) {
StackData stack = stacks[stackNum];
return stack.size == 0;
}
}
In problems like this, it's important to focus on writing clean, maintainable code. You should use additional classes, as we did with StackData, and blocks of code should be broken out into separate methods. This advice is useful not only for passing an interview, but can also be applied to real-world tasks.
Based on the book «Cracking the Coding Interview: How to Get a Job at Google, Microsoft, or Another Leading IT Company».
Original article.
You have an unlimited number of coins in denominations of 25, 10, 5, and 1 cent. Write code that determines the number of ways to represent n cents.
Expand answer
This is a recursive problem, so let's figure out how to calculate makeChange(n), based on previous solutions (subproblems). Let n = 100. We want to compute the number of ways to represent 100 cents.
We know that to get 100 cents we can use 0, 1, 2, 3, or 4 quarters (25 cents):
makeChange(100)= makeChange(100, using 0 quarters) + makeChange(100, using 1 quarter) + makeChange(100, using 2 quarters) + makeChange(100, using 3 quarters) + makeChange(100, using 4 quarters)
Moving on: let's try to simplify some of these problems. For example, makeChange(100, using 1 quarter) = makeChange(75, using 0 quarters). This is because if we must use one quarter to represent 100 cents, the remaining options correspond to the various representations of 75 cents.
We can apply this same logic to makeChange(100, using 2 quarters), makeChange(100, using 3 quarters), and makeChange(100, using 4 quarters).
The earlier expression can be reduced to the following:
makeChange(100)= makeChange(100, using 0 quarters) + makeChange(75, using 0 quarters) + makeChange(50, using 0 quarters) + makeChange(25, using 0 quarters) + 1
Note that the last expression — makeChange(100, using 4 quarters) — equals 1.
What next? Now that we've used up all the quarters, we can use the next largest coin — the 10-cent coin.
The approach used for quarters will also work for 10-cent coins. We'll apply it to the four parts of the expression above. So, for the first part:
makeChange(100, using 0 quarters) = makeChange(100, using 0 quarters, 0 dimes) + makeChange(100, using 0 quarters, 1 dime) + makeChange(100, using 0 quarters, 2 dimes) + … makeChange(100, using 0 quarters, 10 dimes) makeChange(75, using 0 quarters) = makeChange(75, using 0 quarters, 0 dimes) + makeChange(75, using 0 quarters, 1 dime) + makeChange(75, using 0 quarters, 2 dimes) + … makeChange(75, using 0 quarters, 7 dimes) makeChange(50, using 0 quarters) = makeChange(50, using 0 quarters, 0 dimes) + makeChange(50, using 0 quarters, 1 dime) + makeChange(50, using 0 quarters, 2 dimes) + … makeChange(50, using 0 quarters, 5 dimes) makeChange(25, using 0 quarters) = makeChange(25, using 0 quarters, 0 dimes) + makeChange(25, using 0 quarters, 1 dime) + makeChange(25, using 0 quarters, 2 dimes)
After that we can move on to the 5-cent and 1-cent coins. As a result we get a tree-shaped recursive structure, where each call expands into four or more calls.
The base case for our recursion is a fully reduced (simplified) expression. For example, makeChange(50, using 0 quarters, 5 dimes) fully reduces to 1, since 5 dimes give exactly 50 cents.
The recursive algorithm will look roughly like this:
public int makeChange(int n, int denom) {
int next_denom = 0;
switch (denom) {
case 25:
next_denom =10;
break;
case 10:
next_denom =5;
break;
case 5:
next_denom =1;
break;
case 1:
return 1;
}
int ways = 0;
for (int I = 0; I * denom<= n; i++){
ways += makeChange (n – 1 * denom , next_denom);
}
return ways;
}
System.out.writeln(makeChange(100, 25));
Although we implemented the code based on coins used in the USA, it can easily be adapted for any other currency.
Analysis from the book «Cracking the Coding Interview: How to Get a Job at Google, Microsoft, or Another Leading IT Company».
Original article.
Write code to find the minimum distance (expressed as a number of words) between any two words in a file. Order doesn't matter.
Would linear time be sufficient?
How much memory would be needed for the solution?
Expand answer
Let's assume that the order in which word1 and word2 appear does not matter. This question needs to be clarified with the interviewer. If the order of the words matters, the code below will need to be modified.
To solve this problem, it is enough to read the file only once. As we do, we'll store information about where word1 or word2 last occurred in lastPosWord1 and lastPosWord2, and update the value of min as needed, then update lastPosWord1. We do the same for word2. By the end of the algorithm's run, we'll have the correct value of min (the minimum distance).
The code below illustrates this algorithm:
public int shortest(String[] words, String word1, String word2) {
int min = Integer.MAX_VALUE;
int lastPosWord1 = -1;
int lastPosWord2 = -1;
for (int i = 0; i < words.lenght; i++) {
String currentWord = words[i];
if (currentWord.equals(word1)) {
lastPosWord1 = i;
// Comment out the following 3 lines if word order
// matters
int distance = lastPosWord1 - lastPosWord2;
if (lastPosWord2 >= 0 && min > distance) {
min = distance;
}
} else if (currentWord.equals(word2)) {
lastPosWord2 = i;
int distance = lastPosWord2 - lastPosWord1;
if (lastPosWord >= 0 && min > distance) {
min = distance;
}
}
}
return min;
}
If we need to do the same work for other pairs of words, we can create a hash table linking words to their positions in the file. The solution would then be the minimum (arithmetic) difference between values from the lists listA and listB.
There are several ways to compute the minimum difference between the values from listA and listB. Let's consider the lists:
listA: {1, 2, 9, 15, 25}
listB: {4, 10, 19}
We can merge the lists into a single sorted list, while linking each value to its original list. This is done by «wrapping» each value in a class that has two instance variables: data (to store the actual value) and listNumber.
list: {1a, 2a, 4b, 9a, 10b, 15a, 19b, 20a}
Calculating the minimum distance then becomes finding the minimum distance between two consecutive numbers that have different list tags. In this case, the solution is 1 (the distance between 9a and 10b).
Analysis from the book «Cracking the Coding Interview: How to Get a Job at Google, Microsoft, or Another Leading IT Company».
Original article.
Simulate using a seven-sided die, given that you only have a five-sided die available.
In other words, how do you get a random number in the range from 1 to 7 using a random integer generator that produces numbers from 1 to 5?
Expand answer
There are several simple ideas, but, alas, they may turn out to be unfair. One of them is to roll the die twice and add up the numbers rolled. This gives a result in the range from 2 to 10. Seems fair? No. Everyone knows that not all sums of two rolls are equally likely. A sum in the middle of the distribution (7) is more likely. The same is true for a five-sided die.
Another idea is to roll the die twice and multiply the resulting values, or otherwise derive a larger number from them. Then divide it by 7 and take only the remainder. The remainder will be in the range from 0 to 6. We don't need 0, so we'll treat it as 7. This approach would give us a «random» number in the range from 1 to 7.
I put the word «random» in quotes because the mathematician John von Neumann wrote that anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. Although such an approach may be quite acceptable for some purposes, the result is not actually fully random, and so this answer is not highly valued at Google or Amazon. On the internet, however, numbers really need to be random, since otherwise hackers would take advantage of that. In a casino, for example.
To get a truly random outcome, let each of seven players roll the five-sided die once. The player who rolls the higher number wins. If several players roll the highest value, they roll again (as many times as needed). The only downside of this approach is that the die might need to be rolled many times. Even without any ties, seven rolls would be needed.
There's a better answer. Think more carefully about the numbers. The numbers 1 through 7 can be represented as three bits, that is, binary numbers from 001 to 111. Can you generate three random bits using a five-sided die?
Naturally, each roll will give you one digit of a three-bit number. If it lands on 2 or 4, call the result a zero; if 1 or 3, a one; if 5, roll again. Keep rolling as many times as necessary if a five comes up.
Repeating this procedure three times generates a number in the range from 000 to 111. Convert it back to decimal, and then the person who rolled the higher number wins (for example, 101 means lottery ticket No. 5 won). If 000 comes up, roll again.
This requires only three die rolls if there are no repeats. On average, this approach requires a little more than four rolls.
Analysis of the puzzle from the book «Are You Smart Enough to Work at Google?».
Original article.
Write code that partitions a linked list around a given value, so that all nodes smaller than the value come before nodes greater than or equal to it.
If we were working with an array, there would be many difficulties related to shifting elements.
Expand answer
With a linked list, the task is much simpler. Instead of shifting and swapping elements, we can create two separate linked lists: one for elements smaller than x, and the second for elements greater than or equal to x.
We traverse the list, placing elements into the before and after lists. Once the end of the original linked list is reached, we can merge the resulting lists.
The code below implements this approach:
/* We pass the head of the list to be split, and the value x, around
* which the list will be split */
public LinkedListNode partition(LinkedListNode node, int x) {
LinkedListNode beforeStart = null;
LinkedListNode beforeEnd = null;
LinkedListNode afterStart = null;
LinkedListNode afterEnd = null;
/* Splitting the list */
while (node != null) {
LinkedListNode next = node.next;
node.next = null;
if (node.data < x) {
/* Insert the node at the end of the before list*/
if (beforeStart == null) {
beforeStart = node;
beforeEnd = beforeStart;
} else {
beforeEnd.next = node;
beforeEnd = node;
}
} else {
/* Insert the node at the end of the after list */
if (afterStart == null) {
afterStart = node;
afterEnd = afterStart;
} else {
afterEnd.next = node;
afterEnd = node;
}
}
node = next;
}
if (beforeStart == null) {
return afterStart;
}
/* Merge the before and after lists */
beforeEnd.next = afterStart;
return return beforeStart;
}
If you don't want to use four variables to keep track of just two linked lists, you can get rid of some of them at the cost of a slight loss of efficiency. But the «damage» won't be very great — the time complexity of the algorithm will remain the same, while the code will become shorter and cleaner.
Alternative solution: instead of inserting nodes at the end of the before and after lists, you can insert elements at the beginning of the list.
public LinkedListNode partition(LinkedListNode node, int x) {
LinkedListNode beforeStart = null;
LinkedListNode afterStart = null;
/ Split the list */
while (node != null) {
LinkedListNode next = node.next;
if (node.data < x) {
/* Insert the node at the start of the before list */
node.next = beforeStart;
beforeStart = node;
} else {
/* Insert the node at the start of the after list */
node.next = afterStart;
afterStart = node;
}
node = next;
}
/* Merge the lists */
if (beforeStart == null) {
return afterStart;
}
/* Find the end of the before list and join the lists*/
LinkedListNode head = beforeStart;
while (beforeStart.next != null) {
beforeStart = beforeStart.next;
}
beforeStart.next = afterStart; return head;
return head;
}
Pay attention to null values. In line 7, an additional check has been added. The next node needs to be saved in a temporary variable so as to remember which node will come next.
Analysis of the problem from the book «Cracking the Coding Interview: Getting a Job at Google, Microsoft or Another Leading IT Company».
Original article.
Write a method that generates a random sequence of m integers from an array of size n. All elements are selected with equal probability.
The first thing that comes to mind is to choose random elements from the array and place them in a new array. But what if we choose the same element twice?
Expand answer
Ideally, we need to shrink the array so as to discard the selected element. But shrinking an array is a fairly costly operation, since it requires shifting elements.
Instead of shrinking (shifting) the array, we can place the element (swap elements) at the beginning of the array and «remember» that the array now starts from element j. If the subset element becomes array[k], then we must replace array[k] with the first element in the array. When we move on to the subset element, we imply that the array element is «dead», and we choose a random element from the range 1 to array.size(). Now subset = array[y] and array[y] = subset. Elements 0 and 1 are «dead», and subset is chosen in the range from array to array[array.size()], and so on.
/* Random number between lower and higher, inclusive */
public static int rand(int lower, int higher) {
return lower + (int)(Math.random() * (higher - lower + 1));
}
/* Select M elements from the original array. Clone the original
* array so as not to destroy the input */
public static int[] pickMRandomly(int[] original, int m) {
int[] subset = new int[m];
int[] array = original.clone();
for(int j = 0; j < m; j++) {
int index = rand(j, array.length - 1);
subset[j] = array[index];
array[index] = array[j]; //array[j] is now "dead"
}
return subset;
}
Analysis of the problem from the book «Cracking the Coding Interview: Getting a Job at Google, Microsoft or Another Leading IT Company».
Original article.
Imagine a robot located in the top-left corner of a grid with coordinates (X, Y). The robot can move in two directions: right and down. How many routes are there from point (0, 0) to point (X, Y)?
Additionally, suppose that there are areas on the grid that the robot cannot cross. Design an algorithm to build a route from the top-left to the bottom-right corner.
Expand answer
We need to count the number of ways to cover the distance with X steps to the right and Y steps down (X + Y steps).
To create a path, we take X steps to the right so that the total number of moves remains fixed (X + Y). Thus, the number of paths must coincide with the number of ways to choose X elements out of X + Y, that is, the binomial coefficient. The binomial coefficient n choose r has the form:
For our problem, the expression will be as follows:
Even if you are unfamiliar with combinatorics, you can still find the solution to this problem yourself.
Let's represent a path as a string of length X + Y, consisting of X characters R and Y characters D. We know that from X + Y non-repeating characters we could form (X + Y)! strings. But in our case, X characters R and Y characters D are used. The R characters can be arranged in X! ways (the same can be done with the D characters). Thus, we need to remove the extra strings X! and Y!. In the end, we get the same expression:
Find the route (there are places on the map that the robot cannot pass through).
If we draw our map, the only way to reach square (X, Y) is to be in one of the adjacent squares: (X-1, Y) or (X, Y-1). Therefore, we need to find a path to either of these squares ((X-1, Y) or (X, Y-1)).
How can this be done? To find a path to square (X-1, Y) or (X, Y-1), we must be in one of the adjacent cells. That is, we need to find a path to a square adjacent to (X-1, Y) ((X-2, Y) and (X-1, Y-1)) or to (X, Y-1) ((X-1, Y-1) and (X, Y-2)). Notice that in our reasoning the point (X-1, Y-1) is mentioned twice; we'll come back to this fact.
Let's try to find the path from the starting square by moving in the reverse direction — starting from the last cell and trying to find a path to each adjacent square. Below is the recursive code implementing our algorithm.
public boolean getPath(int x, int y, ArrayList path) {
Point p = new Point(x, y);
path.add(p);
if (x == 0 && y == 0) {
return true; // path found
}
bolean success = false;
if (x >= 1 && isFree(x – 1, y)) { // Try to go right
success = getpath(x – 1, y, path); // Free! We can go right
}
if ( !success && y >= 1 && isFree(x, y - 1)) { // Try to go down
success = getPath(x, y – 1, path); // Free! We can go down
}
if (!success) {
path.remove(p); // Wrong path! Stop moving along this route
}
return success;
}
Remember that routes get duplicated? To find all paths to (X, Y), we find all paths to (X-1, Y) and (X, Y-1). Then we look at the coordinates of the adjacent squares: (X-2, Y), (X-1, Y-1), (X-1, Y-1), and (X, Y-2). Square (X-1, Y-1) appears twice. Let's remember the visited squares so as not to waste time on them.
This can be done using the following dynamic programming algorithm:
public Boolean getPath(int x, int y, ArrayList path,
Hashtable cache){
Point p = new Point(x, y);
if (cache.containsKey(p)) { // We have already visited this cell
return cache.get(p);
}
path.add(p);
if (x == 0 && y == 0) {
return true; // Path found
}
boolean success = false;
if (x >= 1 && isFree(X - 1, Y)) { //Try to go right
success = getPath(x - 1, y, path, cache); // Free! We can go right
}
if (!success && y >= 1 && isFree(x, y - 1)) { // Try to go down
success = getPath(x, y - 1, path, cache); // Free! We can go down
}
if (!success) {
path.remove(p); //Wrong path! Stop moving along this route
}
cache.put(p, success); // Cache the result
return success;
}
This simple change makes our code faster.
Analysis of the problem from the book «Cracking the Coding Interview: Getting a Job at Google, Microsoft or Another Leading IT Company».
Original article.
Implement a string compression method based on counting repeated characters. For example, the string aabcccccaaa should become a2b1c5a3. If the «compressed» string turns out to be longer than the original, the method should return the original string.
Expand answer
This code does not track the case where the compressed string turns out to be longer than the original. But is this algorithm efficient?
Let's estimate the running time of this code: O(p + k2), where p is the size of the original string, and k is the number of character sequences. For example, the string aabccdeeaa contains 6 character sequences. The algorithm runs slowly because it uses string concatenation, which typically requires O(n2) time.
The code can be improved by using, for example, StringBuffer in Java:
String compressBetter(String str) {
/* Check whether compression would create a longer string */
int size = countCompression(str);
if (size >= str.length()) {
return str;
}
StringBuffer mystr = new StringBuffer();
char last = str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) { // A repeated character is found
count++;
} else { // Insert the character count, update the last character
mystr.append(last); // Insert the character
mystr.append(count); // Insert the count
last = str.charAt(i);
count = 1;
}
}
/* In lines 15-16, characters are inserted when
* the repeated character changes. We must update the string
* at the end of the method, since the very last
* repeated character
* has not yet been set in the compressed string
* */
mystr.append(last);
mystr.append(count);
return mystr.toString();
}
int countCompression(String str) {
char last = str.charAt(0);
int size = 0;
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) {
count++;
} else {
last = str.charAt(i);
size += 1 + String.valueOf(count).length();
count = 0;
}
}
size += 1 + String.valueOf(count).length();
return size;
}
This algorithm is much more efficient. Notice the size check in lines 2—5.
If we don't want to (or cannot) use StringBuffer, this problem can be solved differently. In line 2, the final size of the string is calculated, which allows creating an array of the appropriate size:
String compressAlternate(String str) {
/* Check whether compression would create a longer string */
int size = countCompression(str);
if (size >= str.length()) {
return str;
}
char[] array = new char[size];
int index = 0;
char last = str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) { // Find the repeated character
count++;
} else {
/* Update the count of repeated characters */
index = setChar(str, array, last, index, count);
last = str.charAt(i);
count = 1;
}
}
/* Update the string with the last set of repeated characters */
index = setchar(str, array, last, index, count);
return String.valueOf(array);
}
int setChar(String str, char[] array, char c, int index,
int count) {
array[index] = c;
index++;
/* Convert the count to a string */
char[] cnt = String. valueOf (count) .toCharArray();
/* Copy the characters from the highest digit to the lowest */
for (char x : cnt) {
array[index] = x;
index++;
}
return index;
}
int countCompression(String str) {
/* same as before */
}
Like the previous solution, this code requires O(N) time and O(N) space.
Discussion of the problem based on the book «Cracking the Coding Interview: How to Get a Job at Google, Microsoft, or Another Leading IT Company».
Original article.
You are in a car, where a helium-filled balloon is tied to the floor with a string. The windows are closed. You press the gas pedal. What will happen to the balloon: will it move forward, backward, or stay in the same position?
What will happen to the balloon?
Intuition tells us (almost all of us) that when accelerating, the balloon will be thrown backward. However, intuition is wrong in this case.
Expand answer
Your task is to determine, through deductive reasoning, how the balloon actually moves, and to explain this to the interviewer.
A good answer is to offer an analogy with a spirit level (a construction level). Although this tool is not always at hand when needed, there are people who work with it constantly. Carpenters in particular use it often, to make sure a surface is horizontal. A spirit level contains a narrow glass tube with colored liquid, and inside it — an air bubble. Whenever the level is placed on a perfectly horizontal surface, the bubble ends up in the middle of the tube. If the surface is not horizontal, the bubble shifts toward the higher end of the tube. The analogy here is that the bubble is simply a «hole» in the liquid. When the surface is not level, gravity pushes the liquid toward the lower edge. This, in turn, moves the bubble to where there is no liquid — toward the opposite edge.
Untie the helium balloon and let it bump against the «ceiling». Now it becomes a kind of level. The balloon is the «bubble», made of helium, a gas with lower density, which sits within denser air, and this whole combination of gases is inside a container (the car). Gravity pushes the heavier air down, forcing the lighter balloon to press against the «ceiling».
When the car accelerates, the air, like your body, is thrown backward. This causes the balloon, which is lighter than air, to move forward. If you brake sharply, the air presses against the front window, but the balloon is thrown backward. The same thing is observed during turns. In this case, centrifugal force pushes the air toward the side opposite the axis of the turn, and the balloon toward it. Of course, the same thing happens when the balloon is tied to something, but then it has less freedom to move. The short answer to the question posed is this: a helium balloon shifts in the direction of any acceleration.
Don't believe it? Then right now, put down the book, go to the supermarket, buy a helium-filled balloon, and tie it with a string to the gearshift lever or the parking brake lever. Head home (you don't need to do this at insane speed). You will be surprised, but the balloon really does shift in the opposite direction from what you expected. When you press the gas, the balloon shoots forward, as if trying to race the car to the next traffic light. Brake sharply, so that children's toys fall off the seat, and the balloon will jerk backward. When turning at high speed, when your body leans strongly to one side, the crazy balloon moves sharply the other way. There are videos on YouTube about this apparent strangeness.
Why does our intuition give us the right answers about the spirit level and the wrong ones about the helium balloon? If we talk about the spirit level, the heavy liquid in it is colored with fluorescent dye (and in this respect resembles sports drinks in color), while the bubble in it is practically colorless. We associate color with density, and transparency with emptiness. Therefore, in the case of the balloon, this instinct turns out to be completely wrong. Air is invisible, and 99% of the time we ignore it. The balloon, on the other hand, is colored a nice color and seems to shout: «Look at me!» We almost all forget that a partial vacuum appears in the air around us. A helium balloon moves in the direction opposite to the movement of the bulk mass, because it lacks weight. The real mass — the air — remains invisible.
Interviewers asking this question do not expect you to have a deep knowledge of physics. There is an alternative version of the question, built on the theory of relativity. I am being serious.
It relates to the well-known thought experiment of Albert Einstein involving an elevator. Imagine you are in an elevator riding to the office of your tax advisor, and at this moment a malicious extraterrestrial being decides it would be amusing to teleport you and the elevator into intergalactic space. The elevator is an enclosed space, and there is enough air in it for you to stay alive for a while and entertain this alien being for a few minutes. There are no windows, so you cannot look out and see where you are. The being has hooked the elevator to a cable and pulls it with constant acceleration, exactly equal to Earth's gravity. Can you, inside a closed elevator, determine whether you are being subjected to Earth's actual acceleration or an «artificial» gravity simulated by acceleration?
Einstein claimed that you cannot. If you took your keys out of your pocket and tossed them, they would fall to the elevator floor exactly as they would on Earth. If we took a helium balloon tied to a string, it would rise upward just as it would on Earth. In other words, everything in the elevator would seem completely normal to you.
Einstein's equivalence principle states that there is no simple physical experiment capable of showing the difference between gravity and acceleration. This assumption is fundamental to Einstein's theory of gravity, known as general relativity. Physicists have been trying to find flaws in the equivalence principle for almost a century now. They try and cannot. Therefore it is quite safe to assume that Einstein's idea is correct, at least for any experiments you can carry out in a car with a two-dollar balloon.
So, here is the physical experiment. Tie a string on one end to a lead weight, and on the other — to the index finger of your right hand. Tie a helium balloon to the same finger. Pay attention to the angle between the two strings.
In an elevator, in a parked car, or in a jet plane crashing, the results will be the same. The string with the attached weight will point straight down, the balloon's string — straight up. So the two strings tied to your finger form a straight line. And this will be the case whenever you are subject to the force of gravity.
Now imagine what happens when you start moving. As speed increases, your body will be pressed into the seat. Your intuition, misleadingly, might suggest that the lead weight and the balloon would both be pushed slightly backward relative to your finger, and that during acceleration an angle would form between the two strings (if you trust your intuition). This angle would let you determine the difference between the force of gravity and the force of acceleration. When the car is subject only to gravity, the two strings form a straight line. But when they are affected by centrifugal force or another kind of acceleration, an angle forms between the strings, with your finger as its vertex. That is all you would need to prove that general relativity is wrong. If that happened, you could safely forget about wanting a job at Google, because now your ambitions would rise sharply — you would want a Nobel Prize.
However, since the equivalence principle has been tested rigorously and repeatedly, and has always proven correct, the scenario described will not occur, and you can use the equivalence principle to answer this question. Physics will manifest itself exactly the same way in an accelerating car as in a car subject only to the force of gravity. In both cases, the balloon, your finger, and the lead weight will form a straight line. So the helium balloon (from our question) actually moves in the direction opposite to what we would expect for an object with mass. In other words, it will shift forward rather than backward… left rather than right… and, of course, up rather than down.
Puzzle breakdown from the book «Are You Smart Enough to Work at Google?».
Original article.
A problem through which one can briefly get acquainted with the basics of RSA cryptography.
Suppose you want to make sure that your friend Petya has your phone number. But you cannot ask him about it directly. You have to write him a message on a card and hand the card to Katya, who will act as an intermediary. Katya will bring the card to Petya, he will write his message and give it to Katya, who will pass it to you. You do not want Katya to learn your phone number. Under these circumstances, how should you phrase your question to Petya?
Even without knowing anything about RSA, you can try to come up with an answer.
Expand answer
When using RSA, two keys are generated: a public one and a private one. The public key is similar to an email address. It allows anyone to send you a message. The private key — is something like your email password. You need it to receive your emails, and you must keep it secret, since otherwise a message addressed to you could be read by anyone.
You cannot send Petya a secret message, since he has not created his keys. He might not even know what RSA is, and won't know anything about it until you tell him! But for this you don't need to send him a secret message. You want Petya to send such a message to you, namely — your phone number. This means that we need keys for ourselves, not for Petya. Here is the general scheme of the solution.
«Hi, Petya! We're going to use RSA cryptography. You might not know what that is, but I'll explain what needs to be done. Here is my public key… Take it and my phone number and come up with an encrypted number, following the instructions. Send this encrypted number back to me through Katya».
The trick is to phrase the instructions so that practically anyone could use them. On top of that, you also need to ensure the necessary precision.
RSA cryptography was first described, as is now believed, in 1973. Its first creator was the British mathematician Clifford Cocks, who at the time worked for Her Majesty's secret service. In those years his scheme was considered impractical: it necessarily required a computer. At a time when spies typically made do with cameras hidden in cufflinks, this difficulty was not so easy to overcome. Until 1997, Cocks's idea was kept secret. However, in 1978 three scientists from MIT, Ronald Rivest, Adi Shamir, and Leonard Adleman, proposed it independently of Cocks. The first letters of their surnames (RSA) became the acronym and name of this algorithm.
In the RSA system, a person who wants to receive messages must choose two random prime numbers p and q. The numbers must be large and at least as large (in number of digits) as the numbers or messages that need to be transmitted. For a ten-digit phone number, p and q must also each consist of at least ten digits.
One way to choose p and q — is to use Google and find a website that lists large prime numbers. Say, the Prime Pages, maintained by Chris Caldwell of the University of Tennessee at Martin. Randomly choose two ten-digit prime numbers. Here is an example of such a pair:
1,500,450,271 and 3,367,900,313.
Call them p and q respectively. You will need to multiply them and get the exact answer. There may be a slight difficulty here, since you cannot use calculators, Excel, or Google, nor most other consumer programs, since they display a limited number of significant digits. One option — is to multiply by hand. Or use Wolfram Alpha. Enter
1,500,450,271 and 3,367,900,313
and you get the exact answer:
5,053,366,937,341,834,823.
Call this product N. It is one of the components of your public key. The other component is a number called e, chosen arbitrarily and of a length ideally equal to N, but which does not divide evenly into the product (p - 1)(q - 1). I may have confused you with that last sentence, but don't worry about it for now.
In many applied programs, cryptographers choose a simple three as e. This is a good enough option for many purposes and allows for fast encryption.
You have obtained N and e, and now you have everything necessary to solve the problem. All you need to do is send these two numbers to Petya, along with a complete «RSA Cryptography for Dummies Guide». Petya needs to compute
xe mod N,
where X is the phone number. Since we chose 3 for e, the left-hand side is x raised to the cube. This will be a 30-digit number. «Mod» refers to division by modulus, meaning that you divide x³ by N and take only the remainder. This remainder must be in the range from 0 to N - 1. It will likely be a 20-digit number. This number is the encrypted message that Petya will send back to you.
To solve this problem, Petya needs to cube a number and perform division. The important part of the instructions might be as follows.
«Petya, I want you to carefully follow these
продолжение следует...
Часть 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