Hacker News Reader

> The guy offered no hints when I wasn't sure where to start, he simply continued to repeat the question, a bit slower each time

I hear the same approach works really well when trying to talk to someone that doesn't understand english

I’m in Germany, and I keep forgetting to ask them to slow down when they German at me too quickly. Of course, when they know I’m English, then they English at me and I don’t learn German anyway…

nope, it's louder and always at the same speed.

Maybe it does? When I was learning Russian, it just helped to hear everything slowed down by 2x.

>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.

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.

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)?

Writing a regex at a Google onsite? For SWE?

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.

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"

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

You can't run statistical methods on a single number though

> 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.

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

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

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.

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.

Won’t that be true for any number though? Might as well cut out steps and say accept all numbers as random.

Of course. But now you proved it.

Define a PDF thus:

1 when n = number, 0 everywhere else

Re 2.: It's not possible to prove that a single number is random. You can run some tests on a series of numbers. If this were me getting that question, I would first say that I'd google for some standard tests, then if being asked if I know some by heart, I would start with the average and standard deviation, then I would draw a histogram and expect the distribution to be flat and finally I would try to visualise the numbers in a two-dimensional grid and look for patterns. A truly random number generator doesn't produce patterns.

There's a difference between random and uniformly distributed.

No. Numbers have to be uniformly distributed in order to be random, since Randomness is the lack of pattern or predictability in events[1].

You can randomly sample from any distribution, but as long as you do it from a non-uniform distribution, you can start predicting the pattern (e.g. if you are sampling from a gaussian, you can start predicting median value)

[1] https://en.wikipedia.org/wiki/Randomness

If you follow that assertion, a great number of mathematical concepts become meaningless, e.g. probability distribution.

That assertion is even at odds with the second and third sentences of the article you linked.

> A random sequence of events, symbols or steps has no order and does not follow an intelligible pattern or combination. Individual random events are by definition unpredictable, but in many cases the frequency of different outcomes over a large number of events (or "trials") is predictable. For example, when throwing two dice, the outcome of any particular roll is unpredictable, but a sum of 7 will occur twice as often as 4. In this view, randomness is a measure of uncertainty of an outcome, rather than haphazardness, and applies to concepts of chance, probability, and information entropy.

It's funny how this thread shows the exact problem identified in the article : a LOT of people have some basic idea of how to answer the question, and come up with strong opinions they "know" are right, and arguing with others.

Fact of the matter is that the question is too general, and there are no real answers to it that aren't extremely general themselves.

(One mistake in your response would be that obviously random numbers are taken from a particular distribution, and of course there is some information there about what to expect the next random number to be. Taken to an extreme you can take random numbers from the collection {1}. Can you predict what the next random number will be ? I think I can ... Too general questions means you have to take trivial cases into account)

I wonder how many of the posters into this thread would reject candidates based on the candidates strongly disagreeing with their statements. Especially because I've got a degree in statistics and I would agree with that this question can't be answered.

um no. Even on an infinite sequence, it's infinitely unlikely to get a flat distribution. That's what's annoying about real randomness, compared to 'a flat distribution'.

Well don’t they flatten out over time? That’s my understanding of randomness any way...

Do you think that the sum of rolling two dice isn't random? That isn't a uniform distribution.

I guess that’s true.

More generally, one should probably say that random numbers taken from a distribution match that distribution.

Taken to an extreme one might ask, can you predict random numbers taken from a collection with only one element. Obviously you can predict the next number. It'd be like a roulette wheel with only red numbers. The outcome is random, but perfectly predictable to be red.

Yes it will. This is called the Law of Large Numbers: https://en.wikipedia.org/wiki/Law_of_large_numbers

The interviewer asked "to prove a number is truly random". You can't prove randomness, you can only disprove it.

I'm currently interviewing with a company where the HR person in charge of my case left the company. My emails to him were getting Postmaster responses, so I emailed someone else asking what happened, and apparently no one knew that I was just hanging out in interview limbo.

Being proactive in your interviews never hurts; so long as you aren't bombarding them with emails it's unlikely to hurt your application.

I get that things just happen sometimes, but, wow, does this sound like a red flag against working there to me.

People quit, things happen, need more info.

>2. Google, for not being able to, "prove a random number is truly random,"

This definitely does not seem like a question that should be in a coding interview. However, this is an answerable question under certain assumptions.

It's possible to make a source of randomness more entropic. (c.f. https://en.wikipedia.org/wiki/Randomness_extractor)

What we can do is slice up the number into a given length and estimate the H_{\infty} entropic measure among our sliced-up numbers, treating the numbers as samples from some random source.

edit: if for example you're a crypto researcher, then this question seems warranted.

IS 17 RANDOM OR NOT?!

Can't be. It's all straight lines.

Obviously not, your RNG has a bias toward prime numbers.

I'm changing my pin to a better code again. Four fours, but I'm setting their sequence to be completely random !

4, 4, 4, 4. Checks out, totally random.

The three onsite days were paid I hope? If a coding task takes longer than four hours I ask companies to pay for it.

Honestly, I have not heard of this before. Is this real? Is this common? How does asking to be paid for an interview pan out?

At Level 12, we pay for the time spent taking our skills tests. About 16 hours worth if a candidate makes it through all phases. But I've not paid for the on-site interview, other than travel expenses for remote candidates.

Sixteen _hours_ of testing? I would've disqualified myself after the first hour. That's insane.

He's saying that's in total/spread out, but still seems on the high side. Between a take-home coding challenge (2h?), online coding challenge (1h), talking to recruiter/HR/hiring manager (1h), multiple interviews (coding 1h, culture/fit 1h, system design/architecture 1h, whatever 1h), you're already at 8 hours for a lot of places.

I appreciate them even knowing how long a person would spend on their interview process though.

Since I am an external recruiter, I ask for payment on behalf of my candidates but I can imagine if you formulate it nicely that it might work out, too without having a recruiter representing you.

You can argue that you are interviewing with five companies and all have 4-8 hours coding task, you can't possibly do all of them and you will just do three maximum.

We offer candidates pay for any code they write for us in "real" projects we use to judge them on. Only fair and square.

> 2. Google, for not being able to, "prove a random number is truly random ...

You should have referred to xkcd's getRandomInteger function: https://xkcd.com/221/

Downvotes? Maybe you should have gone with Dilbert's version?

http://dilbert.com/strip/2001-10-25