## Microsoft Interview Question

Software Engineer / Developers**Team:**Windows Phone

**Country:**United States

**Interview Type:**Phone Interview

Assume you have N bytes of storage and a function that can randomly pick an integer element from a range from 1 to x. Populate an array A with 1 to N. Use your random integer function to choose an index between 1 and N. Use A[<random int chosen>] as your next value. Replace A[<random int chosen>] with A[N] and decrement N. Repeat until N == 1, and then just return A[1] and you're done.

By virtue of setting A[n] to be A[<last chosen index>] after each iterations, there will be no collision/repeat detection, so you can pick each element in constant time.

{public int[] getRandomArray2(int N)

{

int[] returnArray = new int[N];

Random rm = new Random();

int iRandomPosition = 0;

int iTemp = 0;

//we don't initialize the array

for (int i = 1; i <= N; i++)

{

iRandomPosition = rm.Next(0, i);

iTemp = returnArray[iRandomPosition];

returnArray[iRandomPosition] = i;

returnArray[i - 1] = iTemp;

}

for (int j = 0; j < N; j++)

Console.WriteLine(returnArray[j]);

return returnArray;

}

}

```
public static int [] randomize(int n){
int [] array = new int[n];
for(int i=0; i<n; i++){
array[i]=i;
}
Random randomGenerator=new Random();
for(int i=0; i<n; i++){
int rand=randomGenerator.nextInt(n-1);
if(rand==i)
rand=(rand+rand) % (n-1);
int temp=array[i];
array[i]=array[rand];
array[rand]=temp;
}
return array;
}
```

package array;

/*

*

* The period of a general LCG is at most m, and for some choices of factor a much less than that. Provided that the offset c is nonzero, the LCG will have a full period for all seed values if and only if:[2]

\,c and \,m are relatively prime,

\,a - 1 is divisible by all prime factors of \,m,

\,a - 1 is a multiple of 4 if \,m is a multiple of 4.

*

*/

public class Arithmetic implements Generator{

private int intialvalue;

private int seed1;

private int seed2;

public Arithmetic(int intialvalue, int seed1, int seed2) {

super();

this.intialvalue = intialvalue;

this.seed1 = seed1;

this.seed2 = seed2;

}

@Override

public int[] GenerateRandom(int n) {

int[] output = new int[n];

int x = intialvalue;

for (int i = 0; i < n; i++) {

x = (seed1 * x + seed2) % n;

output[i] = x;

}

return output;

}

@Override

public void setInitialValue(int n) {

intialvalue = n;

}

}

```
int real_user_input = 5;
int user_input = real_user_input+1;
Random r = new Random();
int nextRan = 0;
StringBuilder sb = new StringBuilder();
int count = 0;
List<int> usedList = new List<int>();
nextRan = r.Next(user_input);
while (usedList.Count < real_user_input )
{
if (nextRan == 0)
{
nextRan = r.Next(user_input);
continue;
}
if (count == 0)
{
usedList.Add(nextRan);
Console.WriteLine("Added " + nextRan);
}
else
{
if (!usedList.Contains(nextRan))
{
usedList.Add(nextRan);
Console.WriteLine("Adding " + nextRan);
}
else
Console.WriteLine("NOT adding " + nextRan);
}
count++;
nextRan = r.Next(user_input);
if ((count % 6) == 0)
{
Console.WriteLine();
Console.ReadKey();
Console.WriteLine();
}
}
Console.WriteLine("Here's the list of 1 to " + real_user_input);
foreach (var i in usedList)
Console.Write(i + ",");
Console.ReadKey();
```

knuth (Fisher-Yates) algorithm:

initialize array of size n with integers from 0 to n-1

- iman.goodarzi March 07, 2013