Several days ago, I saw a question online, which is very interesting. The question states that:

What was the worst interview experience you ever had before?

No doubt, when it comes to computer science related fields / jobs, “Weird” questions are usually the ones people dislike the most because they don’t necessarily indicate one’s capability of engineering. And therefore, I saw such a story:

I went to interview with a tech company, which is fairly large. The first several round I talked to the product manager, the tech people, and it went well for me. They said that my tech base is fairly solid and it shouldn’t be much of a problem for me in the last round with the HR, and here comes the problem.

I interviewed with the HR, and the HR gave me several questions, the first one was “To cut a cake and distribute to 8 people, but need one cake to be remained in the plate, how to?” and the second one was “There are 10 apples in the basket. One apple has a different weight. You can weigh them 3 times.”

Obviously, I wasn’t able to give the answers. And therefore I failed the interview. What dumb question these are!

I don’t want to talk too much about the questions themselves, but I found the second question very interesting. Let’s analyze it.

First Thought

First of all, it is obvious that if we weigh every pair of apple, it would be very easy to give the answer. However this would require 45 times of comparison, which is not good at all. What if we don’t weight them in pairs? What if we weight them by group, say, a group of 4 compared to another group of 4?

That seems to be a good starting point. But how can we group them?

Let’s say we divide and conquer. we devide them into groups of equal numbers, like 5 to 5. In this case, the information we have here would be:

$$\log_210$$

which requires at most 4 times to compare, not good enough. So how can we improve it? Well, thinking of the situation that an apple could be:

  1. Heavier than others
  2. Lighter than others
  3. Has the same weight

It is obvious that we could use 3 as the base, if we do the weighing correctly, and it becomes:

$$\log_310$$

Which requires at most 3 times of comparison. So that is the way we are going for. There is no 4th situation, so the base can be no larger than 3.

So here is our first idea: to separate the apples into 3 groups and compare them.

Next step

Since we have 10 apples, we cannot really separate them into 3 groups of equal number. What do we do? Well, we can try 3-3-3-1. Since the one apple could be either heavier or lighter, we need to first: find which group the apple is in and then decide: the apple is heavier or lighter. These will take two steps, as summarized below:

  1. Separate the apple into 3 groups: 3, 3, 3 and 1 extra one. We call the group with the “abnormal” apple the “problematic” group.
  2. Compare the first 3 apple group and the second 3 apple group. There could be two outcomes, the first one being they have equal weight, and the second one being they have different weights. For the first situation, go to the 3rd instruction. For the second situation, go to the 4th instruction. It takes one comparison in this step.
  3. Compare either the first apple group or the seond apple group to the third apple group. If they still have the same weight, the extra apple is the problematic one. Otherwise, you can tell if the problematic apple is heavier or lighter by noting if the third group is heavier or lighter. Then go to instruction 5. This step takes one comparison.
  4. Compare either the first apple group or the second apple group with the third one. It this case, you already know that the first group and second group have different weights, and you know which one is heavier. Let’s call the group you chose as A and the other group B, while the third one C. When taking one of them to compare to the third group, you already know A != B. It’s either A > B or A < B. If you have now A = C, that means B is the problematic group and you can deduce whether the problematic apple is heavier or lighter by knowing A > B or A < B. If you have now A != C, then A is the problematic group, and you can also deduce if the problematic apple is heavier or lighter. Let’s denote the problematic group with its property, i.e. heavier or lighter in this step. This step takes one comparison. Go to instruction 5.
  5. Now you have the problematic group, and you know if the problematic apple is heavier or larger. We randomly pick two apples from the group. If they have the same weight, the rest is the problematic one. If they don’t, you should choose the heavier one or lighter one according to your prior knowledge, i.e. the problematic apple is heavier or lighter. This step takes one comparison.

So the idea is actually quite simple. Divide into 3, and you will need either once or twice comparison for this step. The amortized number of overall comparison needed is 3.