Microsoft Interview Question for Software Engineer in Tests


Country: United States
Interview Type: Phone Interview




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

public static void shuffleArray(int[] a) {
int n = a.length;
Random random = new Random();
//random.nextInt();
for (int i = 0; i < n; i++) {
int change = i + random.nextInt(n - i);
swap(a, i, change);
}
}

private static void swap(int[] a, int i, int change) {
int helper = a[i];
a[i] = a[change];
a[change] = helper;
}

- Anonymous February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes... this is standard Knuth shuffle algo

for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

And here is the c++ code for the same

void knuthShuffle(int n){
    int *ar = new int[n];
    int i(0),temp(0);
    for (;i<n;i++) ar[i]=i+1; //initialize array
    while(i>0){
        int r = Random(i-1);//which is similar to ->rand()%i; 
        temp = ar[i-1];
        ar[i-1] = ar[r];
        ar[r] = temp;
        i-=1;
    }
    for(i=0;i<n;i++) cout<<ar[i] <<" ";cout<<endl;
    delete ar;
}

Time complexity: O(n)
Space complexity: O(n)

- vik February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Here I implemented Knuth Shuffle Algorithm in C++ for this problem.

#include<iostream>
using namespace std;
void Random_List(int n)
{ int a[10000];
	for(int i=1;i<=n;i++)
	{
		a[i] = i;
	}
	cout<<"randlist("<<n<<") :";
	for(int i=n;i>=1;i--)
	{
		int j = rand() % i + 1;
        int swap = a[j];
		a[j] = a[i];
		a[i] = swap;
	}
	for(int i=1;i<=n;i++)
	{
		cout<<" "<<a[i];
	}
}

int main()
{ int n = 0;
	cout<<"n=";cin>>n;
	Random_List(n);	
	cout<<endl;
	return 0;
}

- DoodleKana February 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<cstdlib>
#include<time.h>

Time -- O(n) Space O(n)

Probability of rand genarating index i == 1/n.
for the function to take O(n2) time -- probability = (1/n)**n;

So for smaller n it will take about n2 but for large n it is O(n)..

You could remove the inner do while loop. But then it won't be truly random.

void c15366664RandSequenc() {
    srand(time(NULL));
    int a[10], n = 10;
    for (int i = 0; i < n; i++)
        a[i] = i;
    int sI = 0, swapper;
    for (int i = 0; i < n; i++) {
        do {
            sI = rand() % n;
        } while (sI == i);
        swapper = a[sI];
        a[sI] = a[i];
        a[i] = swapper;
    }
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
}

- isandesh7 February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think we're supposed to use the Random() method, not srand() and rand().

- Anonymous February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

package Tricky;

import java.util.Random;

public class RandomShuffle {

	int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		RandomShuffle shuffle = new RandomShuffle();
		shuffle.shuffleArray();
		
	}

	private void shuffleArray() {
		Random random = new Random();
		
		for(int i =0;i<arr.length;i++){
			int randomInt = random.nextInt(arr.length);
			int temp = arr[randomInt];
			arr[randomInt]=arr[i];
			arr[i] = temp;
		}
		
		for(int i : arr){
			System.out.print( "  " + i);
		}
		
	}

}

- Anonymous February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

void randlist(int x)
{
	
	ArrayList<int> buffer = new ArrayList<int>();
	int random_integer;
		for(int i=0; i<x; i++)
		{
			random_integer = ((rand)%x)+1
			if(buffer.contains(random_integer)
			{
				continue;
			}
			
			buffer.add(random_integer)
				
		}
		for(int i=0; i<buffer.lenght;i++)
		{
			System.out.println(buffer.Element);
		}
}

- fly123 February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Since you are using ArrayList to store the numbers the worst case complexity for arraylist is O(n), hence your solution will go to O(n2) not O(n).

- Sidhu February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree, I would use Hash Map instead so you can check if the key exists in O(1) (Ideally)...

- Anonymous February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is Java based

Create a HashSet<int>

in a for loop generate the numbers Random(n) function, and check if it exists in HashSet or not, if it doesn't then print it else try again.

HashSet will give you read operations in O(1) time, hence the running time is O(n).

If you want you can use HashMapas well, with the key as the number generated and use value as null (or 1 for morbidly curious minds :) ) since we are only checking if the key exists or not.

- Sidhu February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The expected running time of this approach is actually O(n log n). When you are deciding on the first element, every time you try to choose it, the probability you'll pick one not in the hash map is n/n = 1. For the second element, it's (n-1)/, so the expected number of attempts needed is n/(n-1). By the k-th element the odds are (n-(k-1))/n, and the expected number of attempts needed is thus n/(n-(k-1)). When picking the last element, it'll take you n attempts in the expectation, since only 1 of n choices is available.

The overall complexity will be n/n + n /(n-1) + n/(n-2) + ... n/1 = n [ 1 + 1/2 + 1/3 + ... + 1/n ] = O(n log n).

- Anonymous February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you are way over complicating the problem itself. The probability and the running time complexity are 2 orthogonal concepts. I am doing just a single iteration so it will be O (n) time for the iteration and since hash map return s get in a constant time so it will O (n) +cn where c is constant time for 1 get operation so the total time is O (n) + cn = O (n)

- Anonymous February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the best way to go about this would be via shuffling. The knuth shuffle problem is a much better approach for this

- fly123 February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Sidhu: Not quite. Remember, you said, "if it doesn't then print it else try again." The "else try again" part is quite critical. You must consider how many times you'll need to try again for each element. Every element you print may be the result of several attempts. The analysis above shows that the average number of attempts per element printed in your scheme is O(log n), for a total O(nlogn) hash lookups, and O(nlogn) total expected complexity.

@fly123: please elaborate

- eugene.yarovoi February 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, expected runtime is Theta(n log n).

@The anonymous talking about orthogonal concepts. Huh?

@eugene: I presume you interpreted the Random number generator to generate numbers in range 1,n , where n is the number of numbers to be printed?

- Anonymous February 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous: yes, that's what the problem sounded like to me.

"Random(n) is given as a tool you can use to generate a
single random number between 1-n".

I assumed that Random(n) is O(1) in saying that the overall complexity of the solution discussed here is O(n log n).

- eugene.yarovoi February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <cmath>
#include <cassert>
#include <cstdlib>
#include <ctime>

using namespace std;
static int rand_int(int n) {
int limit = RAND_MAX - RAND_MAX % n;
int rnd;

do {
rnd = rand();
} while (rnd >= limit);
return rnd % n;
}
void shuffle(int *array, int n) {
int i, j, tmp;

for (i = n - 1; i > 0; i--) {
j = rand_int(i + 1);
tmp = array[j];
array[j] = array[i];
array[i] = tmp;
}
}
int main(int argc, char *argv[]) {
long *nullptr=NULL;
srand(time(nullptr));
int arr[]={1,2,3,4,5,6,7,8};
int length=sizeof(arr)/sizeof(arr[0]);
shuffle(arr,length);
for(int k=0;k <length;k++)
{
cout<<arr[k]<<endl;
}
return 0;
}

- Anonymous February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bgfjnsmrdrbbzrzxnqumoanmijmzun

- udygrr February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

They are not supposed to repeat you lessoff.

- Anonymous February 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

this is the easiest question I have ever seen

void printRandom(int n){

vector<int> numbers;
for(int i=1;i<=n;i++)
numbers.push_back(i);

for(int i=n;i>0;i--)
{
int rand = rand()%i;
printf("%d ", numbers[rand]);
numbers.erase(numbers.begin()+rand);
}

}

- Devon February 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Might be easy, but you have managed to mess up the runtime. Your algorithm is quadratic, while a linear time algorithm is possible.

Search the web for Knuth shuffle (or Fischer-Yates shuffle).

- Anonymous February 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not quadratic lol
this is also O(N)
And this is faster than Knuth shuffle. trust me
Do not think about advantages of vector here.

- 9tontruck February 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@9tontruck (aka Devon). LOL back at ya.

numbers.erase(blah). What is the complexity of that?

Don't tell you you have a magical array which can delete elements from the middle in O(1) time.

- Anonymous February 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printNRandomNumbers(int n) {
int a[] = new int[n];
for(int i = 0; i < n; i++) {
a[i] = i + 1;
}
for(int i = 0; i < n; i++) {
int no = (int) (Math.random() * (n - i)) + i;
int tmp = a[i];
a[i] = a[no];
a[no] = tmp;
}
for(int i : a) {
System.out.print(i + " ");
}
}

- Anonymous February 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class RandList {
	private static int Random(int n) {
		return (int) (Math.random() * n + 1);
	}

	public static void printRandList(int n) {
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = i;
			;
		}
		// shuffle array
		for (int i = 0; i < n; i++) {
			int index = (Random(n) + i) % n;
			int tmp = array[i];
			array[i] = array[index];
			array[index] = tmp;
		}
		for (int i : array) {
			System.out.print(i + "\t");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		printRandList(5);
	}

}

- Kevin February 27, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More