About the non-trivial seduction of the tester Claudia: tasks from the booklet GridGain with JBreak and JPoint

    The next Java-conferences JBreak and JPoint passed with a bang. The presentations here always resonate, but many still remember something else.

    GridGain Booklet. Problems about Gref and Ballmer, a Belarusian programmer with a bucket of potatoes, and, of course, the non-trivial seduction of the tester Claudia continue to be published on various resources to the delight of the author, and many do not even know what their source is.

    We are telling. The tasks were specially composed by the chief architect of the GridGain core team, Sergey Vladykin, and after that were solved by all the other participants.

    We know that for most conference attendees, the main difficulty was task number 1. Do not be discouraged, it was the same among GridGain employees! But, in fairness, it should be noted that at Moscow JPoint there were 3 people who solved all 4 problems correctly and transferred their results to us.

    The country! Know your heroes! It:

    • Alexey Ostrikov
    • Anna Gusentsova
    • Ivan Smolyaninov

    Today we publish solutions to problems: for those who remember them well, and for those who see them for the first time. Have fun!

    It seems to us that the main difficulty for the participants was caused by two seemingly contradictory statements: on the one hand, German Oskarovich and Steve agreed to transfer the bytes in turn, on the other - they can talk and listen at the same time. The subtlety is that if each of the participants can distinguish a word from silence in 0.05 seconds, then the last bit in a byte can be distinguished in 0.05 seconds (even if it was a word encoding “1”) and start transmitting the next byte in the opposite direction. Therefore, the transmission time of the first seven bits in a byte depends on the value of the byte, and the last bit can always be transmitted in 0.05 seconds.

    Then it remains only to calculate the average transmission time of one byte in each direction. Since the values ​​of bits “1” and “0” are equally probable, the transmission time of one byte in one direction is

    $ {1 \ over2} ({1 \ over7} + {1 \ over20}) \ times7 + {1 \ over20} $

    seconds, the transmission time of one byte to the other side is

    $ {1 \ over2} ({1 \ over11} + {1 \ over20}) \ times7 + {1 \ over20} $

    seconds. The total transmission time of two bytes in both directions is

    $ {1 \ over2} ({1 \ over7} + {1 \ over11} + {1 \ over10}) \ times7 + {1 \ over10} $

    seconds, and accordingly, the bandwidth in bits is

    $ {16 \ over {1 \ over2} ({1 \ over7} + {1 \ over11} + {1 \ over10}) \ times7 + {1 \ over10}} \ approx12.62 \ text {bps} $

    It is also worth noting that it is incorrect to carry out similar calculations with frequencies, since averaging frequencies violates the assumption of a uniform distribution of “1” and “0” in bits.

    It is clear that both drug addicts are involved in the transfer of the syringe, therefore only the first and third steps can be performed in parallel, and the time of this parallel execution will be equal to the maximum of T1 and T3, while during the transfer of the syringe, neither the first nor the second drug addict can perform other actions , that is, the transfer of the syringe will be performed sequentially with other steps. Therefore, the answer:

    $ \ max (T1, T3) + T2 $

    In this task, we need to optimize the average number of potatoes that fall into the bucket per unit of time, which is equal to the product of the number of potatoes collected per unit of time by the probability that this potato will fall into the bucket. If x is the distance of the programmer from the bucket, then the average number of potatoes is calculated by the formula

    $ V (x) = (0.5 + x) (1-0.25x) = - 0.25x ^ {2} + 0.875x + 0.5 $

    The quadratic function reaches its extremum (in this case, the maximum) at the point

    $$ display $$ - {b \ over2a} = {0.875 \ over2 \ times0.25} = 1.75 $$ display $$

    Innocent will meet Kondraty in the haylord if Claudius fails to reproduce the bug in 90 minutes of testing, but still finds it during the QA-lead test run. It is clear that each of the tests is independent of the other, so the final probability will be equal to the product of the probabilities of each of the events. Since pick-up is displayed at the end of the test run, we are only interested in the number of complete test runs in 90 minutes, which is equal to

    $ \ text {floor} ({90 \ over17}) = 5 $

    The probability that the bug cannot be reproduced in 5 test runs is

    $ (1-0.11) ^ {5} $

    which means that the probability that after 5 successful test runs the bug will play on the test run is equal to

    $ (1-0.11) ^ {5} \ times0.11 = 0.0614 $

    PS Thanks for the efforts of all those who took the time at the JPoint and JBreak conferences to solve these problems. And there were many of them that cannot but rejoice!

    Also popular now: