Byte Array Manipulation - Interview Question

I was having this discussion with my friend who had this question asked to him in the Interview. The Question goes like this. Write a Function which takes in a byte array(2 dimensional) as input along with an Integer n, The initial assumption is all the elements of M*N byte array is zero and the problem is to fill 'n' Byte array elements with value 1, For instance if M=5 and N=5 and the n value is 10 the Byte array should've 10/25 elements to be 1 and rest of the 15 values to be 0. The values filled should be random and one cell in byte array should be filled only once. I was fascinated to try solving this on my own. I've attached the code I've come up with so far.

public Boolean ByteArrayFiller(int a,int b, int n)
    {
        int count = n;
        int iLocalCount = 0;
        byte[,] bArray= new byte[a,b];
        for (int i = 0; i <a; i++)
            for (int j = 1; j <b; j++)
                bArray[i, j] = 0;

        Random randa=  new Random();
        int iRandA = randa.Next(a);
        int iRandB = randa.Next(b);

        while (iLocalCount < n)
        {
            if (bArray[iRandA, iRandB] == 0)
            {
                bArray[iRandA, iRandB] = 1;
                iLocalCount++;
            }

            iRandA = randa.Next(a);
            iRandB = randa.Next(b);
            continue;
        }
        //do
        //{
        //     //iRandA = randa.Next(a);
        //     //iRandB = randa.Next(b);
        //    bArray[iRandA,iRandB]=1;
        //    iLocalCount++;开发者_如何学C

        //} while (iLocalCount<=count && bArray[iRandA,iRandB]==0);

        return true;
    }

The code i wrote is in C# but it's straight forward to understand. It's able to do the purpose of the question( I did some trials runs and results came out correctly) perfectly but I have used Random object in C#(Equivalent to Math.Rand in Java) to fill up the byte array and I keep thinking if Rand returns the same values for a and b. There is a good chance for this to go indefinitely. Is that the purpose of the question? or Does the solution that i came up for this question is good enough!

I am curious to see how experts here solve this problem? I am just looking for new ideas to expand my horizon. Any pointers would be greatly appreciated. Thanks for taking the time to read this post!

A while loop trying random locations until it finds a good one is generally a very bad approach. If n = M*N, then the last one will have a probability of 1/(M*N) of finding a match. If M*N are sufficiently large, this can be extremely inefficient.

If M*N is not too large, I would create a temporary array of M*N size, fill it with the numbers 0 through (M*N)-1, and then permutate it - i.e. you walk through it and swap the current value with that of a random other value.

Then you go to the first n elements in your array and set the appropriate cell. (row = value / columns, col = value % columns).

I would treat the array, logically, as a one-dimensional array. Fill the first n positions with the prescribed value, and then shuffle the array.

Given a byte array, and the number of rows and columns in the array, and assuming that the array is already filled with 0:

int NumElements = NumRows * NumCols;

for (int i = 0; i < NumElementsToFill; ++i)
{
    int row = i / NumRows;
    int col = i % NumCols;
    array[row, col] = 1;
}

// Now shuffle the array
Random rnd = new Random();

for (int i = 0; i < NumElements; ++i)
{
    int irow = i / NumRows;
    int icol = i % NumCols;

    int swapWith = rnd.Next(i+1);
    int swapRow = swapWith / NumRows;
    int swapCol = swapWith % NumCols;

    byte temp = array[irow, icol];
    array[irow, icol] = array[swapRow, swapCol];
    array[swapRow, swapCol] = temp;
}

The key here is converting the one-dimensional index into row/col values. I used / and %. You could also use Math.DivRem. Or create Action methods that do the get and set for you.

Choose a number, which is larger than both N and M and is prime (or co-prime to both N and M). Let's call this number p.

Loop until you've set x numbers:

1. Generate a random number less than N*M. Call this number `l`.
2. Then the next place to put the number will be `p*l%(N*M)`, if that position hasn't been set.

A downside to this approach is that if the array is filling up, you'll have more collisions.

Bascially, you need to choose n unique random numbers from range [0, p) (where p = M * N), and map them to positions of 2-dimensional array.

Naive approaches are 1) generate non-unique numbers with retry 2) fill an array with numbers from 0 to p-1, shuffle it and take first n numbers (takes O(p) time, O(p) memory).

Another approach is to choose them with the following algorithm (O(n²) time, O(n) memory, code in Java):

public Set<Integer> chooseUniqueRandomNumbers(int n, int p) {
    Set<Integer> choosen = new TreeSet<Integer>();
    Random rnd = new Random();

    for (int i = 0; i < n; i++) {
        // Generate random number from range [0, p - i)
        int c = rnd.nextInt(p - i);

        // Adjust it as it was choosen from range [0, p) excluding already choosen numbers
        Iterator<Integer> it = choosen.iterator();
        while (it.hasNext() && it.next() <= c) c++;

        choosen.add(c);
    }

    return choosen;
}

Mapping of generated numbers to positions of 2-dimensional array is trivial.