Commonly asked interview puzzles – Part II
Introduction
Most of the analysts love solving and asking puzzles. Some of the best analysts I know, have a glean in their eyes at mention of a difficult logic puzzle. While these puzzles are fun to solve in free time, they might look scary to other people facing them in an interview backdrop.
As Tavish mentioned in his article, use of puzzles to select candidates may not be the best way to do the recruitment. But, the reality is that puzzles get asked as part of many interviews. This also turns out to be an advantage for you, if you have solved these kind of puzzles before hand. This article will lay out a few more puzzles, which are commonly asked in interviews.
Puzzles are one aspect of the entire data science interview process. We have listed down a comprehensive 7-step framework to crack data science interviews and land your dream role in the ‘Ace Data Science Interviews‘ course. Head over to the portal and enroll today!
I have divided the puzzles in 3 Stages (sort of gamification). Puzzles in stage 1 are simple. Hence, I’ll not give the solution to them. If you are not getting solution to them, you are not applying yourself. You should spend some time thinking about them and you would be able to get the answer. Stage 2 are tougher than Stage 1 and should be more interesting as well. I have included some common approaches people take and the right solution to these interview puzzles. Stage 3 is the most difficult out of these 3 stages and I’ll release the solution to the puzzle next week.
If you have come across any other puzzle in analytics interviews, please feel free to share them through comments and let us try and solve them as a community.
Stage 1 – Simple Puzzles
Puzzle 1 – 3 switches and a light
You have 3 switches in a room. One of them is for a bulb in next room. You can not see whether the bulb is on or off, until you enter the room. What is the minimum number of times you need to go in to the room to determine which switch corresponds to the bulb in next room.
Answer – 1
Puzzle 2 – Mis-labeled bags
You have 3 bags with you – one with pink toys only, one with blue toys only and one with a mix of two colors. But, the labels on all three bags are wrong. What is the minimum number of draws you would need to make, in order to identify all three bags correctly.
Answer – 1
Hint – All the bags carry wrong label
Stage 2 – Let’s make it interesting
Puzzle 3: Find the defective coin
There are 10 stacks of 10 coins each. Each coin weights 10 gms. However, one stack of coins is defective and each coin in that stack weights only 9 gms. What is the minimum number of weights you need to take to find which stack is defective? How?
Typical Solution:
The dumbest answer in this situation would be 10 (or 9) attempts, when you weigh each stack. A few people try to arrive at a solution with divide and rule method – divide the stacks in 2 groups of 5 each and weigh any one of them – if it weighs 500 gms then the other group has defective stack. In the next turn you divide the remaining stacks in 2 groups and weigh again. In this manner, you can get to the defective coin in a maximum of 4 measurements at your weighing machine. While this approach is smarter than 10 attempts, it is still not the most efficient way.
Correct solution:
The trick in solving this puzzle lies in creating a weighted stack for measurement. You can find the defective stack in one measurement. How? You take 1 coin from the first stack, 2 coins from the second, 3 from the third and so on. In total you will have 55 coins. If all of them were non-defective, they would weigh 550 gms. If stack 1 is defective, the measure would read 549 gms. If stack 2 is defective, you will read 548 gms. and so on. So by taking one measurement you can identify, which is the defective stack.
A variation – How many measuring attempts would you need, if there were 11 stacks of 10 coins each and one was defective?
Puzzle 4: Finding the Fastest horses
You have 25 horses and you can race only 5 of them simultaneously. Assuming you do not have access to stop-watch, how many times would you need to race the horses to find the 3 fastest horses.
Typical solutions:
This puzzle typically sees some wide variety of responses. One popular answer is to race all 25 horses through 5 races, then pick the 3 winners from each round – that leaves you with 15 horses. You race them in three rounds to find the 9 fastest and then race 9 to find 6 fastest and then do 2 races with replacement of slow horses from first race to find out the fastest horses. That gives us a total of 12 races. Some answers, I have heard even say 11 races.
Correct solution:
You need 7 races to find out the fastest horses. First do 5 races and identify all the winners, then make them run simultaneously to identify top 3 horses among the winners. The winner of the 6th race is the fastest horse of the bunch. Now, we need to find the second and third – so we take second and third position horses from the group of fastest horse along with the second position horse from the group of horse who came 2nd in sixth race and race them along with the position 2 and position 3 horses from 6th race. The winner and runner up of this race are your second and third best horses.
Puzzle 5: Red and Blue balls in a bag
You have 20 blue and 13 red balls in a bag. You pull out 2 balls one after another. If the balls are of same color, then you replace them with a Blue ball – but if they are of different color, you replace them with a Red ball. Once you take out the balls, you do not put them back in the bag – so the balls keep reducing. What would be the color of the last ball remaining in the bag.
Typical solution:
A lot of people start calculating probabilities and try to create some sort of a series out of the pattern. I got a similar puzzle in one of the interviews and I tried doing that as well. But, if you go down that route, this becomes very tough and unmanageable. The key to solving this puzzle is to realize that there are odd number of red balls in the bag.
Correct solution:
The right answer is Red. This puzzle looks like a difficult one, till you find out the solution. But, the minute you get the solution, you feel that this was dead simple. If you pull out 2 red balls, you replace them with a blue ball. On the other hand, if you pull out one red and one blue – you replace it with a red ball. So, the red balls would always be odd in numbers – either you remove 2 together or remove 1 and add 1 – so they remain odd always. Hence, the last ball to stay in the bag would be a red ball.
Stage 3 – Only for the pros
This puzzle is meant to be solved, if you have done all of the ones above. Again, I won’t release the solution – if you get the solution, you can write it down in comments. If you don’t – I’ll put the answer 7 days after the article is made live. Go – scratch your head!
Puzzle 6 – King and Wine
You are the ruler of an empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You’ve got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them has been poisoned by your enemy. The poison exhibits no symptoms until death and the death occurs within fifteen hours of consuming even a diluted sample.
You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned. You also have 30 prisoners about to be executed, and it would mar your celebration to have anyone else killed. What is the minimum number of prisoners, you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?
These were some commonly asked interview puzzles. If you know of any other puzzle which employers ask in an analytics interview – please feel free to share.
If you like what you just read & want to continue your analytics learning, subscribe to our emails, follow us on twitter or like our facebook page.
Kunal is a post graduate from IIT Bombay in Aerospace Engineering. He has spent more than 10 years in field of Data Science. His work experience ranges from mature markets like UK to a developing market like India. During this period he has lead teams of various sizes and has worked on various tools like SAS, SPSS, Qlikview, R, Python and Matlab.
A small query to your puzzle in the 3rd section: When does the death happen Is it within 15 hours or exactly at 15 hours
code those 1000 bottles in binary notation. Then 10 prisoners are enough as 2^10 > 1000
Nice puzzle! My proposed solution can be found here: http://rpubs.com/guindilla/34836 Cheers.
Ok, nevermind... my solution might not work, as time of death is within 15 hours of consuming the sample, not after 15 hours of consuming the sample, which I interpret as a death can occur between 0 and 15 hours of taking the venom. My bad, must learn to pay more attention to puzzle details :-)
Kunal, Great set of puzzles you have here. Here is my solution to the puzzle, # prisoners required: 10 I solved this using the concept of binary numbers. Lets number all the bottles as 1 to 1000. Now conert these numners into 10 digit binary base. For example 3 becomes 0000000011. Now this will mean this wine should be given to 9th and 10th prisoner. With a 10 digit binary number we can create 1024 (>1000) numbers in similar fashion. Hence, after waiting for 15 hrs , the pattern of death will tell us which bottle is poisoned.For instance, if 9th and 7th prisoner died , the poisoned bottle is 101 which is 5 th numbered bottles . I still feel this number can further been reduced given the poison works in 15hrs ( and not takes as long as 24 hrs). Tavish
Bang on with your solution Tavish.
Hi Tavish, Iam not sure about this solution. Take a look. Since it takes 15 hrs for the person to die and we have 24 hrs we can divide our time into (24-15) = 9 time slots . Divide the no of bottles (1000) by 9 . It gives us arnd 111 . Now using the same principle of binary coding , it can be done by using only 7 prisoners as 2^7 = 128. So now , in order to determine the correct bottle , we have 2 criteria , the binary code of the prisoner and the time at which he dies .
One prisoner can either drink or not drink the wine. So the base of the number system would be 2. Now since 1000 unique bottles have to be identified, we have to select the number of prisoners such that they are able to represent numbers >1000. Since 2^10 = 1024, therefore 10 prisoners would be able to represent numbers from 1 to 1023. Suppose 1 represents drinking and 0 represents not drinking, then bottle number 116 is represented by 0001110100 which means prisoner number 3, 5, 6, 7 drink the wine from this bottle where rest don’t. So wine is served from all the 1000 bottle to prisoners who represent that number. So after 20 hours, the prisoners that die would represent the poisonous bottle number. Therefore the answer is 10. :)
3 prisoners must die. we need to mark the bottles in 3 steps step1 mark the bottles in to 10 categories named A,B,C,D,E,F,G,H,I,J, each category containing a 100 bottles. select 10 prisoners and name them as A,B,C,D,E,F,G,H,I,J AND make them drink a mix of samples from all the 100 bottles from one category each. (Prisoner A will drink sample From category A and so on...) If prisoner A dies, it indicates poison is in between1st to 100th bottle. step 2 subdivide each category into 10 subdivisions each contain 10 bottles. for example category should contain 10 sub categories A1, A2,A3...A10. Do the same marking for all categories. (A1 represents 0 to 10th bottle, B1 represent 100th to 110th bottle) mix the samples from the same numbered subdivisions from all the 10 categories. for example(sample 1 = A1+B1+C1+D1+E1+F1+G1+H1+I1+J1 sample 2 = A2+B2+C2+D2+E2+F2+G2+H2+I2+J2) select another 10 prisoners name them as 1, 2,3,4,5,6,7,8,9,10 and make them drink one sample each. (Prisoner 1 will drink drops from 0 to 10th , 100 to 110th, 200 to 210th, 300 to310th, 400 to 410, 500 to 510th, 600 to 610th, 700 to 710th, 800 to 810th 900 to 910th bottles. Prisoner 2 will drink drops from 10 to 20th , 110 to 120th, 210 to 220th, 310 to320th, 410 to 420, 510 to 520th, 610 to 620th, 710 to 720th, 810 to 820th 910 to 920th bottles. and so on) if prisoner '9' dies it indicates poison is in anywhere between 80 to 90th , 180 to 190th, 280 to 290th, 380 to390th, 480 to 490, 580 to 590th, 680 to 690th, 780 to 790th, 880 to 890th 980 to 990th bottles step 3 now we have 100 subdivisions. . A1 to A10 B1 to B10 C1 to C10 .................. J1 to J10.(each contains 10 bottles each) mark the each 10 bottles from all the subdivisions from i to x. this indicates the last digit of the bottle number. (A1 contains A1a, A1b, A1c, A1d, A1e, A1f, A1g, A1h, A1i, A1j A2 contains A2a, A2b,A2c,A2d,A2e,A2f,A2g,A2h,A2i,A2j ... B1 contains B1a, B1b,B1c,B1d,B1e,B1f,B1g,B1h,B1i,B1j ... J10 contains J10a, J10J,J10c,J10d,J10e,J10f,J10g,J10h,J10i,J10j) mix drops from all 100 subdivisions' first bottle (marked as XXa)and make a sample. (A1a+A2a+...A10a+B1a+....B10a+C1a+.......J10a) do the same for all the second, third......tenth bottles(up to j). select 10 prisoners and name them as a,b,c,d,e,f,g,h,i,j. make them drink one sample each. Now after 15 hours, 3 prisoners will die, one from each step. assume that 'D' from first step, '7' from second step, 'e' from third step died. it indicates 1) the bottle is in D section (between 300th bottle to 400th bottle) 2)it is between 60th to 70th bottle (that is, between 460th to 470th) 3)its last digit is 5, so 465th bottle contains poison.
Loved the solution!
Lovely solution, but the puzzle text stated: "What is the minimum number of prisoners, you must have to drink from the bottles" And you in fact use all 30 prisoners, even though you guarantee that no more than 3 die...
Good solution! Hadn't seen any one provide this solution before. Regards, Kunal
Hii, Nice solution, but I think 30 persons are more in this approach. 27 persons are enough. As basically we are numbering all bottles for 0 to 999 and finding all the three digits by using 10 persons for each digit. But 9 persons are enough to find each digit because if no one will die then the poison is in the tenth one. Regards, Anurag
Hii, Nice solution. But I think we can further reduce it to 27 persons by this approach. Basically we are numbering bottles from 000 to 999 and then finding all three digits by using 10 persons for each digit (i.e 0 to first person,1 to second & so on.). But 9 people are enough because if no one will die then poison is in the tenth one. Hence persons required = 9*3= 27 Regards, Anurag
But how can you be sure a prisoner died because of the step you mentioned? To rephrase, when prisoners 4, 5 and 6 dies, it could mean it was bottle 465, 654,456,645,546 or 564. Correct me if I am wrong..
i have a doubt in your solution.... the person will die only after 15 hours right ? but we have a time limit of 24 by the end of second step it will be 30 hours right?
Reading the text as the Devil would, it actually states: "You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned. You also have 30 prisoners about to be executed, and it would mar your celebration to have anyone else killed." So: I have 1000 slaves and 30 prisoners, and no one else is to be killed (apart from the slaves and prisoners) " What is the minimum number of prisoners, you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?" Let the 1000 slaves drink from one bottle each. One of them dies, and there's your bottle. No prisoners have to taste the wine :-)
Smart attempt! However, you would want to save your slaves over prisoners. Hence this solution does not work. Regards, Kunal
I have some query in solution of Puzzle 4: Finding the Fastest horses As per the solution, we have done 5 races & identified all the winners and rejected rest 20 horses in further races. But still there is a possibility that (since we dont have access to a stop watch) a horse coming 2nd in 1st race might be faster than a horse coming 1st in 4th race. & we are rejecting a horse coming 2nd in 1st race completely in further races. I might be wrong as well. Just let me know your views on it.
No, this possibility does not exist - take an example and follow the steps. The trick is here: "so we take second and third position horses from the group of fastest horse" This ensures that we cover all possibilities.
there could be many answers for the KING & WINE puzzle. 1) if the enemy has not take care at the time of mixing poision into the bottle; then open sealed of cap of bottle will the required bottle. 2) if the enemy has opened sealed of all bottle to confuse then; if the death of the prisoner after tasting the poisionous wine effected by 1 second then answer will be only 1 prisoner required to find poisionous bottle. 3)if the death of the prisoner after tasting the poisionous wine effected by last minute of 15th hour then answer will be only 2 prisoners required to find poisionous bottle. and many other possiblities of the answers
there are many possible answers for the puzzle KING & WINE; as follows 1) if the enemy didn't care at the time of mixing poision in bottle and only broken the seal of bottle in which he has mixed poision and left others un-broken seal. 2) if accuracy of death effects by 1 sec; then only 1 prisoner will be sufficient to find the poisioned bottle 3) if accuracy of death effects by last minute of 15th hour; then 2 prisioners will be sufficient to find the poisioned bottle
Hi Kunal, I have started following this site lately and I love it and really appreciate your efforts and knowledge. Can you please tell some good sources to practice more stuff on such puzzles? Thank you, Akanksha
Solution to level 3 puzzle arrange 1000 in a matrix of 25 rows and 40 column step 2: Make 25 different prisoner drink from each of the rows (Means 25 Prisoners) Step 3: After 1 hours Make 40 different slaves to drink from 40 different coumns step 4: One prisoner and one slave will die intersection of the column and row will be the poisonous bottle
Used to do puzzles a decade back. Just looked at the first puzzle. The answer is 0. Put all three switches on, and see which one heats up after some time. Now lets see the other puzzles :)
Answer to last puzzle: Get 10 prisoner an order them in a row. Each bottle can be represented by a unique string of 10 binary (0/1) numbers. Ask these prisoners to look at each bottle and drink a sip if it has a 1 written in their position (the 5th guy always looks at the 5th digit). After 15 hours, find whic sequence of prisoners die. This will identify the unique bottle that is poisoned.
Aslight modification to the last puzzle is if we want the minimum number of prisoners to die (instead of min number of prisoners to drink). may be 3 prisoners. The 30 prisoners can represent 1000 points in a 3D grid (10 on x axis, 10 on y, 10 on z). The 3 that die will point out which bottle is poisonous. Note, it says drinker will die within 15 hours, not exact 15 hours. If that were the case, only 1 prisoner is needed by noting when exactly he dies.
Using 21 prisoners we can find out. 1000=5*5*5*2*2*2 Take a 6D matrix with sides 5*5*5*2*2*2 each interesting point representing a wine bottle. The poisoned bottle will kill the prisoner (represented as lines) passing through that point.
To test wine bottle needs to opened. The king's idea of opening it in the party would be a flop. Moreover, If so many prisoners try the wine. It will be over. What is the point of killing people just to know which bottle is poisoned. No business value.
One hell of a blog!
We need only 1 prisoner to detect the bottle which contains venom I will number all the bottle's from 1 to 1000 From Starting every 30 seconds i will make that prisoner drink from a bottle in increasing order. So it will take a maximum difference of 30*1000=30000 seconds which is less than 9 hours. So If the last bottle contains venom so it will take a maximum of 15hrs + 30000 seconds, which is less than 24hrs. Check the dying time of the prisoner and then you can figure out which bottle contains venom with simple mathematical calculation.
The no. of prisoner required is 3. Here we are assuming that the same prisoner can taste as many wine bottles as possible, as long as he is alive. Now, we can utilize the entire 24 hours for testing. So first we divide 1000 wine bottles into sets of 11 bottles each. 1000/11=91 (approx). So it will take 91-1 i.e. 90 attempts to identify which set of 11 bottles contains the poisoned wine. The time used is 90*15 mins=22.5 hours and we have 1 dead prisoner. We have 6 blocks of 15 mins in our hands. Now, the identified set of 11 bottles is divided into 3 sets as 5+5+1. The 2nd prisoner is brought in who tastes these 3 sets of bottles. While tasting these 3 sets, the 2nd prisoner will be dead and we shall know either one of these two 5 set bottles is poisoned or the one remaining is poisoned. This testing will take 15+15=30 mins. Now, let us consider, one of the 5 set bottles is poisoned. So, we have 5 bottles, 2 dead prisoners & 1 hour remaining. Now the 5 set bottles is divided as 1+1+1+1+1. The 3rd prisoner is brought in to taste the first 4 bottles which will take 1 hour. Either the 3rd prisoner dies tasting else If the prisoner lives then the last bottle remaining is the poisoned. Cheers!!
plzzz explain puzzal 1............
Solution given by tavish is perfect...which gives bottle number directly...where as sumalatha's solution requires 3 stages means minimum of 3*15 hours of waiting time so it's 45Hrs and given time is only 24Hrs..so her solution here fails
If you make the assumption that the poison may take anywhere from 0 to 15 hours BUT it will be the same amount of time for two prisoners, then you only need two prisoners to identify the bottle. Mark the bottles 1 to 1000. Have the first prisoner start sampling bottle 1 and work his way up every minute. Have prisoner 2 start sampling the bottles starting with bottle 1000 and working his way down. At one bottle per minute, prisoner 1 will die at bottle# (B) + Tdelay. Prisoner 2 will eventually die at 1000-bottle# + Tdelay. Let's assume the posion bottle is #214 and the poison delay time is 1596 minutes (~13 hours). Tdeath1 would then be 1024min and Tdeath2 would be 1596min. So we know the time of deaths, but NOT the bottle number or the Poison delay time Tdelay. We can still figure out both, but for brevity will skip Tdelay and just get bottle number. Tdeath1 = 1024 = B + Tdelay Tdeath2 - 1596 = 1000-B + Tdelay B + Tdelay -1024 = 0 = 1000-B + Tdelay - 1596 Factor out Tdelay B + 1024 = 1000-B -1596 2B = 1000 -1596 +1024 2B = 2024-1596 2B = 428 B = 218 The poison bottle is the bottle labelled 218. We didn't even need to know the delay, though it is easy to figure now (1024 = B + Tdelay... Tdelay = 1024 - 214 = 810). In real life, I may not make the assumption that the delay is the same so maybe I expend two extra prisoners verify. They of course would need to drink right away because the clock is ticking.
The final B = 218 should be B = 214. Was in a hurry. The math is still correct.
I would say 1 prisoner is optimum to figure out which bottle s poisoned. He needs to take a sip from all of the 1000 bottles with some measurable time interval of say 30 secs. So if bottle 1 is poisoned, he dies in 15 hrs. If the bottle 2 is poison, he dies in 15 hrs and 30 sec. So if this time interval is measured, the poisoned bottle can be figured out in the 9 hour window the king has.
group the bottles in 34 bottles each.. mix the wines of each group of 34 bottles and ask 30 prisnors to drink. identify the group of 34 which has poison. now you have 29 prisnors left divide the 34 bottles into group of 2 bottles each. ask 17 prisnors to drink. identify the group of 2 bottles having poison. Now you are left with 28 prisnors now ask 2 prisnors to drink wine from each and find out the poisonous bottle.
#wine problem : Only one person(prisoner) will be required to drink the wine. Heres how - we have 24 hours however it takes 15 hours for the poisnous wine to show its effect. Take one prisoner -> give him a sip -> note down the time -> after 0.5 min give another sip -> note the time -> similarly do for 1000 wines. Now as soon as the prisoner dies, note the time. Subtract 15 hours from it and find the wine corresponding to that time. Thats the poisnous wine!
10 prisoners denote each bottle by its 10 bit binary equivalent( 10 bits because to represent 1000 we need 10 bits in binary) assemble 10 prisoners in a line take bottle one put 1 drop of it in to first prisoners mouth( 0000000001) take bottle two put 1 drop of it in to second prisoners mouth(0000000010) third bottle - one drop in first prisoners mouth,one drop in second prisoners mouth(0000000011) And So on For 1000th bottle (1111101000) At the end of the time constraint a particular pattern of prisoners die which denote the bottle which contains poison. For example (0000000111) which means 7th bottle
i think answer is 2. hours left = 24-15=9. 9*60=540 minutes poison the prisoner at each minute. have 1000 bottles so 500 for each prisoner. note the time when they were poisoned and the time when they died.