Lecture
Это продолжение увлекательной статьи про .
...
intended solely for informational purposes.
Original article.
You place a glass of water on the turntable of a vinyl record player and slowly increase the rotation speed. What will happen first: the glass will slide to the side, the glass will tip over, or the water will spill?
This question was previously asked in interviews at Apple. In your answer, consider the possible scenarios and indicate what the answer depends on if there is more than one.
Show answer
This question was previously asked at Apple. Most people understand that centrifugal force must be taken into account when analyzing it. Equally, you need to know about friction. It arises between the bottom of the glass and the rotating disk, which sets the glass in motion.
To make the situation clearer, imagine a world where friction is completely absent. Everything becomes slicker than Teflon, and infinitely slicker at that. Then, in the experiment described in the question, there would be no effect on the glass at all. The record player's disk would spin beneath the glass without affecting it in any way, meaning the glass wouldn't move at all. This is consistent with Newton's first law: objects at rest remain at rest until acted upon by some force. Without friction, the glass will not move.
Now imagine the opposite scenario: a glass is glued to the disk using very strong Krazy Glue, and an almost infinitely high friction force appears between the two surfaces. In this case, the glass and the disk will rotate as a single unit. Increase the disk's speed, and the glass will rotate faster. This will lead to an increase in centrifugal force. The only thing that will be free to react to this force under these conditions is the water. After all, it isn't glued to the bottom of the glass. When the glass spins fast enough, the water will spill toward the side opposite the center of rotation.
The question asks you to consider a scenario that lies between the extreme cases. At first, friction will be sufficient to hold the glass in place. It will rotate together with the disk, creating a small centrifugal force. As the rotational speed increases, the centrifugal force will grow. The pressure holding the glass in place will remain roughly the same. Therefore, at some point the centrifugal force must exceed the holding force.
Those who have studied physics or spent a lot of time in childhood games will recall that when an object starts to slide, the friction force becomes smaller than when it is stationary. At the top of an icy slide you "stick" a little at first, but then suddenly begin to move freely down it. The same applies to the disk. Instead of accelerating gradually the whole time, the glass is at first held in place, and only after some time does it begin to move.
What happens next? The answer here is: it depends on the shape of the glass and how full of water it is. However, if you limit yourself to just that answer, the interviewer may decide that you're trying to dodge the question. Here are the variants that are possible in real life.
Fill the glass with water to the brim. Even the smallest centrifugal force will cause the water level to rise above the glass's outer edge, causing some of the water to spill. This will happen even while the glass is "glued," that is, before it starts to slide.
Use a very low glass, for example, a Petri dish with a drop of water in it. If you chose such a vessel for the experiment, it will not tip over, nor will it move fast enough for the single drop of water to climb up its wall and spill. Instead, the Petri dish with the drop will simply slide off the disk.
Use a very tall glass, like a flat-bottomed test tube. The centrifugal force effectively acts on the center of gravity. Since the center of gravity in this case is located high up, while the entire friction force is applied at the very bottom, the glass test tube is more likely to tip over than to slide.
It's also important to take the disk's surface into account. If it's made of rubber, this will increase friction and make spilling and tipping equally likely. A more slippery hard plastic surface favors the sliding scenario.
This analysis is taken from the book "Are You Smart Enough to Work at Google?".
Original article.
A short C++ problem in the form of a question for beginners. Why must the destructor of a polymorphic base class be declared virtual? We consider a class polymorphic if it has at least one virtual function.
Expand the answer
Let's figure out why virtual methods are needed. Consider the following code:
class Foo {
public:
void f();
};
class Bar : public Foo {
public:
void f();
}
Foo *p = new Bar();
p->f();
By calling p->f(), we access Foo::f(). This is because p is a pointer to Foo, and f() is a non-virtual function.
To ensure that p->f() calls the correct implementation of f(), it is necessary to declare f() as a virtual function.
Now let's return to the destructor. Destructors are meant for cleaning up memory and resources. If Foo's destructor is not virtual, then when a Bar object is destroyed, the base class Foo's destructor will still be called.
That's why destructors are declared virtual — this guarantees that the destructor for the derived class will be called.
This analysis is taken from Gayle L. McDowell's book "Cracking the Coding Interview" (available in translation).
Original article.
Write a function that swaps the values of variables without using temporary variables. Suggest as many variants as possible.
Expand the answer
This is a classic problem that is often asked in interviews, and it's fairly simple. Let a0 be the original value of a, and b0 the original value of b. Let's denote diff as the difference a0 - b0.
Let's show the mutual position of all these values on the number line for the case when a > b:
Let's assign a the value diff. If we add the value of b and diff, we get a0 (the result should be stored in b). Now we have b = a0 and a = diff. All that remains is to assign b the value a0 - diff, which is the value b - a.
The following code implements this algorithm:
public static void swap(int a, int b) {
// Example for a = 9, b = 4
a = a - b; // a = 9 - 4 = 5
b = a + b; // b = 5 + 4 = 9
a = b - a; // a = 9 - 5
System.out.println("a: " + a);
System.out.println("b: " + b);
}
This problem can be solved using bitwise manipulation. This approach lets us work with different data types, not just integers.
public static void swap_opt(int a, int b) {
//Example for a = 101 (in binary) and b = 110
a = a ^ b; // a = 101^110 = 011
b = a ^ b; // b = 011^110 = 101
a = a ^ b; // a = 011^101 = 110
System.out.println("a: " + a);
System.out.println("b: " + b);
}
This code uses the XOR operation. The easiest way to understand how the code works is to look at two bits — p and q. Let's denote their original values as p0 and q0.
If we can swap two bits, the algorithm will work correctly. Let's walk through the algorithm step by step:
p = p0^q0 /* 0 if p0 = q0, 1 if p0 != q0 */
q = p^q0 /* equals the value of p0 */
p = p^q /* equals the value of q0 */
In line 1, the operation p = p0^q0 is performed, the result of which will be 0 if p0 = q0, and 1 if p0 != q0.
In line 2, the operation q = p^q0 is performed. Let's analyze both possible values of p. Since we want to swap the values of p and q, the result should be 0:
p = 0: in this case p0 = q0, since we need to return p0 or q0. XOR of any value with 0 always gives the original value, so the result of this operation will be q0 (or p0).
p = 1: in this case p0 != q0. We need to get 1 if q0 = 0, and 0 if p0 = 1. This is exactly the result obtained when XORing any value with 1.
In line 3, the operation p = p^q is performed. Let's consider both values of p. As a result, we want to get q0. Note that q at this point equals p0, so the operation actually being performed is p^p0.
p = 0: since p0 = q0, we want to return p0 or q0. By performing 0^p0, we get back p0 (q0).
p = 1: the operation 1^p0 is performed. As a result, we get the inverse of p0, which is what we need, since p0 != q0.
All that remains is to assign p the value q0, and q — the value p0. We have confirmed that our algorithm correctly swaps each bit, which means the result will be correct.
This analysis is taken from a translation of G. Lakman McDowell's book and is intended for informational purposes only.
Original article.
Suggest an algorithm for finding the k-th element from the end in a singly linked list. The list is implemented manually; there is only an operation to get the next element and a pointer to the first element. The algorithm should, if possible, be optimal in time and memory.
Expand the answer
This algorithm can be implemented recursively or non-recursively. Recursive solutions are usually more understandable but less optimal. For example, a recursive implementation of this problem is almost twice as short as the non-recursive one, but it takes O(n) space, where n is the number of elements in the linked list.
When solving this problem, remember that you can choose the value k so that passing k = 1 gives us the last element, 2 the second-to-last, and so on. Or choose k so that k = 0 corresponds to the last element.
If the size of the linked list is known, the k-th element from the end is easy to compute (length – k). You just need to walk through the list and find that element.
This algorithm recursively traverses the linked list. Upon reaching the last element, the algorithm begins counting back, and the counter is reset to 0. Each step increments the counter by 1. When the counter reaches k, the sought element has been found.
The implementation of this algorithm is short and simple – it's enough to pass an integer value back up through the stack. Unfortunately, the return statement cannot return a node's value. So how do we get around this difficulty?
You can avoid returning the element and instead print it out as soon as it's found. And in the return statement, return the value of the counter.
public static int nthToLast(LinkedListNode head, int k) {
if (head == null) {
return 0;
}
int i = nthToLast(head.next, k) + 1;
if (i == k) {
System.out.println(head.data);
}
return i;
}
The solution is correct, but there's another way to go about it.
The second way is to use C++ and pass the value by reference. This approach lets you not only return the node's value, but also update the counter by passing a pointer to it.
node* nthToLast(node* head, int k, int& i) {
if (head == NULL) {
return NULL;
}
node* nd = nthToLast(head->next, k, i);
i = i + 1;
if (i == k) {
return head;
}
return nd;
}
The iterative solution will be more complex, but also more optimal. We can use two pointers – p1 and p2. Initially both pointers point to the start of the list. Then we move p2 forward by k nodes. Now we begin moving both pointers simultaneously. When p2 reaches the end of the list, p1 will be pointing at the element we need.
LinkedListNode nthToLast(LinkedListNode head, int k) {
if (k <= 0) return 0;
LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int i = 0; i < k - 1; i++) {
if (p2 == null) return null;
p2 = p2.next;
}
if (p2 == null) return null;
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
This analysis is taken from a translation of G. Lakeman McDowell's book and is intended for informational purposes only.
Original article.
Write a function that determines the number of bits that need to be changed to turn integer A into integer B. Assume the numbers are 32-bit; any language.
This is one of the typical bit-manipulation problems that interviewers like to ask. If you've never encountered them before, it will be hard to solve on the spot given the stress of an interview, so remember the tricks used in the solution.
Show answer
At first glance the problem seems hard, but it's actually very simple. To solve it, ask yourself: “How can I find out which bits differ between two numbers?”. The answer is simple – using the XOR operation.
Each 1 in the resulting number corresponds to a bit that doesn't match between numbers A and B. Therefore, calculating the number of mismatched bits between A and B comes down to counting the number of ones in A XOR B:
int bitSwapRequired(int a, int b) {
int count = 0;
for (int c = a ^ b; c != 0; c = c >> 1) {
count += c & 1;
}
return count;
}
This code is good, but it can be made even better. Instead of repeatedly shifting to check the significant bit, it's enough to clear the least significant nonzero bit and count how many times this operation needs to be performed until the number becomes zero. The operation c = c & ( c – 1) clears the least significant nonzero bit of c.
The following code implements this method:
public static int bitSwapRequired(int a, int b) {
int count = 0;
for (int c = a ^ b; c != 0; c = c & (c - 1)) {
count++;
}
return count;
}
This is one of the typical bit-manipulation problems that interviewers like to ask. If you've never encountered them before, it will be hard to solve right away, so remember the tricks used here.
This analysis is taken from a translation of G. Lakeman McDowell's book and is intended for informational purposes only.
Original article.
A book has N pages, numbered as usual from 1 to N. If you add up the number of digits contained in each page number, you get 1095. How many pages are in the book?
Show answer
Every number denoting a page has a units digit. With N pages there are N digits in the units place.
All pages except the first 9 have numbers that are at least two digits long. So let's add another N-9 digits.
All pages except the first 99 have three-digit numbers, which adds another N-99 digits.
I could keep going like this, but only a small number of books have more than 999 pages. At the very least, a book with a total digit count of 1095 doesn't fall into the «thick book» category.
From what has been said, it follows that 1095 should equal:
N + (N - 9) + (N - 99).
This equation can be reduced to a simpler form:
1095 = 3N - 108.
From this it follows that 3N = 1203, or N = 401.
So the answer is: the book has 401 pages.
This analysis is taken from the book «Are You Smart Enough to Work at Google?».
Original article.
A C++ problem, which will nevertheless be useful for other languages too. Compare a hash table and the map from the Standard Template Library (STL). How is a hash table organized? Which data structure would be optimal for small amounts of data?
Show answer
A value gets into a hash table when the hash function is called with a key. The values themselves are stored in unsorted order. Since a hash table uses a key to index elements, inserting or looking up data takes O(1) time (assuming a minimal number of collisions in the hash table). A hash table must also handle potential collisions. For this, chaining is used – a linked list of all the values whose keys map to a specific index.
The STL map inserts key/value pairs into a binary search tree based on the keys. This requires no collision handling, and since the tree is balanced, insertion and lookup time is O(log N).
A hash table is implemented as an array of linked lists. When we want to insert a key/value pair, we use the hash function to map the key to an array index. The value is then placed at the corresponding position in the linked list.
It can't be said that the elements of the linked list at a given array index have the same key. Rather, the function hashFunction(key) produces the same value for these keys. So, to retrieve the value corresponding to a key, we must store both the key and the value in each node.
To sum up: a hash table is implemented as an array of linked lists, where each node of the list contains two components: the value and the original key. Let's list the features of hash table implementations:
You need to use a good hash function to ensure that keys are distributed properly. If keys are poorly distributed, there will be many collisions and the speed of finding an element will drop.
No matter how good our hash function is, collisions will occur, and we will need to handle them. This implies using chains of linked lists (or another method of solving the problem).
You can implement methods for dynamically increasing or decreasing the size of the hash table. For example, when the ratio of the number of elements to the size of the table exceeds a certain value, the hash table's size should be increased. This means that we will need to create a new hash table and transfer the entries from the old one into it. Since this is a very time-consuming process, everything possible should be done so that the table's size doesn't change too often.
You can use a map (from the STL) or a binary tree. Although this will require O(log(n)) time, the amount of data is not large, so the time cost will be negligible.
A tree has at least one notable advantage over a hash table. With a map you can iterate over the keys in increasing or decreasing order, and do so quickly. A hash table falls short in this respect.
This analysis is taken from a translation of the book by G. Lakman McDowell and is intended solely for informational purposes.
Original article.
Design a class that provides locking so as to prevent deadlock from occurring.
Expand answer
There are several common ways to prevent deadlocks. One of the most popular is to require a process to explicitly declare which lock it needs. Then we can check whether the resulting lock would be a deadlock, and if so, we can abort.
Let's figure out how to detect a deadlock. Suppose we request the following lock order:
A = {1, 2, 3, 4}
B = {1, 3, 5}
C = {7, 5, 9, 2}
This will result in a deadlock, because:
A locks 2, waits for 3
B locks 3, waits for 5
C locks 5, waits for 2
We can represent this scenario as a graph, where 2 is connected to 3, 3 is connected to 5, and 5 is connected to 2. A deadlock is described by a cycle. An edge (w, v) exists in the graph if a process declares that it will request lock v immediately after lock w. In the previous example, the following edges will exist in the graph:
(1, 2), (2, 3), (3, 4), (1, 3), (3, 5), (7, 5), (5, 9), (9, 2).
The «owner» of an edge does not matter.
This class will need a declare method that uses threads and processes to declare the order in which resources will be requested. The declare method will check the declaration order, adding each consecutive pair of elements (v, w) to the graph. It will then check whether a cycle has appeared. If a cycle has occurred, it will remove the added edge from the graph and exit.
We only need to discuss one nuance. How do we detect a cycle? We can detect a cycle using depth-first search through each connected element (that is, through each component of the graph). There are complex components that allow selecting all the connected components of a graph, but our task is not that complex.
We know that if a loop occurs, then one of the edges is responsible. Thus, if a depth-first search touches those edges, we will detect the loop.
The pseudocode for this loop detection is roughly as follows:
boolean checkForCycle(locks[] locks) {
touchedNodes = hash table(lock -> boolean)
//initialize touchedNodes by setting each lock in locks to false
for each (lock x in process.locks) {
if (touchedNodes[x] == false) {
if (hasCycle(x, touchedNodes)) {
return true;
}
}
}
return false;
}
boolean hasCycle(node x, touchedNodes) {
touchedNodes[r] = true;
if (x.state == VISITING) {
return true;
} else if (x.state == FRESH) {
//...(see full code below)
}
}
In this code, several depth-first searches can be performed, but touchedNodes only needs to be initialized once. We iterate while all values in touchedNodes are false.
The code below is more detailed. For simplicity, we assume that all locks and processes (owners) are sequentially ordered.
public class LockFactory {
private static LockFactory instance;
private int numberOfLocks = 5; /* default */
private LockNode[] locks;
/* Maps a process (owner) to the order
* in which the owner requested locks */
private Hashtable> lockOrder;
private LockFactory(int count) { ... }
public static LockFactory getInstance() { return instance; }
public static synchronized LockFactory initialize(int count) {
if (instance == null)
instance = new LockFactory(count);
return instance;
}
public boolean hasCycle(Hashtable touchedNodes, int[] resourcesInOrder) {
/* check for the presence of a loop */
for (int resource : resourcesInOrder) {
if (touchedNodes.get(resource) == false) {
LockNode n = locks[resource];
if (n.hasCycle(touchedNodes)) {
return true;
}
}
}
return false;
}
/* To prevent deadlock, we force processes to
* declare that they want to lock. We check
* that the requested order will not cause a deadlock
* (a loop in the directed graph) */
public boolean declare(int ownerId, int[] resourcesInOrder) {
Hashtable touchedNodes = new Hashtable();
/* add nodes to the graph */
int index = 1;
touchedNodes.put(resourcesInOrder , false);
for (index = 1; index < resourcesInOrder.length; index++) {
LockNode prev = locks[resourcesInOrder[index - 1]];
LockNode curr = locks[resourcesInOrder[index]];
prev.joinTo(curr);
touchedNodes.put(resourcesInOrder[index], false);
}
/* if a loop is obtained, destroy this resource list
* and return false */
if (hasCycle(touchedNodes, resourcesInOrder)) {
for (int j = 1; j < resourcesInOrder.length; j++) {
LockNode p = locks[resourcesInOrder[j - 1]];
LockNode c = locks[resourcesInOrder[j]];
p.remove(c);
}
return false;
}
/* No loop found. We save the order that was declared,
* so that we can verify that the process actually calls
* the lock in the correct order */
LinkedList list = new LinkedList();
for (int i = 0; i < resourcesInOrder.length; i++) {
LockNode resource = locks[resourcesInOrder[i]];
list.add(resource);
}
lockOrder.put(ownerId, list);
return true;
}
/* Acquire the lock, first checking that the process
* actually requests the lock in the declared order*/
public Lock getLock(int ownerld, int resourceID) {
LinkedList list = lockOrder.get(ownerId);
if (list == null) return null;
LockNode head = list.getFirst();
if (head.getId() == resourceID) {
list.removeFirst();
return head.getLock();
}
return null;
}
}
public class LockNode {
public enum VisitState { FRESH, VISITING, VISITED );
private ArrayList children;
private int lockId;
private Lock lock;
private int maxLocks;
public LockNode(int id, int max) { ... }
/* Attach "this" to "node", checking that we don't create
* a loop (cycle) by doing so */
public void joinTo(LockNode node) { children.add(node); }
public void remove(LockNode node) { children.remove(node); }
/* Check for the presence of a cycle using depth-first search */
public boolean hasCycle(Hashtable touchedNodes) {
VisitState[] visited = new VisitState[maxLocks];
for (int i = 0; i < maxLocks; i++) {
visited[i] = VisitState.FRESH;
}
return hasCycle(visited, touchedNodes);
}
private boolean hasCycle(VisitState[] visited,
Hashtable touchedNodes) {
if (touchedNodes.containsKey(lockId)) {
touchedNodes.put(lockId, true);
}
if (visited[lockId) == VisitState.VISITING) {
/* We have looped back to this node, therefore
* we know there is a cycle (loop) here */
return true;
} else if (visited[lockId] == VisitState.FRESH) {
visited[lockId] = VisitState.VISITING;
for (LockNode n : children) {
if (n.hasCycle(visited, touchedNodes)) {
return true;
}
}
visited[lockId] = VisitState.VISITED;
}
return false;
}
public Lock getLock() {
if (lock == null) lock = new ReentrantLock();
return lock;
}
public int getId() { return lockId; }
}
This analysis is taken from a translation of the book by G. Lakman McDowell and is intended solely for informational purposes.
Original article.
Write a function in C++ that outputs to standard output the last K lines of a file. The file is very large, say 50 GB, the length of each line does not exceed 256 characters, and the number K < 1000.
Show the answer
One straightforward approach is to count the number of lines (N) and output the lines from N-K to N. This requires reading the file twice, which is very inefficient. Let's find a solution that requires reading the file only once and outputs the last K lines.
We can create an array for K lines and read the last K lines. In our array, we will store lines 1 through K, then 2 through K+1, then 3 through K+2, and so on. Each time we read a new line, we will remove the oldest line from the array.
You might wonder: can a solution requiring constant shifting of elements in the array really be efficient? This solution becomes efficient if we implement the shifting correctly. Instead of shifting the array every time, we can make the array "circular."
Using such an array, whenever we read a new line, we will always replace the oldest element. The oldest element will be stored in a separate variable, which will change as new elements are added.
Example of using a circular array:
step 1 (initial state): array = {a, b, c, d, e, f}. p = 0
step 2 (insert g): array = {g, b, c, d, e, f}. p = 1
step 3 (insert h): array = {g, h, c, d, e, f}. p = 2
step 4 (insert i): array = {g, h, i, d, e, f}. p = 3
The code below implements this algorithm:
void printLast10Lines(char* fileName) {
const int K = 10;
ifstream file (fileName);
string L[K];
int size = 0;
/* read the file line by line into a circular array */
while (file.good()) {
getline(file, L[size % K]);
size++;
}
/* compute the start of the circular array and its size */
int start = size > K ? (size % K) : 0;
int count = min(K, size);
/* output the elements in reading order */
for (int i = 0; i < count; i++) {
cout << L[(start + i) % K] << endl;
}
}
We read the entire file, but only 10 lines are kept in memory.
This analysis is taken from the translation of a book by G. Lakman McDowell and is intended solely for informational purposes.
Original article.
You are given a piece of cheese in the shape of a cube and a knife. What is the minimum number of cuts required to divide this piece into 27 equal small cubes? What about 64 cubes? After each cut, the pieces can be rearranged in any way.
This kind of problem used to be commonly given at interviews, and it was invented back in 1950.
Show the answer
To get 27 small cubes, you need to cut each of the three faces of the cube into three parts. Getting three parts requires two cuts. The obvious answer is to make these cuts parallel to each other along all three axes, which requires six cuts in total.
BUT! With questions like this, the first answer that pops into your head is usually not the best one. Can the answer be improved? Remember that you can move the pieces around after each cut (as cooks often do when cutting onions). This substantially increases the number of possible variants, and you might then find one you initially overlooked.
In fact, there is no way to cut the cube into 27 pieces with fewer than six cuts. Ideally you should prove this. Let's show how it can be done. Imagine the small cube that results from cutting the original cube into 3 x 3 x 3 = 27 parts, located right in the middle of the original cube. This little cube has no surface bordering the outside world. Therefore you will have to create each of its six sides with the knife. Six straight cuts are the minimum needed to solve this problem. This question belongs to the category of reverse puzzles. Obviously, the first answer turns out to be correct, although many people try to come up with non-obvious variants.
According to Martin Gardner, the author of this puzzle was Frank Hawthorne, director of the education department of New York, who published it in 1950. The idea of rearranging the pieces to reduce the number of cuts is not as crazy as it might seem. Thus, in this case, a cube can be cut into 4 x 4 x 4 small cubes using only six cuts (whereas the previous approach would require nine cuts).
In 1958, Eugene Putzer and Lowen published a general solution for cutting a cube into N x N x N small cubes. They assured all practically-minded readers that their method could have "important consequences for the cheese and sugar-cube industries."
This question is distantly reminiscent of another one asked at interviews at some financial organizations: how many small cubes are in the center of a Rubik's Cube? Since a standard cube consists of 3 x 3 x 3 parts, the wrong answer — one — is often given. However, anyone who has ever taken apart a Rubik's Cube knows that the correct answer is different — zero. In the middle there is no cube at all, but a spherical joint.
This analysis is taken from the book "Are You Smart Enough to Work at Google?".
Original article.
Implement a method that determines whether one string is a permutation of another. By permutation we mean any reordering of the characters. Case matters, and spaces are significant.
Show the answer
First we need to clarify the details. We should figure out whether the anagram comparison is case-sensitive. That is, is the string "God" an anagram of "dog"? We also need to find out whether spaces are taken into account.
Let's assume that for this problem character case matters and spaces are significant. So the strings " dog" and "dog" do not match.
When comparing two strings, remember that strings of different lengths cannot be anagrams.
There are two ways to solve this problem.
If the strings are anagrams, they consist of the same characters arranged in a different order. Sorting the two strings should put the characters in order. Now it only remains to compare the two sorted versions of the strings.
public String sort(String s) {
char[] content = s.toCharArray();
java.util.Arrays.sort(content);
return new String(content);
}
public boolean permutation (String s,String t) {
if (s.length() != t.length()) {
return false;
}
return sort(s).equals(sort(t));
}
Although this algorithm cannot be called optimal in every sense, it is a good one because it is easy to understand. From a practical standpoint, it is an excellent way to solve the problem. However, if efficiency matters, another variant of the algorithm needs to be implemented.
To implement this algorithm, we can use the property of an anagram — identical "counts" of characters. We simply count how many times each character occurs in the string. Then we compare the arrays obtained for each string.
public boolean permutation(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] letters = new int[256];
char[] s_array = s.toCharArray();
for (char c : s_array) {
letters[c]++;
}
for (int i = 0; i < t.length(); i++) {
int c = (int) t.charAt(i);
if (--letters[c] < 0) {
return false;
}
}
return true;
}
Pay attention to line 6. In this implementation we assume that the ASCII character set is used, but the alphabet could be different.
This analysis is taken from the translation of a book by G. Lakman McDowell and is intended solely for informational purposes.
Original article.
In a dark room, you are handed a deck of cards, in which a known number N of cards are lying face up, and the rest — face down. You cannot see the cards, but you can flip them over. How would you divide the deck into two piles so that each pile has the same number of face-up cards?
This puzzle was at one time popular at JP Morgan Chase. Naturally, finding yourself in the dark, you would simply take out your cell phone and use its screen as a flashlight. However, this problem appeared before the age of cell phones, and it can be solved even without seeing the cards.
Show the answer
The expected answer is that you should count off N cards, starting from the top of the deck, and flip them over. That will be one pile. The remaining part of the deck will make up the second pile.
This puzzle was once popular at JP Morgan Chase. It's understandable that, finding yourself in the dark, you would simply take out your cell phone and use the screen as a flashlight. However, this problem appeared before the era of cell phones, and it can be solved even without seeing the cards. You will most likely start with the following observations.
With an arbitrary division of the deck, it is unlikely that each pile will end up with an equal number of face-up cards (that is possible only if you get lucky). Moreover, all the face-up cards could end up in a single pile.
The question doesn't say that both piles must be equal, only that they must contain the same number of face-up cards.
You can flip cards over. Of course, you have no way of knowing whether you're flipping a card face-up or face-down.
The expected answer is that you should count off N cards, starting from the top of the deck, and flip them over. That will be one pile. The remaining part of the deck will make up the second pile.
Let's explain why this works. Among the N cards you counted off, there could be any number of face-up cards, from zero to N. Suppose there were (before flipping) f such cards. By flipping the cards, you ensured that every face-up card becomes face-down and vice versa. So instead of f face-up cards, you now end up with N-f face-up cards in that pile.
In the other pile, which contains the rest of the deck, there are N face-up cards, minus those f that you counted off. This is the same number as in the first pile with the flipped cards.
This analysis is taken from the book «Are You Smart Enough to Work at Google?».
Original article.
Implement a stack by hand with the standard push/pop functions and an additional min function that returns the minimum element of the stack. All these functions must run in O(1). Optimize the solution for memory usage.
Expand answer
So, the running time estimate for the push, pop, and min functions is O(1).
Extremes don't change often. In fact, the minimum can only change when a new element is added.
One solution is to compare added elements with the minimum value. When the minimum value (minValue) is removed from the stack, we have to “dig through” the entire stack looking for a new minimum. Unfortunately, this violates the O(1) time constraint.
If we track the minimum at every state, we can easily find out the minimum element. We could, for example, record the current minimum element for each node. Then, to find min, it's enough to “pop” the top and see which element is the minimum.
As soon as an element is placed on the stack, the local minimum value becomes global.
public class StackWithMin extends Stack {
public void push(int value) {
int newMin = Math.min(value,min());
super.push(new NodeWithMin(value, newMin));
}
public int min() {
if (this.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return peek().min;
}
}
}
class NodeWithMin {
public int value;
public int min;
public NodeWithMin(int v, int min) {
value = v;
this.min = min;
}
}
The solution has one drawback — if a huge stack needs to be handled, tracking the minimum element will require a lot of resources. Is there a better solution?
The code can be optimized by using an additional stack that tracks minimums.
public class StackWithMin2 extends Stack {
Stack s2;
public StackWithMin2() {
s2 = new Stack();
}
public void push(int value) {
if (value <= min()) {
s2.push(value);
}
super.push(value);
}
public Integer pop() {
int value = super.pop();
if(value == min()) {
s2.pop();
}
return value;
}
public int min() {
if (s2.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return s2.peek();
}
}
}
Why is this solution more efficient? Suppose we are working with a huge stack; the first element inserted automatically becomes the minimum. In the first solution, we need to store n numbers, where n is the size of the stack. In the second solution, it's enough to store a few pieces of data.
This analysis is taken from a translation of the book by G. Lakman McDowell and is intended solely for informational purposes.
Original article.
How many integers in the range from 1 to 1000 have the digit 3? This must be counted without using a computer, giving your reasoning in the comments.
Expand answer
Some numbers (for example, 333) contain more than one 3. You shouldn't count such numbers twice, or even three times. The question is how many distinct numbers have at least one 3.
Every number from 300 to 399 contains at least one 3. Altogether, this group alone gives us a hundred numbers.
There is also a hundred numbers where the 3 occupies the tens place: from 30 to 39; from 130 to 139; and so on up to the numbers from 930 to 939. We already counted ten of these numbers earlier, namely the numbers from 330 to 339. So we need to remove those ten numbers to avoid double counting. In total, we have so far selected 100 + 90 = 190 numbers.
Finally, there is a hundred numbers ending in 3 in the range from 2 to 993. Don't include in this count the 10 numbers that begin with 3 (303, 313, 323,…, 393), because we already included them earlier. This gives another 90 numbers. One tenth of these 90 numbers have a 3 in the tens place (33, 133, 233,…, 933). Removing these 9 numbers leaves 81 numbers. Now we can determine the total number we are interested in.
It equals 100 + 90 + 81 = 271.
Yes, quite.
First, let's find out how many numbers don't have a 3 in their notation. For this, in each position we place 9 digits that don't include 3, i.e., 9 * 9 * 9 = 729. If there are 1000 numbers total, then the answer is 1000 – 729 = 271.
This analysis is taken from the book «Are You Smart Enough to Work at Google?».
Original article.
You have a huge number of URLs, on the order of 10 billion. How would you organize an efficient search for duplicates, given that they will, of course, not all fit in memory?
Expand answer
The difficulty of the problem lies in the fact that 10 billion addresses are given. How much space would be needed to store 10 billion URLs? If, on average, a URL takes up 100 characters, and each character is represented by 4 bytes, then storing a list of 10 billion URLs would require about 4 TB. Most likely, we won't need to store that much information in memory.
Let's first try to solve a simplified version of the problem. Imagine that the entire list of URLs is stored in memory. In that case, we could create a hash table where each duplicate URL is mapped to a value of true (an alternative solution: we could simply sort the list and find duplicates, which would take some time but also has some advantages).
Now that we have a solution to the simplified version of the problem, we can move on to the 400 GB of data that cannot be stored entirely in memory. Let's store some of the data on disk or split the data among computers.
If we are going to store all the data on a single machine, we will need to pass through the document twice. On the first pass, we will split the list into 400 chunks of 1 GB each. A simple way is to store all the URLs in an .txt file, where x = hash(u) % 400. In this way, we split the URLs by hash value. All URLs with the same hash value will end up in the same file.
On the second pass, we can use the solution we came up with earlier: load the file into memory, build a hash table of URLs, and find the duplicates.
This algorithm is very similar to the previous one, but different computers are used to store the data. Instead of storing the data in an .txt file, we send it to machine x.
This solution has both advantages and disadvantages.
The main advantage is that parallel work can be organized so that all 400 blocks are processed simultaneously. For large volumes of data we get a greater time savings.
The drawback is that all 400 machines must work without failures, which in practice (especially with large data volumes and many computers) is not always achievable. Therefore, failure handling must be provided for.
Both solutions are good and both are valid.
Breakdown taken from the book by Gayle L. McDowell, «Cracking the Coding Interview» (available in translation).
Original article.
You must choose one of two bets. In the first option, you must throw a basketball into the hoop in a single shot. If you make it, you get 50 thousand rubles. In the second option, you need to make two out of three shots, and then you also get the same 50 thousand rubles. Which of these options would you prefer? Would your skill at shooting hoops affect your choice?
Expand answer
Let us denote the probability of making the shot as p. On the first shot, your chance of winning 50 thousand rubles equals p. If you miss, you get nothing. On average, you can expect your winnings to be 50 000 ? p.
In the second option, you take three shots and must make the hoop twice to get the money. The probability of success on each individual attempt is still p. The probability of a miss on any attempt equals 1 – p.
In the second option there are 23, or 8, possible scenarios. Let's list them in a table. The symbol ? means that you made the shot, an empty space indicates that you missed.
The first scenario refers to the situation where you completely fail the game. You missed all three shots. The probability of this outcome is 1 – p multiplied by itself three times. Of course, in this case you get no money.
| First shot | Second shot | Third shot | Probability | Did you win 50 thousand rubles? |
| (1 – p)3 | No | |||
| ? | p(1 – p)2 | No | ||
| ? | p(1 – p)2 | No | ||
| ? | ? | p2(1 – p) | Yes | |
| ? | p(1 – p)2 | No | ||
| ? | ? | p2(1 – p) | Yes | |
| ? | ? | p2(1 – p) | Yes | |
| ? | ? | ? | p3 | Yes |
In four of the eight scenarios you win money. In three of them you miss once. These scenarios have probability p2(1 – p). In one case you make all three shots, with probability p3. Add all these probabilities together. Three times p2(1 – p) can be represented as 3p2 – 3p3. Add p3 to this sum, and you get 3p2 – 2p3. The expectation is 50 000 ? (3p2 – 2p3).
Which option is better for you?
Expectation for the first option: 50 000 ? p.
Expectation for the second option: 50 000 ? (3p2 – 2p3).
You might be a complete novice at basketball (p roughly equal to 0) or a master shooter playing in the NBA. As a reference, let's do something you wouldn't do in an interview if given this problem: translate the formula into a spreadsheet and build a graph. This graph shows how the expected winnings change depending on p.
The straight diagonal line reflects the first betting option, the S-shaped curve — the second. The first option is better for you if your chances of making the hoop are below 50%. Otherwise you should choose the second option.
This is quite explainable. A poor player cannot hope to win under either option. He must rely solely on blind luck, which will obviously most likely happen once rather than twice. Therefore a poor player is better off choosing the first option. A very good player should win under either bet, although there is a small chance that on a single shot he will miss. Two out of three shots better reflect his level of skill, and therefore he will want to choose this option. There is a legal principle: if you are guilty, you want your case heard by a jury (because anything can happen); if innocent, it is better for you that your case be heard by a single judge.
If you have followed the reasoning this far, the interviewer will ask you the following question: what value of p would make you switch from one option to the other? To answer this question, equate the winning probabilities of both bets. You get the skill level at which the choice of bet can be made by flipping a coin.
p = 3p2 – 2p3
Divide both sides of the equation by p:
1 = 3p – 2p2,
and then you get
2p2 – 3p + 1 = 0.
Having reached this point, you can simply solve this quadratic equation, mentally thanking your school math teacher. The interviewer will note not only your knowledge of the material, but also how swiftly you perform these calculations. You know that p — the probability — must be between 0 and 1. It's best to try a reasonable value: «Okay, I need a number between 0 and 1. Let's try 0.5». Such an answer will work.
Breakdown taken from the book «Are You Smart Enough to Work at Google?».
Original article.
Imagine a triangle made up of numbers. One number is at the apex. Below it are two numbers, then three, and so on down to the bottom row. You start at the apex, and you need to descend to the base of the triangle. On each move you can descend one level and choose between the two numbers below your current position. As you move, you «collect» and sum up the numbers you pass through. Your goal — is to find the maximum sum obtainable from the various routes.
What algorithm would you propose? What would its complexity be, and can a better option be proposed?
Expand answer
Let's consider various methods of solving this.
The first thing that comes to mind is to use recursion and enumerate all paths from the apex. When we descend one level, all the available numbers below form a new, smaller triangle, and we can run our function again for the new subset, and so on until we reach the base.
def golden_pyramid(triangle, row=0, column=0, total=0):
global count
count += 1
if row == len(triangle) - 1:
return total + triangle[row][column]
return max(golden_pyramid(triangle, row + 1, column, total + triangle[row][column]),
golden_pyramid(triangle, row + 1, column + 1, total + triangle[row][column]))
As we can see, at the first level we run our function twice, then 4, 8, 16 times, and so on. In the end we get algorithm complexity of 2N, and, for example, for a 100-level pyramid we would already need around ?1030 function calls. That's quite a lot.
What if we try to use the principle of dynamic programming and break our problem into a set of small subproblems, whose results we then accumulate. Try looking at the triangle upside down. Now consider the second level (that is, the second-to-last from the base). For each cell we can decide what the best choice would be in our small three-element triangles. Choose the best one, add it to the cell in question, and record the result. In this way we get our triangle again, but one level lower. We repeat this operation again and again. As a result we need (N-1)+(N-2)+…2+1 operations, and the algorithm's complexity is N2.
def golden_pyramid_d(triangle):
tr = [row[:] for row in triangle] # copy
for i in range(len(tr) - 2, -1, -1):
for j in range(i + 1):
tr[i][j] += max(tr[i + 1][j], tr[i + 1][j + 1])
return tr
User gyahun_dash wrote an interesting implementation of the DP method described above in his solution "DP." He used reduce to iterate over pairs of rows, and map to process each of them.
from functools import reduce
?
def sum_triangle(top, left, right):
return top + max(left, right)
?
def integrate(lowerline, upperline):
return list(map(sum_triangle, upperline, lowerline, lowerline[1:]))
?
def count_gold(pyramid):
return reduce(integrate, reversed(pyramid)).pop()
Player evoynov used binary numbers to enumerate all possible routes, represented as a sequence of 1s and 0s, in his solution "Binaries." And this is a vivid example of the complexity of an algorithm with recursion and enumeration of all routes.
def count_gold(p):
path = 1 << len(p) res = 0 while bin(path).count("1") != len(p) + 1: s = ind = 0 for row in range(len(p)): ind += 1 if row > 0 and bin(path)[3:][row] == "1" else 0
s += p[row][ind]
res = max(res, s)
path += 1
return res
And, so it's not boring, let's look at a light brain-teaser from user nickie and his one-liner "Functional DP," which is formally only two lines long. Of course, this solution belongs to the "Creative" category. I don't think the author would use something like this in production code. But just for fun, why not.
ount_gold=lambda p:__import__("functools").reduce(lambda D,r:[x+max(D[j],D[j+1])
for j,x in enumerate(r)],p[-2::-1],list(p[-1]))
That's all for today. Share your ideas and thoughts.
Thanks to CheckiO for an interesting problem.
Original article.
You are given two words or phrases, and your task is to check whether they are anagrams.
An anagram is a word game in which, by rearranging the letters of a word or phrase, we get another word or phrase. Two words are anagrams if one can be obtained from the other by rearranging the letters.
Show the answer
So, we need to compare two phrases. First we need to "process" them: select only the letters and convert them to lowercase. Also, at this step we can convert the string into an array. Let's factor this procedure out into a separate function.
def sanitize(text):
return [ch.lower() for ch in text if ch.isalpha()]
Or, if you care about memory and prefer generators:
def sanitize(text):
yield from (ch.lower() for ch in text.lower() if ch.isalpha())
Or if you love the functional programming style:
sanitize = lambda t: map(str.lower, filter(str.isalpha, text))
Next we need to count each letter in the text, and if the counts for the two words/phrases being checked match, then they are anagrams. Let's assume we only use English letters. Then we can use an array of 26 elements to keep the count.
def count_letters(text):
counter = * 26
for ch in text:
counter[ord(ch) - ord("a")] += 1
return counter
Honestly, this looks like code written in C, not Python. Besides, we're rigidly tied to the English alphabet. Let's replace the list with a dictionary.
def count_letters(text):
counter = {}
for ch in text:
counter[ch] = counter.get(ch, 0) + 1
return counter
Already better, but Python's well-known motto says — "Batteries included." And the Counter class lets us simply count the letters in the text.
from collections import Counter
def count_letters(text):
return Counter(text)
I think you can already see that our separate count_letters function is no longer really needed, and the final solution can be written like this:
from collections import Counter
def sanitize(text):
yield from (ch.lower() for ch in text.lower() if ch.isalpha())
def verify_anagrams(first, second):
return Counter(sanitize(first)) == Counter(sanitize(second))
When I solved this problem for the first time, I didn't use counters. Instead, I converted the text into some universal form for permutations. Of course, I mean a sorted form. If we sort the strings and compare them, it's essentially the same as counting the elements of an array. And since in our problem the text contains only letters and spaces, we can use a trick:
def verify_anagrams(first, second):
return "".join(sorted(first.lower())).strip() == "".join(sorted(second.lower())).strip()
As you can see, with one flick of the wrist we can turn this function into a one-liner (just for fun):
verify_anagrams=lambda f,s,p=lambda x: "".join(sorted(x.lower())).strip():p(f)==p(s)
So that's the story about anagrams.
Thanks to CheckiO for an interesting problem.
Original article.
Propose an algorithm that zeroes out column N and row M of a matrix if the element at cell (N, M) is zero. Naturally, memory usage and running time need to be minimized.
Show the answer
At first glance the problem seems very simple — just walk through the matrix and, for each zero element, zero out the corresponding row and column. But this solution has one major drawback: at the next step we will run into zeros that we ourselves set. It will be impossible to tell whether we set these zeros ourselves or whether they were originally present in the matrix. Quite soon the entire matrix will become zeroed out.
One way is to create a second matrix containing flags for the original zeros. But then two passes over the matrix would be needed, which would require O(N*M).
Do we really need O(N*M)? No. Since we are going to zero out rows and columns anyway, there is no need to remember the values of those elements. Suppose a zero is located in a cell. This means that row 2 and column 4 need to be zeroed out. But if we are zeroing out this row and column anyway, why remember them?
The code below implements our
продолжение следует...
Часть 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