## Interview Question

• 0

Country: United States
Interview Type: Phone Interview

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

The following pseudo code solve it in O(n) time:

index = 1
While (index <= N){
swap(a[index],a[a[index]]);
while(a[index] == index)
index++;
}

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

One more problem is that if it's an array then the rotation itself will require shift hence will be more costly. I think 'havefun''s solution is better. requires O(n) op.

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

static void sort(int [] a)
{
int i = 0;
while(i<a.length)
{
if(a[i]>i+1)
{
int k = a[i]-1;
int temp = a[k];
a[k] = a[i];
a[i] = temp;
}
else
i++;
}

for(int j=0;j<a.length;j++)
System.out.print(a[j]+" ");
}

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

Just think for it using disjoint cycles of the given permutation
For example if N = 5, and given a permutation (3, 4, 1, 5, 2) and want to sort it

Then you have 2 disjoint cycles in this permutation
1st: 3 --> 1 --> 3
2nd: 4 --> 5 --> 2 --> 4
(generate these cycles using the index of every number, 3 will point to the 3rd place in the permutation which is 1 and 1 will show to the 1st place which is 3)

Then given these disjoint cycles, just rotate them till they are all adjusted.

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

instead of this input what if the input is 4,3,1,5,2
then the disjoint cycle would be..
4--5--2--3--1--4
how will the rotation work in this case

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

Try bubble sort or comb sort.

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

//given an array of size n, it holds distinct integers from 1 to n. Give an algorithm to sort the array? one way is to just assign a[i]=i in the array. how to sort the array using the elements of the array and not just assigning directly

``````public class Sort {
public static void main(String[] args) {
int[] arr = { 2, 4, 1, 3 };
int i = 0;
int j = 0;
while (j < arr.length-1) {
i=j;
int x=i+1;
while (arr[i] != i+1) {
swap(arr, i, x);
x++;
}
j++;
}

for(int a: arr)
{
System.out.print(a + ", ");
}
}

private static void swap(int[] arr, int x, int y) {
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;

}
}``````

The time complexity is O(n^2), no additional space is required - O(n) - the size of the array itself

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

Use CountSort relatively small n

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

Why not directly assign? Do they contain additional data? So it is like an array of structs or something?

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

int i = 1
while i < length of the array
do
if arr[i] is not equal to i
then
swap arr[arr[i]] and arr[i]
else
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.