Lecture
Это продолжение увлекательной статьи про .
...
algorithm. We use two arrays to keep track of all the rows and columns containing zeros. Then we make a second pass and set the zeros based on the array we created.
public void setZeros(int[][] matrix) {
boolean[] row = new boolean[matrix.length];
boolean[] column = new boolean[matrix .length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix .length; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
column[j] = true;
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix .length; j++) {
if (row[i] || column[j]) {
matrix[i][j] = 0;
}
}
}
}
For optimization, a bit array can be used instead of a boolean array.
This analysis is taken from the book by Gayle L. McDowell, "Cracking the Coding Interview" (available in translation).
Original article.
Design an algorithm that finds, in an array, all pairs of integers whose sum equals a given value.
Show the answer
This problem can be solved in two ways. The choice is determined by a trade-off between efficient use of time, memory, or code complexity.
A very simple and (time-)efficient solution — creating a hash table mapping an integer to an integer. This algorithm works by stepping through the entire array. For each element x, the hash table is searched for sum – x, and if the entry exists, (x, sum – x) is output. After that, x is added to the table and the next element is checked.
Let's start with the formulation. If we try to find a pair of numbers whose sum equals z, then the complement will be z – x (the value that needs to be added to x to get z). If we try to find a pair of numbers that sum to 12, the complement to -5 will be the number 17.
Imagine we have a sorted array {-2, -1, 0, 3, 5, 6, 7, 9, 13, 14}. Let first point to the beginning of the array, and last — to its end. To find the complement to first, we move last backward until we find the desired value. If first + last < sum, then a complement to first does not exist. We can also move first toward last. Then we stop if first turns out to be greater than last.
Why does this solution find all complements to first? Because the array is sorted, we check smaller numbers. When first + last is less than sum, there is no point in checking smaller values, they will not help find a complement.
Why does this solution find all complements of last? Because all pairs are formed using first and last. We have found all complements of first, which means we have found all complements of last.
void printPairSums (int[] array, int sum) {
Arrays.sort(array);
int first = 0;
int last = array.length - 1;
while (first < last) {
int s = array[first] + array[last];
if (s == sum) {
System.out.printIn(array[first] + "" + array[last]);
first++;
last--;
} else {
if (s < sum) first++;
else last--;
}
}
}
Excerpt from the book «Cracking the Coding Interview: How to Get a Job at Google, Microsoft or Another Leading IT Company».
Original article.
Suppose you need to design an algorithm that demonstrates a person's circle of acquaintances for a social network. How would you do this, given that the database is very large?
A large database means on the order of a billion registered users and no fewer than 100 billion «friendship» connections between them.
Expand the answer
A good way to solve this problem is to remove constraints and first deal with a simplified version.
First of all, let's forget that we are dealing with millions of users. Let's find a solution for the simple case.
We can create a graph and regard each person as a node, and the existence of a connection between two nodes indicates that the users are friends.
class Person {
Person[] friends;
// Other information
}
When it is necessary to find a connection between people, it is obviously worth using the well-known breadth-first search algorithm.
Why not depth-first? It is very inefficient. Two users might be «neighbours,» but we would have to look through millions of nodes in their subtrees before the connection is found.
When we are dealing with huge services like LinkedIn or Facebook, we cannot store all the data on a single computer. This means that a simple Person data structure will not work — our friends may be on different computers. Thus, we need to replace friend lists with lists of their IDs and work with them as follows:
For each friend ID: int machine_index = getMachineIDForUser(personID).
We move to machine #machine_index.
On that machine, we do: Person friend = getPersonWithID(person_id).
The code below demonstrates this process. We have defined a Server class, which stores the list of all computers, and a Machine class, representing an individual machine. Both classes have hash tables that provide efficient data lookup.
public class Server {
HashMap();
HashMap();
public Machine getMachineWithId(int machinelD) {
return machines.get(machineID);
}
public int getMachineIDForUser(int personID) {
Integer machinelD = personToMachineMap.get(personID);
return machineID == null ? -1 : machineID;
}
public Person getPersonWithID(int personID) {
Integer machineID = personToMachineMap.get(personID);
if (machineID == null)
return null;
Machine machine = getMachineWithId(machineID);
if (machine == null) return null;
return machine.getPersonWithID(personID);
}
}
public class Person {
private ArrayList friendIDs;
private int personID;
public Person(int id) { this.personID = id; }
public int getID() { return personID; }
public void addFriend(int id) { friends.add(id); }
}
public class Machine {
public HashMap persons = new HashMap();
public int machinelD;
public Person getPersonWithID(int personID) {
return persons.get(personID);
}
}
There are several directions for optimization and additional questions worth discussing.
«Traveling» from one machine to another is an expensive operation (in terms of system resources). Instead of moving from machine to machine in arbitrary order, work in batch mode. For example, if five friends «live» on the same machine, first get information about them.
Most often friends live in the same country. Instead of dividing user data by an arbitrary principle, try using information about country, city, state, etc. This will reduce the number of jumps between machines.
In breadth-first search, we set a visited flag for visited nodes and store it in the node class. In our case, this cannot be done. Since many queries run at the same time, this approach would interfere with editing the data. Instead, we can simulate marking nodes using a hash table that stores a node's id and a flag indicating whether it has been visited.
Server failures happen in the real world. How would this affect the project?
How can caching be used?
Do you search to the end of the graph? (The graph could be infinite.) When should you stop?
Some people have more friends than others, which means it is more likely that a connection between you and someone else can be found this way. How can this data be used to choose where to start traversing the graph?
These are just a few of the many questions that may arise when implementing such an algorithm.
Excerpt from the book by Gayle L. McDowell, «Cracking the Coding Interview» (available in translation).
Original article.
Suppose you have a singly linked list with a loop. Its “last” element contains a pointer to one of the elements of this same list, not necessarily the first one. Your task — find the starting node of the loop.
The elements of the list cannot be changed, and only constant memory may be used.
Expand the answer
This problem is a variation of the classic interview question of determining whether a linked list contains a loop. Let's use the «pattern matching» approach.
The simplest way to find out whether a linked list has a loop is to use the runner technique (fast/slow). FastRunner takes two steps per tick, while SlowRunner takes only one. Like two race cars racing on the same track by different paths, they must inevitably meet.
An astute reader might ask: could the fast runner «jump over» the slow one without colliding? This is impossible. Suppose FastRunner jumped over SlowRunner and is now at element i+1 (while the slow one is at i). This means that at the previous step SlowRunner was at point i-1, and FastRunner was at ((i+1)-2)=i-1. Hence, a collision is inevitable.
Let's introduce a notation: k – the length of the linked list in its unrolled form. How do we know when FastRunner and SlowRunner will meet, using the algorithm from part 1?
We know that FastRunner moves twice as fast as SlowRunner. So when SlowRunner enters the loop after k steps, FastRunner will have traveled 2k steps. Since k is substantially greater than the length of the loop, let's introduce the notation K=mod(k, LOOP_SIZE).
At each subsequent step, FastRunner and SlowRunner get one step (or two steps) closer to the target. Since the system is closed, when A moves by q, it becomes q steps closer to B.
We can establish the following facts:
SlowRunner: 0 steps inside the loop.
FastRunner: k steps.
SlowRunner: is k steps behind FastRunner.
FastRunner: is LOOP_SIZE – K steps behind SlowRunner.
FastRunner catches up to SlowRunner at a rate of 1 step per unit of time.
When will they meet? If FastRunner is LOOP_SIZE – K steps behind SlowRunner, and FastRunner catches up to it at a rate of 1 step per unit of time, they will meet after LOOP_SIZE- k steps. At this point, they will be k steps away from the start of the loop. Let's call this point CollisionSpot.
We now know that CollisonSpot is k nodes before the start of the loop. Since K=mod(k, LOOP_SIZE) (or k=K+M*LOOP_SIZE for any integer M), we can say that the start of the loop is k nodes away. If node N-2 nodes is in a loop of 5 elements, then elements 7, 12, and even 397 belong to the loop.
Therefore, both CollisionSpot and LinkedListHead are located k nodes from the start of the loop.
If we save one pointer at CollisionSpot and move another to LinkedListHead, then each of them will be k nodes away from LoopStart. Moving these pointers will cause them to collide — this time after k steps – at the point LoopStart. All we need to do is return this node.
FastPointer moves twice as fast as SlowPointer. After k nodes, SlowPointer ends up in the loop, while FastPointer is at the k-th node of the linked list. This means that FastPointer and SlowPointer are separated from each other by LOOP_SIZE-k nodes.
If FastPointer moves 2 nodes for every single step of SlowPointer, the pointers will get closer with each cycle and will meet after LOOP_SIZE-k cycles. At that point, they will be k nodes away from the start of the loop.
The start of the linked list is located k nodes from the start of the loop. Therefore, if we save the fast pointer at its current position and then move the slow pointer to the start of the linked list, the meeting point will be at the start of the loop.
Let's write the algorithm, using the information from parts 1-3:
Create two pointers, FastPointer and SlowPointer.
Move FastPointer by 2 steps and SlowPointer by one step.
When the pointers meet, move SlowPointer to LinkedListHead, while leaving FastPointer in the same place.
SlowPointer and FastPointer continue to move at their own speeds; the point of their next meeting will be the desired result.
The following code implements the described algorithm:
LinkedListNode FindBegining(LinkedListNode head) {
LinkedListNode slow = head;
LinkedListNode fast = head;
/*Find the first meeting point LOOP_SIZE-k steps along the linked list.*/
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { //Collision
break;
}
}
/* Error - no meeting point, therefore no loop */
if (fast == null || fast.next == null) {
return null;
}
/* Move the slow runner to the start of the list (Head). The fast one remains
at the meeting point.
*Every k steps from Loop Start. If the pointers continue to
move at the same speed, then
* they will meet at Loop Start. */
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
/* Return the start point of the loop. */
return fast;
}
Discussion based on the book «Cracking the Coding Interview: How to Get a Job at Google, Microsoft, or Another Leading IT Company».
Original article.
On an island there is a rule — blue-eyed people are not allowed to be there. A plane leaves the island every evening at 20:00. All the inhabitants gather at a round table every day; each person can see the eye color of the other people, but does not know their own eye color. No one has the right to tell a person what their eye color is. There is at least one blue-eyed person on the island. How many days will it take for all the blue-eyed people to leave?
Expand answer
Let's use the «base case» and «build» approaches. Suppose that there are n people on the island, and c of them are blue-eyed. Thus, we know that c > 0.
Suppose that all the people on the island are sufficiently intelligent. If it is known that there is only one blue-eyed person on the island, then, upon finding that everyone else's eyes are not blue, he will conclude that he himself is the only blue-eyed person, who should leave on the evening flight.
Two blue-eyed people see each other, but do not know what c equals: c = 1 or c = 2. From the previous case, we know that if c = 1, the blue-eyed person can identify himself and leave the island on the first evening. If a blue-eyed person is on the island (c = 2), this means that the person who sees only one blue-eyed person is himself blue-eyed. Both people will have to leave the island that evening.
Let's use the same logic. If c = 3, then these three people will immediately see that there are 2 (or 3) more people with blue eyes on the island. If there had been two such people, they would have left the island the day before. Since blue-eyed people still remain on the island, any person can conclude that c = 3 and that he has blue eyes. All of them will leave that same night.
This pattern can be used for any value of c. Therefore, if there are blue-eyed people on the island, it will take c nights for all of them to leave the island.
Discussion based on the book «Cracking the Coding Interview: How to Get a Job at Google, Microsoft, or Another Leading IT Company».
Original article.
Write code to remove duplicates from an unsorted linked list. You may only use constant memory.
Expand answer
To remove duplicates from a linked list, they first need to be found. A simple hash table is suitable for this. In the solution below, a pass is made through the list, with each element added to the hash table. When a duplicate element is found, it is removed, and the loop continues to run. By using a linked list, the entire task can be solved in a single pass.
public static void deleteDups (LinkedListNode n) {
Hashtable table = new Hashtable();
LinkedListNode previous = null;
while (n != null) {
if (table.containsKey(n.data)) {
previous.next = n.next;
} else {
table.put(n.data, true);
previous = n;
}
n = n.next;
}
}
The given solution requires O(N) time, where N is the number of elements in the linked list.
In this case, we can implement the loop using two pointers: current (traverses through the linked list) and runner (checks all subsequent nodes for duplicates).
public static void deleteDups (LinkedListNode head) {
if (head == null) return;
LinkedListNode current = head;
while (current != null) {
/* Remove all following nodes with the same value */
LinkedListNode runner = current;
while (runner.next != null) {
if (runner.next.data == current.data) {
runner.next = runner.next.next;
} else{
runner = runner.next;
}
}
current = current.next;
}
}
This code requires only O(1) space, but takes O(N2) time.
Discussion based on the book «Cracking the Coding Interview: How to Get a Job at Google, Microsoft, or Another Leading IT Company».
Original article.
Write a method that shuffles a deck of cards. The deck must be perfectly shuffled, i.e., all permutations of the cards must be equally likely. You may use a perfect random number generator.
This is a very popular problem and a well-known algorithm. If you are already familiar with the solution, read on.
Expand answer
Let's solve the problem «head-on». We can pick cards in arbitrary order and place them into a new deck. In effect, the deck is an array, so we need a way to lock individual elements.
Original deck (before choosing 4): /* We choose a random element to place at the beginning of the shuffled deck * We mark the element in the original deck as "blocked", so that * it is not chosen again */ Shuffled deck (after choosing 4): [?] [?] [?] [?] Original deck (after choosing 4): [X]
If we mark an element, what prevents it from being chosen again? One way is to swap the «dead» ( ) and first elements of the deck:
Original deck (before choosing 4): /* We choose a random element to move it to the beginning of the shuffled deck * There is element 1, which will replace the chosen element. */ Shuffled deck (after choosing 4): [?] [?] [?] [?] Original deck (after choosing 4): [X] /* We choose a random element to move it to the beginning * of the shuffled deck. There is element 2, which will replace the just * chosen element */ Shuffled deck (after choosing 3): [?] [?] [?] Original deck (after choosing 3): [X] [X]
The algorithm is easier to implement for a situation where the first k cards are «dead» than for a situation where, for example, the third, fourth, and ninth cards are «dead».
The algorithm can be optimized by combining the shuffled and original decks together.
Original deck (before choosing 4): /*We choose a random element between 1 and 5 and swap it with 1. * In this example we chose element 4. * After this, element 1 is "dead" */ Original deck (after choosing 4): /* Element 1 is "dead". We choose a random element to swap with * element 2. In this example let's say we choose element * 3.*/ Original deck (after choosing 3): /* Repeat. For all i between 0 and n-1 swap a random element j * (j >= i, j < n) and element i. */
This algorithm is easy to implement iteratively:
public void shuffleArray(int[] cards) {
int temp, index;
for (int i = 0; < cards.length; i++) {
/*Cards with indices from 0 to i-1 have already been chosen
* (they have been moved to the beginning of the array), so now we
* choose a random card with an index greater than or equal to i
* */
index = (int) (Math.random() * (cards.length - i)) + i;
temp = cards[i];
cards[i] = cards[index];
cards[index] = temp;
}
}
A similar algorithm can be devised on your own as well; it comes up fairly often at interviews. Before an interview, make sure you understand the mechanism behind how it works.
Analysis based on the book «Cracking the Coding Career: How to Get a Job at Google, Microsoft, or Another Leading IT Company».
Original article.
Suppose you've been tasked with developing a web crawler — a program that, roughly speaking, visits pages on the Internet, indexes them, extracts links from them, follows those links, and repeats the process. Question: how do you avoid getting stuck in an infinite loop?
Show answer
First of all, let's ask ourselves: under what conditions could an infinite loop arise in this problem? Such a situation is quite likely, for example, if we consider the World Wide Web as a graph of links.
To prevent looping, we need to detect it. One way is to create a hash table in which, after a page v is visited, hash[v] = true is set.
This kind of solution is applicable when using breadth-first search. Each time we visit a page, we gather all of its links and add them to the end of the queue. If we have already visited a page, we simply ignore it.
Great, but what does it mean to visit a page v? What defines page v: its content or its URL?
If a URL is used to identify a page, you need to be aware that URL parameters can point to a different page. For example, the page www.careercup.com/page?id=microsoft-interview-questions is different from the page www.careercup.com/page?id=google-interview-questions. On the other hand, you can add parameters and the page will not change. For example, the page www.careercup.com?foobar=hello is the same page as www.careercup.com.
You might say: «Fine, let's identify pages based on their content». That sounds right, but it doesn't work very well. Suppose the careercup.com homepage displays some randomly generated content. Every time you visit the page, the content will be different. Can such pages be called different? No.
In reality there is no perfect way to identify a page, and the task turns into a puzzle.
One way to solve it is to introduce a criterion for evaluating page similarity. If a page is similar to another page, we lower the priority of traversing its child elements. For each page, a kind of signature can be created based on fragments of content and the URL.
Let's see how such an algorithm might work.
Suppose there is a database storing a list of items that need to be checked. On each iteration we select the page with the highest priority:
We open the page and create a signature for the page, based on certain subsections of the page and its URL.
We query the database to see when a page with this signature was last visited.
If an item with such a signature was checked recently, we assign it a lower priority and return the page to the database.
If the item is new, we crawl the page and add its links to the database.
Such an algorithm will not allow us to fully crawl the World Wide Web, but it will prevent infinite loops. If we need the ability to fully crawl a page (suitable for small intranet systems), we can simply lower the priority so that the page still gets checked eventually.
This is a simplified solution, but there are many others that can also be used. In fact, the discussion of this problem can transform into a different problem altogether.
Analysis taken from Gayle L. McDowell's book «Cracking the Coding Interview» (available in translation).
Original article.
You have a glass jar containing small marbles, and at any time you can determine how many there are. You and a friend are playing the following game: each of you, in turn, takes 1 or 2 marbles from the jar. The player who takes the last marble wins. What is the best strategy in this game? Can you predict at the very beginning who will win?
Show answer
The number of marbles gets smaller and smaller with each move, and eventually there will be very few left. That's when the strategy becomes completely clear.
Let's assume that only one marble remains in the jar and it's now my turn to take one. By taking the last marble, I win.
I also win if two marbles remain, because I can take both.
But three remaining marbles are a bad option for me. I'll have to leave either one or two marbles, and that's when my opponent will immediately take advantage of such a gift.
Four and five marbles are a good option. I can leave my opponent with the unfortunate (for them) number three.
Well, now it's all clear. A number that is divisible by three means a loss for me: 3, 6, 9, 12… are bad options when it's my turn to move. Everything else (1, 2, 4, 5, 7, 8…) is fine.
So how can this be used in the game? We start with a large but unknown number of marbles. Let's divide it by 3. If the number divides evenly, that's a losing situation for us. In that case, try not to go first. If your opponent offers to flip a coin to decide who goes first, show some "generosity" and let them take the first move. But if you're lucky and the number of marbles is not divisible by three, and you go first, then the winning strategy is simple: on each move, take as many marbles as needed so that the jar is left with a losing number. Say, if you start with 304 marbles (great for you), you take one, leaving your opponent with an unlucky 303. Do this on every move, and eventually they'll be left with three marbles. This strategy guarantees you a win.
Moreover, this strategy will absolutely reliably lead you to victory, regardless of how the other player acts (unless, in a fit of anger, they smash the jar on the floor). They have to take one or two marbles from the remaining number, which is unlucky for them. This always allows you, on your next move, to leave a "lucky" number of marbles in the jar.
But what if you start with an unlucky arrangement? You're doomed to lose if the other player applies the strategy described above themselves. However, there's no tragedy yet. Your opponent might not know about this strategy, or might simply miscalculate. Anyone who plays without a strategy will almost certainly sooner or later give you the chance to move to a happy (for you) number, since two-thirds of all numbers are winning for you. A person who knows the optimal strategy but makes even a single mistake during the game is doomed: they are no longer in control (of course, provided you don't make such a mistake yourself).
But, in fact, what you're actually being asked is whether it's possible to predict who will win. Yes, if both players know the theory of this game perfectly. Determine whether the initial number of marbles is "lucky." If so, the first player always wins. And vice versa.
But we live in the real world. Who would dare to predict the final outcome?! Even if both players know the correct strategy, the more marbles there are in play, the higher the chance of a mistake. The odds favor whoever doesn't make a mistake while following the winning strategy.
There are also variants of this question, for example: the one who takes the last marble loses. What should you do in this case? Write the "unlucky" number of marbles as 3N+1, and then apply the same strategy.
Analysis based on the book "Are You Really Smart Enough to Work at Google?".
Original article.
Original article.
There are N companies, and you want them to merge and form one large company. How many different ways can you do this? An acquisition can be considered a special case of a merger, where A acquires B and B acquires A count as two different ways. Equal mergers are also possible.
Show answer
With a strict interpretation of the term "merger," two companies give up their former individual identities and merge into a new entity with a new brand. For instance, the pharmaceutical giants Glaxo Wellcome and SmithKline Beecham merged in 2000, giving rise to the pharmaceutical colossus GlaxoSmithKline. (Also, as you correctly guessed, both parent companies were themselves the result of numerous prior mergers).
Taking into account the egos of chief executives, true mergers are rare. A merger requires that the negotiating parties have roughly equal power. It's much more common to see situations where the leadership of one company has an advantage and therefore doesn't let the leaders of the weaker company forget it. So the deal is essentially more like an acquisition — a form of combination in which company A swallows company B, after which B ceases to exist as a separate organization (though it is often retained as a brand). An example of such a development would be Google's 2006 acquisition of YouTube.
In this regard, mergers are symmetric, since there is only one way for two companies to merge as equals. An acquisition, however, is asymmetric: one company is the acquirer, and the other is the acquired. The scenario in which Google bought YouTube is not equivalent to the scenario in which YouTube would have acquired Google.
Most people who don't work in investment banking don't see much difference between mergers and acquisitions. As a result, they loosely call any corporate combination a "merger." It follows that you need to ask the interviewer what they mean by "merger" in their question. Fortunately, most of the reasoning given below holds regardless of what clarification the interviewer provides.
Start with acquisitions, since they're more common (and also somewhat easier to explain). We can use an analogy: imagine the companies as checkers pieces, and acquisitions as moves in an ongoing game. Start with the number of players being N. A move in the game consists of placing one piece on top of another, meaning the top piece has "acquired" the bottom one. After an acquisition, you can use "tall" pieces the same way "kings" are used in a regular game.
Each move reduces the number of pieces (both regular and "tall" ones) by one. Eventually you'll stack all the pieces into a single pyramid, creating the tallest possible combination. To reach the goal of this game, you'll need N-1 moves, resulting, in the end, in a pyramid consisting of N pieces. How many different scenarios can lead to this outcome?
The simplest case involves two companies, where company A can acquire company B, or B can acquire A. In this case there are two possible scenarios.
If there are three companies, you first need to decide which company will acquire another company first, and which one specifically. There are six possible options for this first acquisition, which can be represented as six possible pairs made up of the three participants (AB, AC, BA, BC, CA, and CB). After the initial acquisition, you're left with two companies. Now the situation is exactly the same as the one described in the previous paragraph. Therefore, the number of possible acquisition sequences with three companies is 6 x 2 = 12.
If there are four companies, you get 12 possibilities for the first acquisition: AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, and DC. As you've probably already figured out, if with three companies there are 12 options at this stage, then with four companies there are 12 x 6 x 2, that is, 144 acquisition scenarios.
Let's generalize. With N companies, the number of first acquisitions is N x (N-1).
This simply means that any of the N companies can become the first acquirer, and any of the remaining (N-1) companies can be the first to be acquired. After the first acquisition, N-1 separate companies remain, and there are (N-1) x (N-2) possibilities for a second acquisition. After that, (N-2) companies remain, along with (N-2) x (N-3) possible acquisitions. We keep multiplying the ever-decreasing number of possible acquisitions, continuing until we reach the last acquisition, where 2 x 1 possibilities remain. It's easy to see that, using factorial notation, the product can be expressed as N! x (N-1)!, which is exactly the number of possible acquisition scenarios.
What happens if we consider not acquisitions, but actual mergers? With this approach, we can take the results of the analysis above for each of the N-1 acquisitions and divide it by 2. It follows that the number of valid merger variants equals N! x (N-1)!, divided by 2^(N-1).
And finally, if a merger can mean either a merger or an acquisition, you simply add both answers together.
Analysis based on the book "Are You Really Smart Enough to Work at Google?".
Original article.
What is the minimum set of coins needed to be able to give any amount of change from 1 to 99 cents? Available coin denominations: 1, 5, 10, 25, 50 cents and 1 dollar.
Show answer
There are two ways to interpret this question. They lead to different answers, so it's best to ask the interviewer what they mean (or to prepare both variants of the answer). One interpretation is to find the smallest assortment of coins that allows giving exact change from 1 to 99 cents. Let's call such a set a universal change-making set. How many coins would be in this set?
The problem uses US coins. The US dollar (USD, $), equal to 100 cents. In circulation there are coins – penny (1 cent), nickel (5 cents), dime (10 cents), quarter (25 cents), half dollar (50 cents), as well as 2 and 1 dollar coins.
Imagine you are a shop owner and a person meticulous by nature, who likes to start the day with enough coins in the till to be able to give change on the first purchase of the day, regardless of the amount. What is the minimum number of coins you should have in your till so that you can always give change?
The answer is easy, since American coins are specially chosen by denomination to make giving change easier. Each coin is worth at least twice as much as the previous one. This means you can use the following algorithm to give change equal to X cents.
If the required change X is 50 cents or more, put down a 50-cent coin and subtract that amount from X.
If X is now 25 cents or more, put down a quarter (25 cents) and subtract it from X.
Divide the new value of X by 10 and take the integer part. Put that many dimes into the till.
If the remaining amount is 5 cents or more, put a nickel into the till and subtract the remainder from the amount.
Divide the remaining amount into cents and put that many 1-cent coins into the till.
This rule not only works, but also lets you give any amount of change using the minimum possible number of coins. You could, for example, skip the first line and use two quarters instead of one 50-cent coin, but that means you would need an extra coin.
Want to give any amount of change with the minimum number of coins? Always keep on hand one 50-cent coin, one quarter, one nickel, with each of these coins needed in only a single copy. You may also need two dimes (say, if you need to give change equal to 20 cents) and no more than four 1-cent coins (to give 4 cents). This means you should have nine coins totaling 1.04 dollars. This is a universal set that lets you give any amount of change. Obviously, to give change from a dollar, you would never need to use all nine coins at once.
An alternative interpretation of the question is this: what is the smallest number X such that you would never need more than X coins to give change. In fact, this is asking, for which amount of change would you need the most coins. Perhaps you think that you would need the most coins for change equal to 99 cents? You are right. For that you would need eight coins, namely one 50-cent coin, a quarter, two dimes, and four 1-cent coins. Eight coins would also be needed for change equal to 94 cents (compared to the previous set, instead of one dime you would use a nickel).
This question is considered quite tricky and is used in psychological creativity tests.
Excerpt from the book «Are You Really Smart Enough to Work at Google?».
Original article.
You have 25 horses. How many races do you need to hold to determine the three fastest among them? You cannot use a stopwatch. Only five horses can take part in each race.
Expand the answer
You can start your answer by clarifying: ask the interviewer whether the «fastest horse» should be considered the one that wins a particular race. Although this assumption does not hold at an actual racetrack, it greatly simplifies the problem: suppose that if A beats B in one race, then A is objectively and indisputably a faster horse than B. If you are told that this assumption may be used, then indeed the fastest horse will win in an individual race.
The first thing that comes to mind — you need at least five races. Any of the horses could be among the top three. Besides, you would need to hold races for all 25 horses. Five races of five horses each — there is no other way.
Logical. Second conclusion: five races are not enough. Divide the 25 horses into groups of five, and hold races. In each race, one horse will compete against four others. Say, in one of the races, the horses finish in the following order.
Although Ridonna won this race, you cannot conclude from its results that she is the fastest horse out of the 25, or even that she is among the top three. To clarify this last statement, let's use an extreme case: imagine that all the slowest horses in the other races are faster than Ridonna (who might, in the overall ranking, place only 21st out of 25 possible).
Did we learn anything from this race? Of course we did. We learned how to rank these five particular horses. We also learned that we can cross Veronika and Almadena off the list of contenders for the top three. Since they did not place in the top three in this race, they cannot be among the three fastest of the 25 horses either.
The same can be said of the horses that placed fourth and fifth in the other races. In each race of five horses, two are eliminated from further consideration. After the first five races, we can cross off 10 horses, leaving 15 as contenders for the title of the three fastest.
The sixth race should compare the horses that performed well in the first five races. It seems reasonable to hold a race for the winners of the first five races. Let's do that. Let's take Ridonna from the race described above and send her to compete with the winners of the other races. The final result might look like this.
Again, we can reasonably cross Princess Gita and Sikarel off the list of contenders for the win. They obviously, judging by the results of this race, cannot be among the three fastest of the 25. We also learn that the fastest horse is Fidana, since she beat all the other horses that were first in the preceding races. If the question were to determine the single fastest horse out of the 25, we would already have the answer. It is Fidana.
However, we need to determine the three fastest. Among the contenders for the win, we can cross off not only Princess Gita and Sikarel, but also all the horses that they beat in the first races. The horses that they beat were slower, and we already know that the winners of two of the races on the list have been crossed off.
Now let's deal with Flavia. Since she came in third in this race, all the horses that she beat in the first race are also excluded from further consideration.
Now let's move on to Ridonna. Based on the last race, she is, at best, the second horse overall. This leaves open the question of Bavkida, who came in second in the first round, after Ridonna, but overall she could be the third fastest of all. (In this case, the list of winners would be: Fidana, Ridonna, Bavkida).
Kharceya, who came in third in the first race, which Ridonna won, is now out of further contention.
The two horses that came in second and third after Fidana in the first race are still contenders. It is possible that these horses are faster than Ridonna, but they never raced against her.
So, six horses remain. Of these, three were first in the last race: two who came in second and third in the race with the overall winner, and one who came in second in her own first race, losing only to the horse that placed second overall.
We already know that the fastest of all the horses is Fidana. For this reason, there is no point in racing her again. Only five horses remain. Naturally, we will hold a race for them in the seventh and final round. The first two horses that win here will end up taking second and third place.
A small change to the rules. Start with a qualifying round of five races, in which all 25 horses compete. Then choose the championship race option: only the winners of the qualifying races will be admitted to the next round. The horse that comes in first in the second race will become the overall winner.
Excerpt from the book «Are You Really Smart Enough to Work at Google?».
Original article.
A short brain-teaser. Research results show that 70% of people like coffee, while 80% like tea. What are the upper and lower bounds on the proportion of people who like both coffee and tea?
Show the answer
Not all tea lovers feel positively about coffee; not all cat lovers tolerate dogs, and not all fans of one team are simultaneously supporters of another. Draw a Venn diagram on a board, or at least imagine one mentally. It is a rectangle whose area corresponds to the number of participants in the study. Let the larger part of this rectangle correspond to 70% — the number of respondents who like coffee, and a small circle inside represent the 30% of people who evidently do not like coffee. (The total area of the whole rectangle should equal 100%, although achieving such precision in the picture is not required.)
80% of respondents like tea. If we show this percentage as a circle, it will overlap the parts representing coffee lovers and those who dislike this drink. (The group of coffee lovers is simply not large enough to contain all those who like tea.) To set the upper bound on the number of people who like both drinks, let us assume that every coffee lover also likes tea.
Therefore, the circle representing the 80% of tea lovers can be split into two parts: those who like both tea and coffee (70%) and those who like only tea (10%). 70% is the upper bound. To get the lower bound, let's shift the circle for tea lovers so that it covers the circle of those who don't like coffee. Now everyone who dislikes coffee (30%) likes tea. This leads to 80 – 30 = 50% of people who like both tea and coffee. This figure is the lower bound.
Analysis based on the book "Are You Really Smart Enough to Work at Google?".
Original article.
A problem that must be solved without a calculator or computer, with only a pencil and paper on hand. How many zeros are at the end of 100 factorial?
Show the answer
The factorial of one hundred is written as 100! This is the product of all natural numbers up to and including one hundred. Sometimes the factorial is written like this:
100 x 99 x 98 x 97 x … x 4 x 3 x 2 x 1
To answer the question of the problem, you don't need to find the result of the multiplication. You are expected only to determine the number of zeros at the end of the product, without knowing exactly what it will be. To solve this problem, several rules need to be formulated. You already know one of them. Look at the following expression.
387 000 x 12 900 = 5 027 131 727
Doesn't it seem like something's funny here? After all, when multiplying two round numbers, that is, ones that end in zeros, it is impossible to get a non-round number. This would violate the law of conservation of trailing zeros (a law I just made up, but which is nonetheless true). The product will always inherit the zero endings of its factors. Here are a few correct examples of this:
10 x 10 = 100
7 x 20 = 140
30 x 400 = 12 000
Of the factors of 100 factorial, ten end in zero: 10, 20, 30, 40, 50, 60, 70, 80, 90 and 100 (which ends in two 0s). This already gives at least eleven trailing zeros, which 100! is bound to inherit.
Warning: following only this rule sometimes prompts some candidates to state in their answer that 100 factorial ends in eleven zeros. Such an answer is incorrect. Sometimes you can multiply two numbers that don't end in zero and get a product that has one or more zeros at the end. Here are a few examples of this kind:
2 x 5 = 10
5 x 8 = 40
6 x 15 = 90
8 x 125 = 1000
All but the last pair are among the hundred factors of 100 factorial. So your work isn't done. Now we come to the law of "hot dogs and buns." Imagine a situation where, at a picnic, some people bring hot dogs (in packs of ten), others bring buns (packed eight to a pack), and some bring both. There is only one way to determine how many hot dogs can be made from these products. Count the hot dogs, count the buns, and pick the smaller of the two numbers.
The same law should be used in answering our question. For this we need to replace "hot dogs" and "buns" with "factors of 2" and "factors of 5."
In each of the equations above, a number divisible by 2 is multiplied by a number divisible by 5. Factors of 2 and 5, when multiplied together, "jointly" produce a perfect ten, which adds one more zero to the overall product. Look at the last example, where, seemingly out of thin air, three zeros appear at the end.
8 x 125 = (2 x 2 x 2) x (5 x 5 x 5)
= (2 x 5) x (2 x 5) x (2 x 5)
= 10 x 10 x 10
= 1000
So we need to pair up twos and fives. Let's take, for example, the number 692 978 456 718 000 000.
It ends in six zeros. This means it can be written as follows:
692 978 456 718 x 10 x 10 x 10 x 10 x 10 x 10,
or like this:
692 978 456 718 x (2 x 5) x (2 x 5) x (2 x 5) x (2 x 5) x (2 x 5) x (2 x 5).
The first part, 692 978 456 718, is not divisible by 10. Otherwise it would end in zero, and this part could be reduced by another factor of 10. Moreover, there are six factors here equal to 10 (or 2 x 5), which corresponds to the six trailing zeros of the number 692 978 456 718 000 000. Convincing, isn't it?
This gives us a reliable system for determining the number of zeros at the end of any large number. Pick out the factors of 2 and 5. Pair them up and multiply them: (2 x 5) x (2 x 5) x (2 x 5) x … The number of pairs of twos and fives equals the number of trailing zeros. Ignore everything left over on the left.
In general, on the left you will be left with a two or a five for which no pair was found. Usually these are twos. Moreover, when dealing with a factorial, it's always twos. (Factorials have more even factors than factors divisible by 5.) Therefore the bottleneck is the number of fives. It follows that the question can be rephrased differently: how many times can 100! be divided evenly by 5?
This arithmetic operation can easily be done even in your head. In the range from 1 to 100 there are 20 numbers divisible by five: 5, 10, 15, …, 95, 100. Note that 25 gives 2 factors equal to 5 (25 = 5 x 5), and moreover this group also contains three more numbers that include 25: 50, 75 and 100. In total, this adds four more fives, for 24 in total. 24 factors of five give 24 pairs with an equal number of twos, resulting in 24 factors of 10 (leaving plenty of twos on the left with no pair). Thus, 100! ends in 24 zeros.
If you're curious to know the exact answer, the value of 100 factorial is:
93 326 215 443 944 152 681 699 238 856 266 700 490 715 968 264 381 621 468 592 963 895 217 599 993 229 915 608 941 463 976 156 518 286 253 697 920 827 223 758 251 185 210 916 864 000 000 000 000 000 000 000 000.
Analysis based on the book "Are You Really Smart Enough to Work at Google?".
Original article.
Propose an algorithm for finding the largest sum of a contiguous sequence from an array of integers, both positive and negative.
Show the answer
This is a fairly difficult but very popular problem. Let's solve it using an example array:
2 3 -8 -1 2 4 -2 3
If we regard the array as containing alternating sequences of positive and negative numbers, then it makes no sense to consider parts of positive or negative subsequences. Why? By including part of a negative subsequence, we decrease the total value of the sum, so we should not include part of a negative subsequence at all. Including part of a positive subsequence seems even stranger, since including this subsequence in full will always give a larger result.
We need to come up with an algorithm that treats the array as a sequence of negative and positive numbers arranged alternately.
Any number can be represented as the sum of subsequences of positive and negative numbers. In our example, the array can be reduced to:
5 -9 6 -2 3
We still don't have a great algorithm, but now we understand better what we're dealing with.
Let's consider the previous array. Do we need to account for the subsequence {5, -9}? Summing them gives -4, so there's no point including both of these numbers, {5} alone is sufficient.
In what cases does it make sense to account for negative numbers? Only if it allows us to join two positive subsequences, each of whose sum is greater than the contribution of the negative value.
Let's proceed, starting from the first element in the array.
5 is the largest sum we've encountered so far. Thus, maxsum = 5 and sum = 5. Then we see the next number (-9). If we add this number to sum, we get a negative value. There's no point extending the subsequence from 5 to -9 (-9 reduces the total sum to 4). So we simply reset the value of sum.
Now we've reached the next element (6). This subsequence is larger than 5, so we update the values of maxsum and sum.
Then we look at the next element (-2). Adding this number to 6 makes sum = 4. Since this isn't the final value, our subsequence looks like {6, -2}. We update sum, but not maxsum.
Finally we look at the next element (3). Adding 3 to sum (4) gives us 7, so we update maxsum. The maximum sequence has the form {6, -2, 3}.
When we work with a reversed array, the logic remains the same. The following code implements this algorithm:
public static int getMaxSum(int[] a) {
int maxsum = 0;
int sum = 0;
for (int i = 0; i < a.lenght; i++) {
sum += a[i];
if (maxsum < sum) {
maxsum = sum;
} else if (sum < 0) {
sum = 0;
}
}
return maxsum;
}
What if the array consists of negative numbers? How should we proceed in that case? Consider the simple array {-3, -10, -5}. There are three different possible answers:
-3 (if we assume the subsequence cannot be empty);
0 (the subsequence can have zero length);
MINIMUM_INT (for the error case).
Our code used the second answer (sum = 0), but there is no single unambiguous "correct" solution to this question. Discuss it with the interviewer.
This analysis is based on the book "Cracking the Coding Interview: How to Get a Job at Google, Microsoft, or Another Leading IT Company".
Original article.
Write a program to calculate the median value in a stream of numbers, dynamically tracking new incoming numbers obtained randomly.
Expand the answer
One possible solution is to use two heaps of different priorities: a max heap (maxHeap) for values above the average, and a min heap (minHeap) for values below the average. This allows us to split the elements roughly evenly, with two values — the tops of the heaps. Finding the average value is now very simple.
What does "roughly evenly" mean? "Roughly" means that with an odd number of numbers, one of the heaps will have an extra number. We can formulate:
if maxHeap.size() > min.Heap.size(), then heap1.top() will be the median value; if maxHeap.size() == minHeap.size(), then the median value will be the average of maxHeap.top() and min.Heap.top().
In the balancing algorithm, we guarantee that maxHeap will always contain one extra element.
The algorithm works as follows. If the new value is less than or equal to the average, it is placed in maxHeap; otherwise it goes into minHeap. The sizes of the heaps may be equal, or maxHeap may have one extra element. This requirement is easy to satisfy by moving an element from one heap to the other. The median value is found at the top. Updates take O(log(n)) time.
private Comparator maxHeapComparator;
private Comparator minHeapComparator;
private PriorityQueue maxHeap, minHeap;
public void addNewNumber(int randomNumber) {
/*Note: addNewNumber maintains the condition that
*maxHeap.size() >= minHeap.size() */
if (maxHeap.size() >= minHeap.size()) {
if ((minHeap.peek() != null) &&
randomNumber > minHeap.peek()) {
maxHeap.offer(minHeap.poll());
minHeap.offer(randomNumber);
} else {
maxHeap.offer(randomNumber);
}
} else {
if(randomNumber < maxHeap.peek()) {
minHeap.offer(maxHeap.poll());
maxHeap.offer(randomNumber)
}
else {
minHeap.offer(randomNumber);
}
}
}
public static double getMedian() {
/*maxHeap is always at least as large
*as minHeap. If maxHeap is empty, minHeap is also empty. */
if (maxHeap.isEmpty()) {
return 0;
}
if(maxHeap.size() == minHeap.size()) {
return ((double)minHeap.peek()+(double)maxHeap.peek()) / 2;
} else {
/* If maxHeap and minHeap have different sizes, then
* maxHeap has one extra element.
* Return the top of the maxHeap heap */
return maxHeap.peek();
}
}
This analysis is based on the book "Cracking the Coding Interview: How to Get a Job at Google, Microsoft, or Another Leading IT Company".
Original article.
It's raining, and you need to get to your car, which is parked at the far end of the parking lot. Would you run to it or not, if your goal is to get as little wet as possible? How would you behave if you have an umbrella?
Expand the answer
To answer this question, you need to reconcile two conflicting facts that affect your reasoning. Here are the arguments in favor of running: the longer you're out in the rain, the more drops will fall on your head, and the wetter you'll get. If you run, you'll reduce your exposure time to the rain and thereby stay drier.
But there's also an argument against running. When moving horizontally, you also run into raindrops that would not have hit you if you had stayed in place. A person running in the rain gets wetter than someone standing in the same rain.
This is a weighty argument, but in this particular case it simply doesn't apply. You need to get to your car, and there's nothing you can do about that. Imagine you're dashing across the parking lot at infinitely high speed. Your senses have also become infinitely sharp, so you don't bump into other cars. Time seems to stand still for you. It's like a slow-motion effect. The raindrops seem not to move, but "hang" in the air. During this rapid dash, not a single drop will fall on your head, back, or sides. But to reach the car, you need to "punch" a kind of tunnel through the rain. Therefore the front part of your clothing will absorb every drop located along the path from shelter to the car.
When you move at a normal speed, you're bound to encounter those same drops, or more precisely, their successors. At normal speed, your head will also get its share of drops. The number of raindrops you encounter depends on the length of your horizontal path, as well as on the time it takes you to cover it. The length of the path in this problem is a
продолжение следует...
Часть 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