This blog contains the my collection of top 10 puzzles asked in data science/analyst interviews. I thought of making a catalog so that they can be useful to one who is preparing for the interview.
So lets start this "Puzzling" journey.
1. Ant and Triangle Problem
Three ants are sitting at the three corners of an equilateral triangle. Each ant starts randomly picks a direction and starts to move along the edge of the triangle. What is the probability that none of the ants collide?
Solution
Let’s start by reversing the way the riddle is asked and find the probability that there willnot be a collision instead. When will this happen?
Well, what if all of the ants are walking in the same direction? Then there will never be a collision between any of the ants because they are all walking in the same direction. And, the only time they will be walking in the same direction is if they are all walking either counter-clockwise around the triangle, or clockwise around the triangle. So, there are only two scenarios in which a collision will not happen between the ants.
Now that we know that there are only two scenarios where the ants will not collide, we have to ask ourselves how many different ways are there for the ants to move on the sides of the triangle? Well, each ant can move in 2 different directions. Because there are 3 ants, this means that there are 23 (which equals eight) possible ways that the ants can move. And since we already know that there are only 2 ways in which the ants can avoid collision entirely, this means that there are 6 scenarios where the ants will collide. And 6 out of 8 possible scenarios, means that the probability of collision is 6/8, which equals 3/4 or .75. Thus, the probability of the ants colliding is .75.
2. Crossing the Bridge Puzzle
Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person: 1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge?
Solution :
The solution is to have W(10 mins) carry the torch and begin to cross with any of the others lets say X(1). Each continues at their own pace so in 1 minute X has reached the other side and one of the others can begin to cross say Y(2), when he reaches the other side Z(7) can begin to cross. W and Z will cross the bridge at the same time i.e. at the end of 10th minute.
This solution satisfies the criteria that there are never more than 2 people on the bridge and the torch is always on the bridge whilst someone is crossing. So in that sense it is a neat solution.
3. Burning Rope Problem
A man has two ropes of varying thickness (Those two ropes are not identical, they aren’t the same density nor the same length nor the same width). Each rope burns in 60 minutes. He actually wants to measure 45 mins. How can he measure 45 mins using only these two ropes.
He can’t cut the one rope in half because the ropes are non-homogeneous and he can’t be sure how long it will burn.
Solution :
Take one rope and burn it at both ends.At the same time, burn one end of the other rope. When the first rope is burnt (i.e. 30 minutes), light the other end of the other rope (half of the
remaining 30 minutes gives you 15 minutes) When it burns out, that`s 45 minutes.
4. Heaven’s Gate Problem
You are standing before two doors. One of the path leads to heaven and the other one leads to hell. There are two guardians, one by each door. You know one of them always tells the truth and the other always lies, but you don’t know who is the honest one and who is the liar. You can only ask one question to one of them in order to find the way to heaven. What is the question?
Solution :
Ask one of the guard:" what would the other guard say if i ask him which way is the hell?"
And whatever answer he gives that is the way to heaven.
If you end up asking the question to the truthful one, he will tell the true and he knows the other guard is going to lie so he will so the way to heaven.
If you end up asking the question to the liar he will lie what the answer will be and he lies and instead shows the way to heaven.
5. 10 Coins Puzzle
You are blindfolded and 10 coins are place in front of you on table. You are allowed to touch the coins, but can’t tell which way up they are by feel. You are told that there are 5 coins head up, and 5 coins tails up but not which ones are which. How do you make two piles of coins each with the same number of heads up? You can flip the coins any number of times.
Solution :
Make 2 piles with equal number of coins. Now, flip all the coins in one of the pile.
How this will work? lets take an example.
So initially there are 5 heads, so suppose you divide it in 2 piles.
Case:
P1 : H H T T T
P2 : H H H T T
Now when P1 will be flipped
P1 : T T H H H
P1(Heads) = P2(Heads)
Another case:
P1 : H T T T T
P2 : H H H H T
Now when P1 will be flipped
P1 : H H H H T
P1(Heads) = P2(Heads)
6. King and Wind Bottles Puzzle
A bad king has a cellar of 1000 bottles of delightful and very expensive wine. A neighboring queen plots to kill the bad king and sends a servant to poison the wine. Fortunately (or say unfortunately) the bad king’s guards catch the servant after he has only poisoned one bottle. Alas, the guards don’t know which bottle but know that the poison is so strong that even if diluted 100,000 times it would still kill the king. Furthermore, it takes one month to have an effect. The bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever bad king he knows he needs to murder no more than 10 prisoners – believing he can fob off such a low death rate – and will still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time. Explain what is in mind of the king, how will he be able to do so ?
Solution :
Think in terms of binary numbers. (now don’t read the solution, give a try).
Number the bottles 1 to 1000 and write the number in binary format.
bottle 1 = 0000000001 (10 digit binary)
bottle 2 = 0000000010
bottle 500 = 0111110100
bottle 1000 = 1111101000
Now take 10 prisoners and number them 1 to 10, now let prisoner 1 take a sip from every bottle that has a 1 in its least significant bit. Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit. etc.
prisoner = 10 9 8 7 6 5 4 3 2 1
bottle 924 = 1 1 1 0 0 1 1 1 0 0
For instance, bottle no. 924 would be sipped by 10,9,8,5,4 and 3. That way if bottle no. 924 was the poisoned one, only those prisoners would die.
After four weeks, line the prisoners up in their bit order and read each living prisoner as a 0 bit and each dead prisoner as a 1 bit. The number that you get is the bottle of wine that was poisoned.
1000 is less than 1024 (2^10). If there were 1024 or more bottles of wine it would take more than 10 prisoners
7. Mislabeled Jar Puzzle
You have 3 jars that are all mislabeled. One jar contains Apple, another contains Oranges and the third jar contains a mixture of both Apple and Oranges.
You are allowed to pick as many fruits as you want from each jar to fix the labels on the jars. What is the minimum number of fruits that you have to pick and from which jars to correctly label them?
Solution
Let’s take a scenario. Suppose you pick from jar labelled as Apple and Oranges and you got Apple from it. That means that jar should be Apple as it is incorrectly labelled. So it has to be Apple jar.
Now the jar labelled Oranges has to be Mixed as it cannot be the Oranges jar as they are wrongly labelled and the jar labelled Apple has to be Oranges.
Similar scenario applies if it’s a Oranges taken out from the jar labelled as Apple and Oranges. So you need to pick just one fruit from the jar labelled as Apple and Oranges to correctly label the jars.
8. Red and Blue marbles Puzzle
You have two jars, 50 red marbles and 50 blue marbles. You need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. When picking, you’ll first randomly pick a jar, and then randomly pick a marble out of that jar. You can arrange the marbles however you like, but each marble must be in a jar.
Solution :
Seems tricky at first right? Given that the number of red and blue marbles are the same, you would tend to think that the odds are 50-50. You would try different combinations, such as 25 of each colored marble in a jar or putting all red marbles in one jar and all the blue in the other. You would still end up with a chance of 50%.
So lets think of a better way to distribute the marbles. What if you put a single red marble in one jar and the rest of the marbles in the other jar? This way, you are guaranteed at least a 50% chance of getting a red marble (since one marble picked at random, doesn’t leave any room for choice). Now that you have 49 red marbles left in the other jar, you have a nearly even chance of picking a red marble (49 out of 99).
So let’s calculate the total probability.
P( red marble ) = P( Jar 1 ) * P( red marble in Jar 1 ) + P( Jar 2 ) * P( red marble in Jar 2 )
P( red marble ) = 0.5 * 1 + 0.5 * 49/99
P( red marble ) = 0.7474
Thus, we end up with ~75% chance of picking a red marble.
9. Gold Bar Problem
You’ve got someone working for you for seven days and a gold bar to pay him. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. What and where are the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?
Solution :
The trick is not to try and how to cut in such a way to make 7 equal pieces but rather to make transactions with the worker. Make two cuts on the gold bar such that you have the following sizes of bars.
1/7, 2/7 and 4/7. For convenience sake, I would just refer to the bars as 1, 2 and 4.
At the end of Day 1: Give Bar 1 (You- 2 and 4, Worker- 1)
At the end of Day 2: Give Bar 2, Take back Bar 1 (You- 1 and 4, Worker- 2)
At the end of Day 3: Give Bar 1 (You- 4, Worker- 1 and 2)
At the end of Day 4: Give Bar 4, Take back Bar 1 and Bar 2 (You- 1 and 2, Worker- 4)
At the end of Day 5: Give Bar 1 (You- 2, Worker- 1 and 4)
At the end of Day 6: Give Bar 2, Take back Bar 1 (You- 1, Worker- 2 and 4)
At the end of Day 7: Give Bar 1 (You- Empty, Worker- 1, 2 and 4)
10. 100 Doors Puzzle
You have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), ec, until you only visit the 100th door. What state are the doors in after the last pass? Which are open which are closed?
Solution :
For example, after the first pass every door is open. on the second pass you only visit the even doors (2,4,6,8…) so now the even doors are closed and the odd ones are opened. the third time through you will close door 3 (opened from the first pass), open door 6 (closed from the second pass), etc..
what state are the doors in after the last pass? which are open which are closed?
You can figure out that for any given door, say door #42, you will visit it for every divisor it has. so 42 has 1 & 42, 2 & 21, 3 & 14, 6 & 7. so on pass 1 i will open the door, pass 2 i will close it, pass 3 open, pass 6 close, pass 7 open, pass 14 close, pass 21 open, pass 42 close. for every pair of divisors the door will just end up back in its initial state. so you might think that every door will end up closed? well what about door #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only visit door #9, on pass 1, 3, and 9… leaving it open at the end. only perfect square doors will be open at the end.
Puzzles are good way to exercise your brain. I hope this was a good start.
No comments:
Post a Comment