> You have 12 marbles and a balance scale. One of the 12 marbles is inconsistent with the others, meaning it could be heavier or lighter than its peers of normal weight. You are allowed to use the balance scale exactly 3 times to identify which of the 12 marbles is irregular AND determine whether it is heavier or lighter than normal.
I also got this riddle, in 2015. I couldn't solve it. Tbh, I think it's a terrible question. There isn't really a step-by-step problem solving process, but you just need to have a "leap" to realize you can weight the marbles in groups of 3. I also got rejected. It's crazy to get rejected from a one-question riddle like this
Back when I interviewed at MS as a college senior, I had no clue about these "formats". So when someone asked me how I would make (I think they meant design) a web crawler, I started writing one in Python. They didn’t stop me, and it seemed to be awkward to them that I was doing this, whereas I felt awkward that they were acting that way when I was doing what they asked. It was just stupid all around. These systems deserve to be gamed, and the interviewers can't handle anything else, like in TFA.
Google was more elitist than most in its early years. As I recall, candidates had to have graduated from an elite CS program with and provide a transcript when applying showing top grades.
> The key point here is our programmers are Googlers, they’re not researchers. They’re typically, fairly young, fresh out of school, probably learned Java, maybe learned C or C++, probably learned Python. They’re not capable of understanding a brilliant language but we want to use them to build good software. So, the language that we give them has to be easy for them to understand and easy to adopt
> It must be familiar, roughly C-like. Programmers working at Google are early in their careers and are most familiar with procedural languages, particularly from the C family. The need to get programmers productive quickly in a new language means that the language cannot be too radical
One would expect folks coming from an elite CS program, and able to master Google's hiring processes, to be a bit more skilful.
Ironically all those four languages that get mentioned have quite advanced type systems, versus the one for "simple" minds.
> I also got this riddle, in 2015. I couldn't solve it. Tbh, I think it's a terrible question. There isn't really a step-by-step problem solving process, but you just need to have a "leap" to realize you can weight the marbles in groups of 3.
It’s an information theory question similar to the “how far can you drop the egg before it breaks” puzzle. You don’t need a leap of intuition, just remember the right theorems and formulae from college.
I probably would’ve failed the interview. At best I could write an algorithm that empirically arrives at the answer, which may or may not impress the interviewer enough to pass.
Stuff like this is why I dropped out of coding competitions some time in high school. You can always brute force the easy version, then the next tiers drop numbers that cannot be solved unless you know (or can invent) that one weird maths trick.
In the initial state there's 24 (12 * 2) different possibilities: The marble you're looking for is one of 12 and it's either lighter or heavier. By using a balance scale there's 3 possible outcomes (left side is heavier; right side is heavier; same weight). This means that for your last (third) weighing you'll have to have reduced the problem down to 3 (or fewer) different possibilities. If there's 4 or more there's no way to reduce it down to a single possibility. Before the second weighing you should have reduced it down to 9 (3*3) different possibilities.
Once you know this, you can start making educated guesses for the first weighing and quickly eliminate those which makes it impossible to continue. For instance: Splitting the marbles into two. This gives two possible outcomes: Left side is heaver or right side is heavier. For the first outcome it means that either the target marble is lighter and part of the left group (6 marbles) or heavier and part of the right group (6 marbles). That's 12 different possibilities (more than 9) and therefore we know that it's impossible to determine the marble with just two more weighings.
There's still guessing to be done, but at every part of the decision tree you can at the very least quickly avoid exploring paths which are guaranteed to not work.
Now that you spell it out, I guess this just binary search. You need O(log n) weighings because each weighing splits the search space in half. So I was wrong it’s not an information theory question, it’s just comp sci algorithms. I got my college classes mixed up (it’s been 14years)
Exactly. Same kind of thinking gives you bounds on what can be done. For example, can you do 13 marbles in 3 weighings? 213 < 3^3, so maybe (though I think not). Can you do 14 marbles? 214 > 3^3, so definitely no.
I think it's a terrible _interview_ question, partly due to it's "IQ test" nature, but mostly because it's a pretty hard problem and I really wouldn't expect someone to be able to just spew out a solution the first time they hear it.
Of course, the process would be more about the interviewer observing your thought process, seeing how you develop a notation for solving this thing which you almost certainly don't have any pre-existing notation for, etc. I just really wouldn't expect much progress in the space of 5 to 10 minutes, although I am basing this on the "13 marbles" version of the problem.
I also got this riddle, in 2015. I couldn't solve it. Tbh, I think it's a terrible question. There isn't really a step-by-step problem solving process, but you just need to have a "leap" to realize you can weight the marbles in groups of 3. I also got rejected. It's crazy to get rejected from a one-question riddle like this