GOOGLE Interview Question || Puzzle : 12 Men On An Island || Hard Logic Puzzle

GOOGLE technical interview puzzle : This puzzle is asked in the software or technical porgramming Google interviews. This video explains the questions or requirements and two different answers.
It's a hard logic riddle.
-----------------------------------------------
You can find the solution with 4 men at this google drive link below:
-----------------------------------------------
This interview puzzle has a mind blowing GOOGLE twist inside, so watch the complete video as you will see a smarter approach to solve this puzzle.
PUZZLE :
There are 12 men on an island. Eleven weigh exactly the same amount but one of them is either heavier or lighter than others. There is a see-saw on the island which can be used to find out the odd man, but the catch here is that you can use the see-saw only 3 times.

So using the see-saw only 3 times... Your task is to find out
- the odd man (i.e. the man with different weight).
- and Also find out if the odd man is heavier or lighter.

There exists several variations of this interview puzzle such as:
- 12 (twelve) balls and 3 (three) weighing/scale
- 12 marbles and 3 scale
- Twelve coins and three weighing (12 coins riddle)
In all these variations the intention is to identify the defective object by using the scale only three times. Also, you would need to figure out if the defective object is lighter or heavier compared to others.

This google interview coding question or puzzle was also featured in a TV series called Brooklyn 99 (Brooklyn Nine-Nine ) in the same format of 12 men as in this video.
Google is known for asking tricky puzzles and hard riddles in the interviews. They check the optimization skills of a candidate with his approach of solving a puzzle. If a candidate has good optimization skills then it will benefit the organization in writing optimized programming code that eventually improves the response time of software applications and websites.

In the video I have explained a natural approach followed by a fresh approach which is expected by google interviewer. I also have explained why the first approach is not upto the mark for google and how we can arrive at the second approach in most logical way possible.
So if you are preparing for google interview questions for software engineer then you can watch all google puzzles on my channel.

You are most welcome to share puzzle, math problems or any topics for upcoming videos.

Also try these hard google puzzles:
100 Doors Puzzle || Hard Puzzle for genius minds

5 Pirates PUZZLE (Version 2) | 100 Gold Coins 5 Pirates

Gold Chain Puzzle || Beautiful Logic Puzzle || 149 links

[murali]

It's a war between space and time complexity. Earlier days memory was too costly but we had time, hence we had less space consuming but more time consuming apps. But now space is cheap but time is costly, that's why we are having more space consuming and less time consuming apps. Dynamic Programming literally means using more space to reduce the time required for computation.


So it's simple, the first approach takes more time but less space, and the second approach takes more space but less time. The solution depends relative to the problem always which is why we don't have 1 definite solution for all.

Both the approaches are correct and you would get a job if you are able to explain it.

[georgemcaneny]

If we weren’t all so awkward we could simply ask the people their weights, thus eliminating the need for a seesaw

[gblargg]

I puzzled over and gave up. The first solution is so amazing how it saves every bit of useful information from each step to combine later to reach a result quickly. The second solution washes all that away and looks at the general problem, showing how it all just falls together naturally and without anything special. The richness of the solutions to such a simple problem are what brings me back to mathematics every time. So much hidden wonder. Even though I didn't solve it myself I found this inspiring.

[kangjohan]

Like always, while credit is given to those who solved the question, I always admired those who came up with these questions in the first place....

[SkittleJawnz]

My answer: Google search which man is heavier or lighter since all of their data is online

[rameshkiran]

I solved this puzzle in other way around
12 yrs back..
W-weigh, we give number to each on
Scenario 1, W1: four on each side 1234-5678 if it is balanced then it is simple to find the odd one from remaining 4, as follows W2: keep a person(12) aside n weigh like this 9, 10-11, 1, if it is balanced then compare 12 with 1, ll know whether he is lighter n heavier. If it isn't balnced, and tilting towards 9, 10 means either one of them is heavier r 11 is lighter, then W3:compare 9&10, which way it goes is the heavier one, if balanced 11 is lighter.
Scenarios 2: W1: 1, 2, 3, 4 - 5, 6, 7, 8 unbalanced n shifted towards 1234, W2: 1, 2, 5 - 3, 6, 9 if still shift to 1, 2, 5 it means either one from 1&2 is heavier r 6 is lighter.. Then compare 1&2 which side it tilts is the heavier if balanced 6 is lighter. If 1, 2, 5- 3, 6, 9 is balanced means eeither 4 is heavier r one from 7&8 is lighter, then compare 7 with 8. if in Scenario 2 balance shifted to 3, 6, 9 side that means either 3 is heavier r 5 is lighter... Compare any one from 3&5 with normal one to get to know the odd one...

[mnad]

We had this question back in winter term 1989 on our very first weekly exercise sheet at the very beginning of our Computer Sciences studies, at Karlsruhe University, Germany. We did come up with solutions similar to this one, but the real catch came when we were shown and told that this can be modelled as an error-correcting Hamming code with a 12x3 matrix over Galois Field GF(3). One matrix multiplication and bang, you get the position and weight of the odd man out. Oh, that was an ideal precursor to the advanced stuff that was to follow in the next couple of years, and a sure way to whet our appetite. Happy memories.

[letsgobrandon]

Not at google but I was asked this question years ago for a server lab job. I did not know the answer and did not get the job lol. He said not one interviewee knew the answer. I still believe to this day if I knew this riddle I would have gotten that job.

[WHYNOTDOTTV]

I watch the first minute of this video and then I paused it. I realized that I was presented with this puzzle in 1989. However it was presented to us as 12 balls and a balance scale that could only be used three times.
The professor wanted us to come up with the best route that will result in the highest potential of coming up with a solution. I came up with a solution the next day. When I presented it to him he said that I must have made a mistake. The reason was; when he was presented with the puzzle, it was presented to them as something that does not have solution. I'm glad that he had forgotten to tell us that little detail.

[loklokeshava]

When we are going to attend for aptitude can easily test the trainer by giving this question....🙋‍♂️

[nickwisely]

for the first few minutes, "Ahh I got this, simply do it as TedEd has explained".
the second explanation, "Ohh wait, what was that? how could you... but... nevermind."

[zilvarro]

I think in general you should balance the following three quantities as good as possible in every step (while making sure Left and Right contain the same number of people by filling up with Confirmed Persons):
A) 2 * Unknowns Outside + Suspects Outside
B) Unknowns Inside + Heavy Suspects Left + Light Suspects Right
C) Unknowns Inside + Light Suspects Left + Heavy Suspects Right
If not perfectly possible you should prefer to have the Inside a bit larger.

Reasoning: This optimizes the worst possible outcome of the scaling step.

[archanagupta]

Use the sand on the island
Measure the amount of compression one guy makes then see all compressions and compare the deeper or shallower one

[chrismoule]

Just found this: my father gave me this one when I was a young teenager. His only clue was "you must get the maximum amount of information from each weighing". When I couldn't do it, he amended this to "what does each weighing tell you?". I did it - in the end. Later on I did programming and got to know about the "even more logical" approach mapped out here.

[armochim]

This is based on a problem from a brazilian math professor Júlio César de Mello e Souza. during the 1930 decade. My father was one of his students and told that he was a wornderfull mathematician. I'd lije to suggest that the Google give credit to him. He wrote a book called "O homem que calculava" Something like "The man that used to do calculus"

[thatrandomguy]

At first I thought this was one of those bs "Only 1% with 6000 IQ can solve" puzzles but it was a genuine programming problem. Thank you algorithm

[magicmulder]

The key idea is the "balancing with known normal men" part. That's what I didn't see initially when I considered how many to place on the see-saw.

[johannesvanderhorst]

My first solution had a slight difference: in the second weighting, on both sides I put two suspects to be heavy and one suspect to be light. This removes case 2b and adds an additional case 2c.

[coffeecuppepsi]

I did group of 4 vs 4. Then shift out 3 pleople from the left and shift in three to the right. Weigh again. By tracking which way scale tilts you can tell which group of three has lighter/hevier person. If last guy is left alone just weigh him against anyone else. .

[workbyme]

I created the same puzzle to challenge myself when I was a high school student back to 50 years ago. 12 coins with one fake without knowing it is heavier or lighter, the measurement tool is a balance scale. The solution I found was divided them into 3 groups, 4 each. 1, 2, 3, 4 5, 6, 7, 8 and, 9, 10, 11,12. The first measurement is to place 1, 2, 3, 4 on left side and 5, 6, 7, 8 on right side. If it is balanced, 9, 10, 11, 12 has one fake coin, it's easy to find it with 2 measurements. If it is not balanced, then the tricky part is to do a rotation. Left side to be 1, 6, 7, 8 right side to be 5, 10, 11, 12. Then you'll find 2, 3, 4 or 6, 7, 8 or 1, 5 has a fake coin in it. You can easily find it with 3rd measurement. Then I ask myself what is the maximum coin I can inspect with 4 measurements? How about 5 and more? Then I found the answer is 12*3^（n-3). I read most of the comments, I like the one solution to use 3x3 grid.