Microsoft Interview Question for Software Engineer in Tests

• 1
of 1 vote

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

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

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)

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

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, 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] << " ";
}

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

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

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

}

}

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

}
for(int i=0; i<buffer.lenght;i++)
{
System.out.println(buffer.Element);
}
}

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

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).

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

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

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.

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).

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

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)

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

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

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

@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.

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

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?

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

@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).

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);
shuffle(arr,length);
for(int k=0;k <length;k++)
{
cout<<arr[k]<<endl;
}
return 0;
}

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

bgfjnsmrdrbbzrzxnqumoanmijmzun

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

They are not supposed to repeat you lessoff.

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

}

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

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).

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

this is also O(N)
And this is faster than Knuth shuffle. trust me

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

@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.

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 + " ");
}
}

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

}

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.