algorithm for generating a random numeric string,

Question

Can be in any language or even pseudocode. I was asked this in an interview question, and was curious what you guys can come up with.

Answer 1

I always like saying Computer Random Numbers are always only pseudo-random. Anyway, your favourite language will invariably have a random library. Next what is a numeric string ? 0-9 valued for each character ? Well let's start with that assumption. So we can generate bytes between to Ascii codes of 0-9 with offset (48) and (int) random*10 (since random generators typically return floats). Then place these all in a char buffer 10000 long and convert to string.

Answer 2

Return a string containing 10,000 1s -- that's just as random as any other digit string of the same length.

Answer 3

I think this is a trick question - the obvious answer of generating digits using a standard library routine is almost certainly flawed, if you want to generate every possible 10000 digit number with equal probability...

If an algorithmic random number generator maintains n bits of state, then clearly it can generate at most 2ⁿ possible different output sequences, because there are only 2ⁿ different initial configurations.

2³³²¹⁹ < 10¹⁰⁰⁰⁰ < 2³³²²⁰, so if your algorithm uses less than 33220 bits of internal state, it cannot possibly generate some of the 10¹⁰⁰⁰⁰ possible 10000-digit (decimal) numbers.

Typical standard library random number generators won't use anything like this much internal state. Even the Mersenne Twister (the most frequently mentioned generator with a large state that I'm aware of) only keeps 624 32-bit words (= 19968 bits) of state.

Answer 4

I think the real question was to determine what the interviewer actually wanted. For example, random in what sense? Uncompressable? Random over multiple runs of the same algorithm? Etc.

Answer 5

You can start with a list of seed digits:

seeds = [4,9,3,1,2,5,5,4,4,8,4,3] # This should be relatively large

Then, use a counter to keep track of which digit was last used. This would be system-wide and shouldn't reset with the system:

def next_digit():
    counter = 0
    while True:
        yield counter
        counter += 1
pos_it = next_digit()
rand_it = next_digit()

Next, use an algorithm that uses modulus to determine the "next number":

def random_digit():
    position = pos_it.next() % len(seeds)
    digit = seeds[position] * rand_it.next()
    return digit % 10

Last, generate 10,000 of those digits.

output = ""
for i in range(10000):
    output = "%s%s" % (output, random_digit())

I believe that an ideal answer would use more prime numbers, but this should be pretty sufficient.

Answer 6

Without additional requirements, this will work:

StringBuilder randomStr = new StringBuilder(10000);
Random rnd = new Random();
for(int i = 0; i<10000;i++)
{
  char randomChar = rnd.AsChar();
  randomStr[i] = randomChar;
}

This will result in unprintable characters and other unpleasentness. Using an ASCII encoder you can get letters, numbers and punctutaiton by sticking to the range 32 - 126. Or creating a random number between 0 and 94 and adding 32. Not sure which aspect they were looking for in the question.

BTW, No I did not know the visible range off the top of my head, I looked it up on wikipedia.