Three interesting questions

Yesterday, we talk about three interesting questions in the cuisine and luckily I have found the answers by myself for this three enigma. Now, I share them with you.

[Probability and a series of number]
A series of integers are coming but we don't know the total number of these integers. We have a fix number of memory. Try to design a way to give one number of them randomly.

Idea: Because we don't know the number, so in fact we keep the random during all the process. We start from the simple case. We we given one number, we just keep it. But once we have two, we must update it with the prob 0.5. That is the key. Once we know the total number until now, we have the method to update the data randomly.So two memory is OK.

[Find the polynomial]
We are given a polynomial of degree integer positive. We have two chance to test the polynomial by value. How we find it?

Idea: Intuitively, this is not so logical because in maths we know we can construct a polynomial of certain zeros. But pay attention to the positive integer coefficient. The addition of one polynomial cannot always be correct.

The correct way to think by maths: if we can separate the coefficient, we get it. But to separate the coefficient we have to know the range, so the first chance we can use it to test the range of coefficient. For example, we put 1 in it. We get the range. We put 100000~0 to it, then we get the coefficient.

RMK: It is said that this method can be used to attack the HashCode.

[The most frequent number]
Once again, we are given a series of integer and we know that there is one number which appears more than half of it. We don't know the number, try to find it.

Idea: this is one in which I use the most of time. I got the answer by intuition and then prove it by maths. We get one number, count the number from it, count the number it occurs. If the frequency is lower than half, erase all the data and re gain the number.

A better arrangement can reduce the memory to two. But the heart of this idea is that if we do partition of the interval, at least from one point, the frequency of this number is always above 0.5.