## Linkedin Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

Fisher Yates Shuffle :

``````for ( i=0; i < A.length -1 ; i++ )
{
j = randInt(A, i, A.length -1);
swap(A, i, j)
}``````

The -1 on the A.length is not needed, but notice the final iteration if you exclude the -1 does nothing extra vs. the version above (swaps the final element with itself deterministically).

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

for ( i=0; i < A.length -1 ; i++ )
{
j = randInt(A, i, A.length -1);
swap(A, i, j)
}

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

``````for(int i=0;i<arr.length;i++){
x = (int) ((Math.random()*(arr.length-i)) + i);
temp = arr[x];
arr[x]=arr[i];
arr[i]=temp;
}``````

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

``````for(int i=0;i<arr.length;i++){
x = (int) ((Math.random()*(arr.length-i)) + i);
temp = arr[x];
arr[x]=arr[i];
arr[i]=temp;
}``````

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

Could someone please explain whats going on here?

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

The basic idea of the fisher yates is this:

``````|1 2 3 4 5
Do a swap of 1 and random(1,2,3,4 5) = 3
3|2 1 4 5
Do a swap of 2 ad random(1, 2, 4, 5) = 4
3 4 | 1 2 5``````

Notice how after something it swapped, it is no longer available for swap.
Therefore on the first pass there was a 1/n chance of any one element being picked to swap. And on the second we never look at that element again so there is a 1/(n-1) chance of picking any single element on the second pass.
so on the n'th pass there is a 1/1 chance of picking that element.
Therefore each permutation has the probabily of 1/(n!) which is perfectly "random".

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

607202

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

Here is C++ solution.

I assume the rand() function guarantee the uniform distribution of the random numbers.

``````#include<time.h>
#include<iostream>
#include<chrono>
#include<random>

using namespace std;

void swap(int *A, int s, int d)
{
int tmp= A[s];
A[s] = A[d];
A[d] = tmp;
}

void shuffle(int* A, int len)
{
for (int i = len-1; i >0; i--)
{
int next = rand()% (i+1);
swap(A, next, i);
}
}

int main()
{
int A[10] = {1,2,3,4,5,6,7,8,9,10};
srand(time(NULL));

for (int j = 0; j < 20; j++)
{
shuffle(A, 10);
for (int i = 0; i < 10; i++)
cout<<A[i] << ", ";
cout<<endl;
}
return 1;
}``````

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.

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

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