How to Create a Random Generator

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!

Sign is on a good track, but his algorithm is wrong. It is not much random. It is actually pretty hard to create random like this. I was playing around with this and everything I tried created obvious patterns when printed in 2D. In the end I manged to create an algorithm that doesn't create any eye-visible patterns. I looked for inspiration in existing random algorithms.

public static uint bitRotate(uint x)
{
    const int bits = 16;
    return (x << bits) | (x >> (32 - bits));
}

public static uint getXYNoise(int x, int y)
{
    UInt32 num = seed;
    for (uint i = 0; i < 16; i++)
    {
        num = num * 541 + (uint)x;
        num = bitRotate(num);
        num = num * 809 + (uint)y;
        num = bitRotate(num);
        num = num * 673 + (uint)i;
        num = bitRotate(num);
    }
    return num % 4;
}

When this algorithm is used to render a 4-shades of gray image, it creates this:

For comparison, the Random algorithm creates this pattern:

And Sign's algorithm too has patterns: