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

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.

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

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....

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.

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.

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

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.

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...

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"

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

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

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."

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.

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.

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.

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.

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

I've seen this question many times before Google even existed...This is a famous puzzle.

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. .

The big problem that threw me off track when I first was confronted with this problem in the late 90s is the amount of if/then/else branching you have to do. And if you know the 9 ball / 1 heavier problem, it actually makes it harder for you to solve this since you start off trying to solve it the same way, which does not work.