Friday, January 11, 2008

It's Simple

Another round of job interview brainteasers. Answers below:

You have a cube, 10 inches on a side. Cut it into smaller cubes, 1 cubic inch each. How many smaller cubes do you have?

No, that's not the brainteaser. I didn't realize that at first and thought it was a trick question.

Remove the outside layer of small cubes from all six sides of the big one. How many small cubes do you have now?

Scroll down for the answer.

Answer: 512, or 83. I had to visualize this: (1) Remove the right and left layers, leaving an 8 × 10 × 10 prism. (2) Remove the top and bottom layers, leaving an 8 × 8 × 10 prism. (3) Remove the front and back layers, leaving an 8 × 8 × 8 cube.

This took maybe a minute of mental processing and afterward, the hiring manager gave me, "Or ten minus two cubed. Here's another one."

You have eight balls, all indistinguishable from each other except that one of the eight is heavier than the rest. You also have a balance scale, which you can only use twice. How do you figure out which ball is the heavy one?

Weighing half of the balls against the other half will require log2(8) = 3 weighings. Same problem splitting the balls up five and three, six and two, seven and one, and eight and zero. "There must be another way to divide up the balls," the hiring manager encouraged (?) me, although I still wasn't convinced this wasn't a trick question. "There must be another way to divide up the balls." He must have said it twenty, maybe thirty times, in a couple of minutes. No pressure.

I don't know; inspiration struck. The first weighing needs to divide the set of balls into subsets with at most 21 + 1 balls in each, which is the largest number of balls that can be compared in a single weighing. Divide the balls into subsets A, B, and C, where A and B have three balls each and C has two. If A and B have equal weights, then the heavy ball must be in subset C, and it's trivial to solve from there. The case where A and B have unequal weights can be generalized: Say A is heavier than B. The heavy ball must be in subset A. Now, arbitrarily weigh two of the balls from A. If their weights are equal, then the heavy ball must be the remaining one. Q.E.D.

I enjoy these kinds of problems, but what's up with the interviewer pushing me, hurrying me, tapping his fingers on the desk and molding my mind like the solution's obvious and I must be the stupidest person ever to not see it right away. Yes, it's easy for you because you have the answer, jackass!!!