During an interview I was asked to implement a random generator in java without using any existing random number libraries that takes as an argument int n, and returns a random number between 0 and n. This was the implementation I provided:

public static int random(int n) {
    int r = 0;
    for (int i =0; i <n;i++) {
    return r;

// helper that returns 0 or 1
private static int helper() {
    long t = System.nanoTime();
    if (t%2 == 0) {
        return 1;
    } else {
        return 0;

He said it's not right but he wouldn't tell me what he was expecting. Why did he say it's wrong? How would you have done it differently?

  • 2
    Did he specify that you needed to return deviates from the uniform distribution? Commented May 26, 2012 at 2:32
  • 4
    I assume he didn't say he wanted a good one. Most people don't know how to make a good one, and even if one did, there are many ways to do it. So there's no one "right" solution. I'd call yours good enough, given that simple ones that use bit shifting and XOR aren't very random. If you were on a Linux system, you could read from /dev/random, but that might be cheating. Commented May 26, 2012 at 3:06
  • 8
    Next time, tell them that such tests are called reinventing a square wheel
    – jfrankcarr
    Commented May 26, 2012 at 5:26
  • 2
    @jfrankcarr: Absolutely, I'd have answered - "Why bother, there have been better mathematicians than I writing these for years. Use those"
    – James
    Commented May 26, 2012 at 10:52
  • 2
    I've been sick and tired of such stupid tests, it happens to me sometimes and it's just unfair. They throw away all of your past experience and accomplishments because of such stupid tests. Just like some websites that presents you tests with tricky options, like same answers changing a , to a . just to fool you. My knowledge is meant to build powerful systems, there is a good IDE to prevent me from typos like this. Unfortunately the world is becoming full of this. Commented Jul 3, 2016 at 13:23

8 Answers 8


Main issues with your approach:

  • System.nanoTime() isn't (on its own) a useful source of random bits - it's highly likely to produce the same value multiple times in a row if you call it in quick succession because many systems don't actually have a sufficiently accurate timer. Even if it was nano-second-accurate, you are likely to get predictable patterns from the lowest bits if you sample it in a tight loop. Valid uses of System.nanoTime in random number generation might be: a) one-off initialisation of a seed value or b) occasionally adding some extra randomness into an entropy pool (not guaranteed to be beneficial, but it can't hurt)
  • Even if the bits were truly random, by adding the 0/1 values n times you would be creating a binomial-style distribution with a mean of n/2, i.e. not a uniform distribution which is presumably what the interviewer was expecting.
  • Your algorithm is O(n) - not good for generating random numbers with a large value of n!

You ideally want a PRNG that produces new pseudo-random bits from an internal state. Here's the one I use:

private static volatile long state = 0xCAFEBABE; // initial non-zero value

public static final long nextLong() {
  long a=state;
  state = xorShift64(a);
  return a;

public static final long xorShift64(long a) {
  a ^= (a << 21);
  a ^= (a >>> 35);
  a ^= (a << 4);
  return a;

public static final int random(int n) {
  if (n<0) throw new IllegalArgumentException();
  long result=((nextLong()>>>32)*n)>>32;
  return (int) result;

This is based on George Marsaglia's XORShift algorithm. It produces good pseudorandom numbers and is very fast (typically even faster than a Linear Congruential Generator since the xors and shifts are cheaper than multiplies and divides on most hardware).

Having said that, I wouldn't expect people to memorise this kind of algorithm for an interview unless you are specifically applying for a role as a crypto programmer!

  • 3
    "Having said that, I wouldn't expect people to memorise this kind of algorithm for an interview unless you are specifically applying for a role as a crypto programmer!" Totally agree.
    – RandomGuy
    Commented Oct 18, 2017 at 10:57

first you have a binomial distribution (values towards n/2 are more likely to occur than 0 or n-1)

a better way would have been to generate ceil(log2(n)) bits and returning the value when the value is less than n and restarting otherwise

public static int random(int n) {
        int r = 0;
        for (int i =1; i<n;i<<=1) {
        if(r<n)return r;

also nanoTime() is only as accurate as the system can provide, which means that t%2 might be biased 1 or 0. Calling it in such a tight loop gives a very high likelihood of the returned values being the same on a machine with a low accuracy

a much better solution would be implementing a proper RNG like a Linear congruential generator and using that for the generation of the random bits

  • I see. So then how would you have done it?
    – paul smith
    Commented May 26, 2012 at 2:31
  • @paulsmith I don't understand why they asked this from you tbh... at best you could have memorised any of the many algorithms out there as they are incredibly simple when someone has already chosen the right constants. And what would have that proven anyway?
    – Esailija
    Commented May 27, 2012 at 14:46
  • @Esailija maybe implementing prngs is part of the job? maybe the job has a lot of probabilistic stuff involved and they were less interested in the implementation but more in what the candidate knew about probability distributions ? maybe the interviewer is an idiot - we may never know ;)
    – jk.
    Commented May 28, 2012 at 8:30

As others have said, the problem is that you're summing your bits. When choosing a number between 0 and 4 your algorithm would pick a two most of the time because there are many more ways to get a two by summation of the bits:

0: 0+0+0+0
1: 1+0+0+0, 0+1+0+0, 0+0+1+0, 0+0+0+1
2: 1+1+0+0, 1+0+1+0, 1+0+0+1, 0+1+1+0, 0+1+0+1, 0+0+1+1  
2: 0+1+1+1, 1+0+1+1, 1+1+0+1, 1+1+1+0
4: 1+1+1+1

Using bit shifts would have given you a lot better distribution, but you'd still be getting bad values from a timer in a tight loop.

I don't know for sure but I'd imagine there are well-tested normally distributed hash functions in Java's standard libraries. Starting with a seed of, say the timer, you could do something like this:

randomBits = hashFunction(seed)
seed = randomBits
return seed % n

I'm no mathematician and I'm a bit worried that the modulo at the end might skew the distribution, but it would be a lot more random than summing bits and could be written quickly in an interview.


A simple class of random number generators are the linear congruential generators, which generate numbers through state = (state * a + b) % c.

Java's Random class works exactly like that, using the system time as initial state. The state in java.util.Random has a size of 48 bits, while it only ever returns at most 32 bits of that, so it looks "quite random". LGCs aren't great random number generators, but they do their job if only few values are needed.


He probably expected you to use Java's Random class.

Your current implementation takes a sum of "coin toss" results to determine a random number. While your results will be somewhat random, they won't be evenly distributed. If you roll two dice, you'll end up with a total of 7 roughly half the time. This approach to random number generation is subject to the same math.

The people who implement Java's libraries have gone out of their way to solve a lot of the issues around random number generation, and it's usually best to use them when they offer a solution to your problem. No need to reinvent the wheel.

If you want to know how to produce a good Random number generator, you can always read up on how Java implements theirs!

  • I wish! He strictly told me any use of random library methods are forbidden
    – paul smith
    Commented May 26, 2012 at 2:24
  • 1
    @paulsmith: These are good details to provide in the question when you ask it to ensure that people give you good answers. For what it's worth, I doubt that 99% of Java developers could produce a decent pseudo-random generation algorithm. The best I could do would probably be to take the system time and mod it with n. Commented May 26, 2012 at 2:31
  • 10
    @paulsmith apparently, he expected you to know a PRNG algorithm. If it's relevant to the job, it might be fit, although it still seems a bit far fetched as an interview question to me.
    – kaoD
    Commented May 26, 2012 at 2:33

To ratchet freak's answer I would add that the interviewer probably considered your use of System.nanoTime() as cheating since, in a way, it's an external random number generator, though not a very good one by itself.

He probably wanted you to implement a clearly deterministic generator from scratch, as the one from Wikipedia pointed out by ratchet freak.


You could use your current implementation to provide good (not great) random 0 or 1 by adding a timer for some entropy. We ran a small contest and this solution was among the best - you were very very close:

public static void random(int iterations) throws InterruptedException{
    for(int i = 1 ; i <= iterations ; i++){
        System.out.print(System.nanoTime() % 2);
        Thread.sleep(0, 200);
        if(i % 1000 == 0){

Here's the correct answer: Creating a good random number generator is difficult. If it's not something you have specifically learned, then it is impossible to come up with anything remotely useful. If you have learned about it, then it's still not something that you would likely be able to do from memory.

You might know about a linear congruential random number generator, but there are some constants involved that need some very very tricky analysis to get right. Something you'd look up on the internet. You might have heard of Marsaglia's KISS algorithm, or the Mersenne twister. Each one you wouldn't even try to implement without looking up the details on the internet.

There are very few programming jobs where I would hold it against you if you cannot write a good random number generator. That said, what you should say is: "I have never done this, I don't know if the result would be any good". Then write an algorithm - coming up with anything is positive. And then the important thing: Write some code that tests the random number generator. For example, use n = 20 and check that the result is never less than 0 or greater than 20, and print out how often each number from 0 to 20 comes up in 2100 calls (you'd hope that each comes up about 100 times).

In practice, outside an interview, you'd need someone who knows better how to write a random number generator than the guys responsible for the code in the Java library. That person would be quite rare.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.