Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
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)
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;
}
#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] << " ";
}
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);
}
}
}
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);
}
}
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).
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.
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).
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)
I think the best way to go about this would be via shuffling. The knuth shuffle problem is a much better approach for this
@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
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?
#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;
}
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);
}
}
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).
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.
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);
}
}
public static void shuffleArray(int[] a) {
- Anonymous February 01, 2013int 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;
}