Microsoft Interview Question
Software Engineer / DevelopersTeam: 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