Was interviewing

this occurance alone cannot verify that you are a brainlet. there are other factors at play here. so you can calm down and accept this as a defeat and also a learning experience.

Yes, that is the anwser.
I don't know if I'm supposed to solve it without any hint during the interview.

I did in 30 seconds so I don't know why wouldn't someone else. It's high school math, after all.

generating a random number in a range is a pretty common task, you probably don't have enough programming experience, for [a, b) from [0, 1) its just a + rand() * (b - a) btw

Why the hell do you guys have to answer such questions in interviews? If you walk in with a masters in comp sci from a university nobody should question your ability to do 1st grade programming homeworks. If I'd be asked such insulting shit I'd stand up immediately and walk out. (Maybe mumbling something the interviewers mother)

>assuming rand() returns a float instead of a single bit
lmao

But the hardest part is you are not given a continuous value generator, and only a binary random generator is given.

Import random
random[0,6]

That makes more sense and is a much more difficult problem, I remember some user asking it in dpt a couple months ago

/thread

JS wins again

>Why the hell do you guys have to answer such questions in interviews?
The answer is obvious.
This is an extremely simple question that any person with any coding experience should give at least *a* answer too.
And yet OP couldn't do it, that is why the question was asked.

No, it isn't hard. The obvious solution of adding 6 results took a few seconds for me to come up.

You are asked to generate uniformly.

That isn't right. The while loop always results in a 6 if started with 7, it should refill all 3 bits instead.

Why not just do it in binary? just shit out 3 random 1s or 0s and subtract 1 so long as it's not just 0000. It'll be slightly biased due to that last bit but it's probably a shitty random number generator in the first place so who gives a fuck?

The "dirty" solution is generating a large enough integer and taking the modulos.
The easiest approach to generating a random large integer with a uniform distribution is doing something like:
Sum_i=0^n X_i*2^i
Where X_i is the random variable, this distribution is uniform since this representation of integers is unique.

But adding coin tosses gives a Binomial Distribution, or Poison Distribution if coin is biased.

You call it 6 times and sum? This gives a uniform distribution I think.

Actually it's not uniform after thinking about it for a sec but that wasn't a requirement.

>given a random 0 1 generator
Why didn't you just put that one in a loop?
>Am I a brainlet?
yes

Yes and?
It generates numbers between 0 and 6, that was the question the interviewer wanted answered.
Then you tell him why this is a bad idea for certain purposes and propose another solution.

There are at least two other ideas that immediately come to mind.
Either generating a large integer with a uniform distribution (easy for powers of 2) or generating a uniform number between 0 and 7 and rerolling if it is 7.

OP here.
Maybe I should make things clear.

You are asked to write an RNG to generate integers from 0 to 6.
The distribution of the output of your function must be uniform.
You are given a uniform random binary generator.
There are follow up questions like try to generate between M and N, where 0

redblobgames.com/articles/probability/damage-rolls.html

do {
n = (rand_bit()

given that a bell curve is still "random", you could have just put the 0/1 generator in a loop.
Then the interview could move forward to discussing results and likely turning them into an even distribution.

interview problems aren't there for you to show off you learned Cracking the Coding Interview by heart but for them to get an idea of the ways in which you solve problems.

Taking the other persons idea, just generate random binary bits which results in the greatest possible number being above the bounds.

After that just re-roll if it hits a number outside of your bound - this will result in a uniform distribution.

Am I a complete brainlet or would this work?

Attached: 1568658813423.jpg (1000x1314, 198K)

Yes, it would work, but it has a potentially infinite running time.

Yes, is there a way to overcome this though using the same method?

this board is infuriating. are you all trolling?
this is the correct answer.

R(2) + 2*R(2) + 2*R(2)

I do not think so.
Basically it is very easy to generate uniform integers to the power of two with the binary random number generator, but the problem will always remain.

That won't be uniform. That generates a Gaussian distribution centered around 3.

Can someone please explain to a brainlet why most random number generators produce normal distributions?

>The answer is obvious.

The obvious answer is wrong, which anyone with a basic understanding of stochastic will know.
If you think the interviewers are morons, that is the answer you should give. But if they aren't morons, and you can't figure out the right answer, give this one and explain why it is wrong. Better than nothing. Usually they just want to know if you can think on your feet.

uniformity is not part of OPs narration

I feel there could be a bug here, but tried again...
int rand32() {
int n = 0;
for(int i = 0; i < 32; i++) { n = 2*n + toss(); }
return n;
}

int rand_int(int max) {
int X = (MAX_INT / max);
int n = rand32();
while(n >= X*max) n = rand32();
return (n / X);
}

int rand_range(int low, int high) {
int range, n;
if(high == low) return low;

if(high < low) SWAP(high, low);
range = high - low;
n = rand_int(range);
return low + n;
}

>The obvious answer # is wrong
Nope.
It still answers the original question.
Nowhere was uniformity demanded in the OP.

>If you think the interviewers are morons
You get a question and give an answer, then you explain the drawbacks of the answer.
If they wanted something different they would ask "is this uniform" and then you explain why it isn't and give a different answer.

>why most random number generators produce normal distributions?
What do you mean?
Mostly it's uniform, eg. generating a random integer between 0 and N.

Normal distributions being common is based on the central limit theorem, basically, if you average a random process under many circumstances the result will be a normal distribution.

What does 'random' mean then?

If it's a cryptography or math related job they sure as fuck wouldn't take it. If they're a bunch of code monkeys, they wouldn't know any better. That's the real question here.

I spent the last hour trying to find a clever solution involving distributing the numbers that are twice as likely when using module up to the ones above, but then I realised that it wouldn't work and just retrying in that case properly evens out the distribution but has an unbounded run time, like you said.
I was also hoping it would be possible to do some clever bit tricks to construct a random number out of bits, but I guess not.

The likelihood of that is also infinitely low. It is the best solution in this thread if applying for a software engineer/developer job, maybe not if for a PhD.

int res = 0;
res | randint(0,1);
res | randint(0,1)

uh i meant |=

Good job, you made a distribution from 0 to 7.
Now try making one from 0 to 6.

You could just discard values over 6 and start over using a do while loop

>What does 'random' mean then?
There are infinitely many different random distributions, all of them describe "randomness" in some sense.

>If it's a cryptography or math related job
Literally just ask them.
Or say "you can sum then up and get a none uniform distribution, should the distribution be uniform?".

Anyway, this isn't a question to test your math skills it is "can you solve a basic problem" question, to check if the candidate has any clue whatsoever.

as terry said, you can be the most intelligent person on the planet, but you cannot figure out all the opening move for chess. Lack of knowledge doesn't mean lack of intelligence

Just throw out the 7s

I suppose one has to sacrifice some randomness too ensure that an infinite loop is impossible. For example give back the numbers in order each time you loop n-times, with n as only 10 this case would only have a likelihood of (1/2)^10=0,0000000009.

x = 6(2*rng_binary)
(a*4 - a) % 6

Yeah, after rerolling 10+ times you could just return a zero.
The difference to a uniform distribution would be miniscule.

int _rand (arr in)
{
if (len(in) == 1) return in[0];
return randint(0,1)? int_rand(tail(in)) : int_rand(tail(reverse(in)));
}

Attached: 1563839429769.png (425x481, 159K)

whoops typo, should be int int_rand (arr in)

why not just loop over the 0/1 generator 6 times and return the sum?
>muh distribution
they didnt specify this

1/64 chance of getting 0

Do you honestly think this is what they wanted?
This is what would happen:
>Heh yes Sir this was the solution I came up with
>Proudly tips fedora
>Well yes this is sort of a solution, but we are of course really looking for an even distribution which your code doesn't achieve
>...B-but good Sir this wasn't explicitly stated in the task??
>Yes user you might technically be right, but we're not really looking to hire an autist, we want somebody with good reading comprehension and with at least a sliver of common sense.
>...

eh the law of large numbers implies that we can just assume the chance of getting an infinite loop is the same as it's expected value, ie, 0.You're more likely to run into a processor defect than continue rolling >6 for any noticeable amount of time.

>Do you honestly think this is what they wanted?
What they wanted is to see if the person in front of them has enough braincells to rub together to solve an extremely simple problem.
Stop overthinking this, they probably expected exactly that answer and the follow up questions would be about distributions or they would just love on.

that's the equivalent of throwing away the half the applications because you don't want to hire unlucky people

Who fucking reads "random" and thinks "ahhh yes I will make an uneven distribution", if it means throwing retards like you in the trash then so be it.

>"write a random integer generator between 0 and 6 given a random 0 1 generator!"
>give a solution that returns mostly 3's
>"You're hired!"

Red flag, if you ask me.

are you guys actually autistic or what? I understand interviews are stressful but have you really not even now considered, I don't know, *asking* if they wanted a uniform distribution?

which is based btw

>Who fucking reads "random" and thinks "ahhh yes I will make an uneven distribution"
"Random" has nothing to do with a certain form of distribution.
In fact most random things aren't uniformly distributed.

But again, this is a retard question the "hello world" of the interview.

It is still random. Again, you do realize that the interviewer expects such answers and wants to discuss them to see if you actually understand them?

int seed(void)
{
int res = 0;
int i = 32;
while(i--)
res |= randint(0,1)

>random
By what definition?

merriam-webster.com/dictionary/random

The solution has a clear pattern. It's called a poisson distribution.

That does not create a random uninform number. The anons use bit shifts and what not are getting the correct answer.

It is an amusing question I encountered the same issue once when writing something in befunge.

>By what definition?
The definition used in any probability theory course.

>The solution has a clear pattern. It's called a poisson distribution.
A uniform distribution has a very clear pattern too.

Well yeah you're right, (1/2)^n decreases much faster than n increases.

>return seed%(end-begin) + begin;
should be seed()

>The definition used in any probability theory course.

Which is? "It could be anything, but it mostly is the stuff in the middle"?

>eh the law of large numbers implies that we can just assume the chance of getting an infinite loop is the same as it's expected value
What?
You don't need the law of large numbers for that lmao...

>Which is?
It should be known to you if you discuss such matters.

See eg. libgen.is/book/index.php?md5=EDF8B50556411915E32AFC152B2E7043 page 4
If you need a quick refresher on what a "random variable" is.

how would you generate a binary value from 0 to 6 using only a generator that returns 0 and 1

ESL brainlet here - what is the goal in op's question, i'm not sure i get it
>given a function that returns either 0 or 1, write a function that returns a random number between 0 and 6 using that function
is that right?

based, truly the most patrician of languages

>the reading comprehension of jslets

see

ah, thanks user, somehow missed that

so you have a
genBinary() that returns either 0 or 1
and at the end of the day you want to generate
000
001
010
011
100
101
110
right?

Create a state machine of 0 to 6 states. Hard code a random state transitions with the degree of each state being equal. Use rand(0,1) to choose to which state your transition. It is semi predictable but do it 3 times consecutively for each rand(0,6) and you are very likely to have an unpredictable generator that gives a random number in a constant and predictable amount of time. You can even put all the state transitions in a matrix.

matrix =
[ [ 5,6],
[ 4, 1],
[ 6, 3],
[ 1, 5],
[ 3, 0],
[ 5, 2],
[ 0, 4]]

randnr=0;

int rand06(int randnr){
randnr = matrix(randnr, rand(0,1));
randnr = matrix(randnr, rand(0,1));
randnr = matrix(randnr, rand(0,1));
return randnr;
}

The contents of this matrix are shit as you would ideally create a matrix where the smallest loop is at least as bib as the consecutive amount of state transitions. Obviously this generator scales horribly but good enough for small numbers.

>must be random
>must be uniform
uhhhhhh

#include

int main(void) {
return rand() & 0x00000007;
}

Assuming ints are 32-bits of course

Now that I think about this, this will also sometimes return 7.
Maybe you should convert the output of rand() to base 7 and just return the least significant number instead.

nice solution! So far so good, after 10263629 still it did not fall into infinite loop. Most numbers are choosen after 2 recursive calls.

import random

def randBin():
return random.randint(0,1)
def random6(it=0):
print(it)
if randBin()==0:
if randBin()==0:
if randBin()==0:
it+=1
return random6(it)
else: return 0
else:
if randBin()==0: return 1
else: return 2
else:
if randBin()==0:
if randBin()==0: return 3
else: return 4
else:
if randBin()==0: return 5
else: return 6
#print(randBin())

for i in range(0,10000000000000000000000000000000):
print(str(i)+" th iteration")
print(random6())

i really like this solution, really clever

Based on
int random(int M, int N) {
int max = N-M;
if (max

>It is still random
So is "if 0 return 0, else return 6" but the interviewer would still think you're retarded for presenting that.

Nice to see it working :-)

Do this >Ok user, but what if we want a uniform distribution?
Cast the first 3 results to an integer. If you get 7, try again

>Ok, but can we do it in a single pass?
No, the number of possibilities must be both a power of two, and a multiple of 6. That is impossible

>How about something that is close enough?
Cast the next 32 bits to an int, then mod it by 6.