A painful interview question

I saw two interview questions yesterday. There were two questions. Many people answered the first question, but few people answered the second question. I am learning PHP recently, so this article uses PHP as the basis to bring the second analysis today.

Attached are two interview questions:

　　1: There are 100 lights in the hall, and each light is numbered, ranging from 1-100. Each light is controlled by a switch. (When the switch is pressed once, the light turns on, and when pressed again the light turns off. The number of the switch is the same as the controlled light.) At the beginning, all the lights are off. Now press the switch according to the following rules.
For the first time, light up all the lights.
For the second time, press all the switches that are multiples of 2.
For the third time, press all the switches that are multiples of 3.
And so on. For the Nth time, press all switches that are multiples of N.
Ask how many lights are still on in the hall after pressing the button for the 100th time.
　2: There is a 27 cm thin wooden pole, and there is an ant at each of the five positions: 3 cm, 7 cm, 11 cm, 17 cm, and 23 cm. The wooden pole is very thin and cannot pass an ant at the same time. At the beginning, it was arbitrary whether the ants' heads were facing left or right. They would only walk forward or turn around, but not retreat. When any two ants meet, they will turn around and walk in opposite directions at the same time. Suppose ants can walk one centimeter per second. Write a program to find the minimum time and maximum time for all ants to leave the wooden pole.

The first one is relatively simple and I won’t go into details about it, but the second one makes people have a headache just by looking at it.

　 Let’s briefly analyze this question.

Judging from the question itself, it seems that considering the positions of five ants at the same time is really confusing. Fortunately, the last sentence of the question is still very useful. It is the maximum time and minimum time for all ants to leave the wooden pole. Use the thin rod as a horizontal axis. The positions of the ants have been given. When the position of the last ant leaving is <=0 or >=27, all ants leave the wooden pole. (This seems to be nonsense.)

　 1 meter per second, this kind of question setting is enough to make people comfortable. After all, the time the ant moves here is numerically equal to the distance the ant moves. (If it is considered that all ants leave the wooden pole and continue to move at the original speed). And they move simultaneously.

Ants have only two directions of movement, left or right. Considering the actual situation of the coordinate axes, if we assume that moving to the right is 1, then the equivalent movement to the left is -1. It is very important to consider this step in the binary world of computers.

　Okay, here’s the foreshadowing. Whether you understand it or not, here’s the more important content.

　Finding the maximum time and minimum time is just like finding the maximum and minimum numbers in a pile of numbers. This kind of thing should not be difficult. The key is to find the last time to do the comparison. What does time have to do with anything? Judging from the title design, it should only be related to the initialmotion state of each ant. As for the movement status of a certain ant at a certain moment during the period, do we need to worry about it? No need. That would only complicate the problem.

How many initial states are there for ants? 2^5=32. Obviously each of these 32 types of time needs to be calculated, and a simple loop can be used.

　 Focusing on the movement status of ants is nothing more than two variables: position and direction. So here I simply introduce two arrays $arr and $b. The former is used to describe the current position of a certain point, and the latter is used to describe the current direction. $b[i]

As described previously, the value should only be -1 or 1.

Considering this, we can straighten our thinking and assign an initial value to the arrays '$arr' and '$b'. Use time '$i' to make a loop. After each ant moves every second, when '$arr[$k]==$arr[$k-1]', change the matching state value '$b[k ]' value. When the 'value' of all '$arr' is <=0 or >=27, stop looping and return '$i'. A lot of loop traversal is used. Of course, for simplicity, when '$arr[$k]' is no longer on the pole, you can use the unset() function to delete it. Finally, it is judged that '$arr' is empty to end the loop.

After talking about the main content, we still have to deal with a small detail. How to generate the array "$b" that describes the movement status of ants?

It can't be generated manually. There are 32 situations for 5 ants, and 1024 situations for 10 ants. It's really painful to generate. But you obviously know to generate 32 arrays, so you have to use it. Therefore, it is easy for us to think of converting a decimal number into a binary number of length 5. Then replace the 0 in this binary number with -1. Convert the replaced string into an array.

　Finally, paste the corresponding code:

<?<span>php
</span><span>for</span>(<span>$j</span>=0;<span>$j</span><32;<span>$j</span>++<span>){

    </span><span>$var</span>=<span>sprintf</span>("%05b", <span>$j</span><span>);

    </span><span>$var</span>=<span>str_replace</span>('1', '1|', <span>$var</span><span>);
    </span><span>$var</span>=<span>str_replace</span>('0', '-1|', <span>$var</span><span>);

    </span><span>$b</span>=<span>explode</span>('|',<span>$var</span><span>);

    </span><span>$res</span>=getRes(<span>$b</span><span>);


    </span><span>if</span> (<span>isset</span>(<span>$min</span><span>)) {
        </span><span>if</span> (<span>$res</span><<span>$min</span><span>) {
            </span><span>$min</span>=<span>$res</span><span>;

        }
    }</span><span>else</span><span>{
        </span><span>$min</span>=<span>$res</span><span>;
    }
    </span><span>if</span> (<span>isset</span>(<span>$max</span><span>)) {
        </span><span>if</span> (<span>$res</span>><span>$max</span><span>) {
            </span><span>$max</span>=<span>$res</span><span>;
        }
    }</span><span>else</span><span>{
        </span><span>$max</span>=<span>$res</span><span>;
    }
    </span><span>print_r</span>(<span>$b</span><span>);
    </span><span>echo</span> "此次结果是".<span>$res</span>.'   $max='.<span>$max</span>.'  $min='.<span>$min</span><span>;
    </span><span>echo</span> "<hr/>"<span>;

}


</span><span>echo</span> "最大值是".<span>$max</span>."最小值是".<span>$min</span><span>;


</span><span>//</span><span>获得某种情况下的时间</span><span>function</span> getRes(<span>$b</span><span>){
    </span><span>$arr</span>=<span>array</span>(3,7,11,17,23<span>);
    </span><span>for</span>(<span>$i</span>=1;<span>$i</span><100;<span>$i</span>++<span>){

        </span><span>foreach</span> (<span>$arr</span><span>as</span><span>$k</span> => <span>$val</span><span>) {
            </span><span>$arr</span>[<span>$k</span>]=<span>$val</span>+<span>$b</span>[<span>$k</span><span>];
            </span><span>if</span> (<span>$arr</span>[<span>$k</span>]==@<span>$arr</span>[<span>$k</span>-1<span>]) {
                </span><span>$b</span>[<span>$k</span>]=-<span>$b</span>[<span>$k</span><span>];
                </span><span>$b</span>[<span>$k</span>-1]=-@<span>$b</span>[<span>$k</span>-1<span>];
            }

            </span><span>if</span> ((<span>$arr</span>[<span>$k</span>]>=27)||(<span>$arr</span>[<span>$k</span>]<=0<span>)) {
                </span><span>unset</span>(<span>$arr</span>[<span>$k</span><span>]);
            }
        }


        </span><span>if</span> (<span>empty</span>(<span>$arr</span><span>)) {
            </span><span>return</span><span>$i</span><span>;
        }


    }

}</span>

　 PHP is not good at mathematical operations, and the author is not good at mathematical operations. I feel that the code I wrote above can barely complete the task. I also hope to get your guidance.

The above introduces a painful interview question, including the relevant aspects. I hope it will be helpful to friends who are interested in PHP tutorials.