This is the 14th day of my participation in the genwen Challenge

This series is a little bit fancy, just to expand your thinking, kind of intelligence questions, usually not in the interview, but some factories will ask some, as far as I know, some departments here will ask some of these, and then say in the group: “Alas, the whole army was destroyed again, -_-“, I curiously looked at the group, take out this problem, although can be solved, but really in the spirit and time pressure should not be easy to do. I thought of this, so I created a column to help you in your interview.

1. It doesn’t matter if you can’t solve this kind of problem. This is the attitude you should have, 2. If you can’t do the answer, it is also good to organize your thoughts. In fact, the interviewer may be looking at your reaction to the problem and the pressure, not the question itself.

I once passed a mensa test on 33IQ in high school. I still have confidence in myself, but as time goes by, I increasingly think patience and perseverance are the only way to grow wisdom, so work hard ^-^

Besides, isn’t it a little boring to watch the algorithm series every day?

1. Accounting and testing

Topic describes

Have 1000 passengers, have 1 person positive sex interfuse among them, but kit is serious insufficient now, have 10 only, how can ability find this person out? The kit can be reused, as long as it is tested by a positive person, it will turn red after 10 hours.

Train of thought

When I got this problem, I initially responded that there was no solution, whether it gave me a brain teaser (such as someone with real eyes), but there was no solution at all, playing word games or something, but after my colleague gave me the answer that there was definitely a solution, I ruled out the possibility of no solution and began to seriously think about this problem. In fact, this also saves a wave of things, I am afraid that some students directly by intuition feel impossible, and then to the word game direction more and more far.

Maybe I majored in mathematics and was sensitive to numbers. Fortunately, I directly thought of the right path

  1. Ten boxes to test 1,000 people,2 ^ 10 = 1024Well, we should use binary.
  2. I started with the simple problem, don’t start with 1000, since it’s related to binary, when I think of two, I start with how many people need 2, 4(2 ^ 2) How many do individuals need, 8(2 ^ 3(How many people need?
  3. Decomposition problem
    • How do I reuse the kit, how do I quantify it and how do I number it
    • How do you find that person

If it is 2 people, should not have what to say, direct 1 kit is enough, choose the first person to test (number 0), 10 hours after the red => (0 is positive) otherwise, another person (number 1) is positive.

If we have four people, we can number them 0, 1, 2, 3, and these numbers can be represented in binary as 00, 01, 10, 11, and we can see that there are two bits of binary that can be represented, as shown in the figure below

Test box 1 Test box 2 Personnel ID [0] 0 0 [1] 0 1 [2] 1 0 [3] 1 1Copy the code

Correspondingly, our test box 1 is for people numbered [2], [3] test, and test box 2 is for people numbered [1], [3]. In fact, this is the position corresponding to 1 in the picture, which means using the kit. Ten hours and we looked at the results.

There are several possibilities:

                Box 1 ` ` tryRed |Box 1 ` ` tryDid not turn redBox 2 ` ` tryTurn red` [3] positive `        |   ` [1] positive `Because looking at the figure above, only [3Box | for try2For [1Has been measured]2A box to he tried | and [1No trial box was given1Measurement, other all don't meet |Box 2 ` ` tryDid not turn red` [2] positive `        |   ` [0] positive `Similarly, you can speculate | backstepping by oneself, don't become red, if it is [1], [2], [3] | some positive, the result will not so, box must be in redCopy the code

It’s even clearer if you draw it as a binary tree:

Root/kit 11 red 0 not red/kit 2 1 red 0 not red 1 Red 0 Not red path 11 10 01 00 Positive id [3] [2] [1] [0]Copy the code

At this point, we can tell that the problem can indeed be solved in this way to find out who is positive, and then we can expand it to eight people, which, by inference, should be detected with three kits, since binary 000-111 represents eight people. => 1000 can indeed be tested with 10 boxes. (2^10 > 1000), good we’re on the right track.

Let me draw 8 people

Try the box1Try the box2Try the box3Staff No. [0]         0       0      0           000Binary is0
[1]         0       0      1           001Binary is1
[2]         0       1      0: [3]         0       1      1: [4]         1       0      0
[5]         1       0      1           101Binary is5
[6]         1       1      0: [7]         1       1      1
Copy the code

Test according to the corresponding position, for example, test box 1 is arranged on [4],[5],[6],[7], and test results are completed. Finally, find out the final positive patient according to the binary tree path of kit results.

                  root
                 /    \
               0       [1] kits1Results hypothesis1/ \ \0   1    [0]   1test kit2Results hypothesis0/ / \ \ / \ \0  1 0  1 0 [1] 0  1test kit3Results hypothesis1Description No. [5] are positive.Copy the code

And then at the end of the day it goes back to 1,000 people, and I’m not going to write it.

In addition, we recommend another series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithms disassembly series remember to like ha

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference