4 ms·

>Google, for not being able to, "prove a random number is truly random," I really hope they just wanted you to argue that the task is impossible.

skosch 9y ago
Or maybe bring up some heuristics (https://en.wikipedia.org/wiki/Diehard_tests https://en.wikipedia.org/wiki/Diehard_tests) – but of course proving a negative is always a futile exercise.
- fgonzag 9y ago
  You can't run statistical methods on a single number though
GoToRO 9y ago
It's not impossible: make a dice with all the numbers up to that number; throw the dice until it falls on that number; done.
- PeachPlum 9y ago
  Define a PDF thus: 1 when n = number, 0 everywhere else
- matthewbauer 9y ago
  Won’t that be true for any number though? Might as well cut out steps and say accept all numbers as random.
  - GoToRO 9y ago
    Of course. But now you proved it.
xrisk 9y ago
If the last 'n' generated numbers were also given to you, this seems like a fair task - to check the randomness of a sequence of numbers. Wikipedia has an article about "randomness tests". [1] An example algorithm could determine if a run of integers represents a random sequence with some probability 'p'. [1]: https://en.m.wikipedia.org/wiki/Randomness_tests https://en.m.wikipedia.org/wiki/Randomness_tests
- hanbura 9y ago
  Those tests can "disprove" that a sequence is random (quotes because of course a true random generator will occasionally generate suspicious sequences of arbitrary length) But you can't prove that a sequence is indeed random: the sequence [sha256(1), sha256(2), sha256(3), ...] passes the usual tests and isn't even clever. For any set of tests you can write a pseudo random generator that passes them
wolfram74 9y ago
Yeah, my first reaction to that prompt is "it can't be done. Saying whether or a not /a/ number is random is meaningless, only sequences of numbers can be treated with statistical methods"
Bahamut 9y ago
Reminds me of a question one interviewer asked me to do at the very beginning of the session when I did my first onsite at Google - write a regex for emails. I told him no, and explained why. He then asked me to write a naive email regex to catch a simple situation, which I subsequently did.
- aaronchall 9y ago
  This makes sense as an interview question. Will the interviewee push back when asked to do something impossible? Will they then demonstrate that they can do some simpler case (which will minimize mental switching costs for both the interviewee and interviewer)?
- akhilcacharya 9y ago
  Writing a regex at a Google onsite? For SWE?
seattle_spring 9y ago
> I really hope they just wanted you to argue that the task is impossible. Pretty dumb fucking thing to ask a front end engineer to do, if you ask me.
vorotato 9y ago
I actually would argue that a single number alone is always random. This is because a pattern is a recognizable arrangement of elements. A single number is a single element and cannot be arranged, and so it has no pattern. Since the definition of randomness is the lack of a pattern, and a single number can never have a pattern then a single number is always random.
joebubna 9y ago
To prove a random number is truly random you would have to prove the random number generator that gave it to you is truly random. If the output was plotted (from the minimum possible output to the maximum) and run a sufficient number of times, I would expect the chart of the output to have a very good distribution, and not have any serious hotspots. To prove this, my solution would probably go something like: Probability of number N being output = 1 / MaxPossibleNumber Then I would run a test a sufficient number of times (depends on what MaxPossibleNumber is) such that as the amount of numbers generated approaches infinity, the percentage of times any particular number is output approaches 1/MaxNumber. The harder part would be making sure sequences of numbers don't repeat. In addition to looking at the total distribution, I think I would also want to log the order in which the numbers were generated and then run an algorithm that looks for sequence repeats. I am NOT familiar with how random number generators work, so this is a naive solution off the top of my head and could be completely wrong, but w/e.

skosch 9y ago

Or maybe bring up some heuristics (https://en.wikipedia.org/wiki/Diehard_tests https://en.wikipedia.org/wiki/Diehard_tests) – but of course proving a negative is always a futile exercise.

fgonzag 9y ago
You can't run statistical methods on a single number though

GoToRO 9y ago

It's not impossible: make a dice with all the numbers up to that number; throw the dice until it falls on that number; done.

PeachPlum 9y ago
Define a PDF thus: 1 when n = number, 0 everywhere else
matthewbauer 9y ago
Won’t that be true for any number though? Might as well cut out steps and say accept all numbers as random.
- GoToRO 9y ago
  Of course. But now you proved it.

xrisk 9y ago

If the last 'n' generated numbers were also given to you, this seems like a fair task - to check the randomness of a sequence of numbers. Wikipedia has an article about "randomness tests". [1] An example algorithm could determine if a run of integers represents a random sequence with some probability 'p'. [1]: https://en.m.wikipedia.org/wiki/Randomness_tests https://en.m.wikipedia.org/wiki/Randomness_tests

hanbura 9y ago
Those tests can "disprove" that a sequence is random (quotes because of course a true random generator will occasionally generate suspicious sequences of arbitrary length) But you can't prove that a sequence is indeed random: the sequence [sha256(1), sha256(2), sha256(3), ...] passes the usual tests and isn't even clever. For any set of tests you can write a pseudo random generator that passes them

wolfram74 9y ago

Yeah, my first reaction to that prompt is "it can't be done. Saying whether or a not /a/ number is random is meaningless, only sequences of numbers can be treated with statistical methods"

Bahamut 9y ago

Reminds me of a question one interviewer asked me to do at the very beginning of the session when I did my first onsite at Google - write a regex for emails. I told him no, and explained why. He then asked me to write a naive email regex to catch a simple situation, which I subsequently did.

aaronchall 9y ago
This makes sense as an interview question. Will the interviewee push back when asked to do something impossible? Will they then demonstrate that they can do some simpler case (which will minimize mental switching costs for both the interviewee and interviewer)?
akhilcacharya 9y ago
Writing a regex at a Google onsite? For SWE?

seattle_spring 9y ago

> I really hope they just wanted you to argue that the task is impossible. Pretty dumb fucking thing to ask a front end engineer to do, if you ask me.

vorotato 9y ago

I actually would argue that a single number alone is always random. This is because a pattern is a recognizable arrangement of elements. A single number is a single element and cannot be arranged, and so it has no pattern. Since the definition of randomness is the lack of a pattern, and a single number can never have a pattern then a single number is always random.

joebubna 9y ago

To prove a random number is truly random you would have to prove the random number generator that gave it to you is truly random. If the output was plotted (from the minimum possible output to the maximum) and run a sufficient number of times, I would expect the chart of the output to have a very good distribution, and not have any serious hotspots. To prove this, my solution would probably go something like: Probability of number N being output = 1 / MaxPossibleNumber Then I would run a test a sufficient number of times (depends on what MaxPossibleNumber is) such that as the amount of numbers generated approaches infinity, the percentage of times any particular number is output approaches 1/MaxNumber. The harder part would be making sure sequences of numbers don't repeat. In addition to looking at the total distribution, I think I would also want to log the order in which the numbers were generated and then run an algorithm that looks for sequence repeats. I am NOT familiar with how random number generators work, so this is a naive solution off the top of my head and could be completely wrong, but w/e.