## Microsoft Interview Question for Software Engineer / Developers

Team: Windows Phone
Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
5
of 5 vote

knuth (Fisher-Yates) algorithm:
initialize array of size n with integers from 0 to n-1

``````for (int i = n - 1 ; i >= 0 ; --i)
{
int j = getRandomNum(0, i);//random between 0 and i
swap(array[i], array[j]);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Generate array contains 1 to N, then sort by random value Time/Space O(N)

Comment hidden because of low score. Click to expand.
0
of 2 vote

Create an array of size N, (index being 0), and initialize all elements with 0. Generate a random number less than N and if arr[index]=0 put it in arr[index]. If it is already occupied, generate another no. Continue doing this till the array is completely filled.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Create an array int p[N], and set its value p[i]=i+1 for i=0 to N-1. write a for loop as bellow:

``````for(count=N;count> 1;count--)
{
int ranCnt=random()%count;
swap(p[count-1], p[ranCnt]);
}``````

p is the final result you want.

Comment hidden because of low score. Click to expand.
0
of 0 vote

void genRandom( int N ){
int flag[N] = {0}; int count = 0;int x;
while( count < N ){
do{
x = rand() % N;
}while(flag[x]);
flag[x] = 1;
count++;
printf("%d",x+1);// Required range is 1 to N
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

To initialize an array a of n elements to a randomly shuffled copy of source, both 0-based:
a[0] ← source[0]
for i from 1 to n − 1 do
j ← random integer with 0 ≤ j ≤ i
a[i] ← a[j]
a[j] ← source[i]

search for Fisher-Yates_shuffle on wikipedia

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

{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;

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)
{
Console.WriteLine("Added " + nextRan);
}
else
{
if (!usedList.Contains(nextRan))
{
Console.WriteLine("Adding " + nextRan);
}
else
Console.WriteLine("NOT adding " + nextRan);

}

count++;
nextRan = r.Next(user_input);
if ((count % 6) == 0)
{
Console.WriteLine();
Console.WriteLine();
}
}

Console.WriteLine("Here's the list of 1 to " + real_user_input);
foreach (var i in usedList)
Console.Write(i + ",");

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.