## Amazon Interview Question for Software Engineer / Developers

• 5

Country: India
Interview Type: Phone Interview

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

I think this is a trick question for 2 reasons:
1) Whether the array is sub-sorted or not, an in-place quick sort can be done in O(nlogn)
2) So if we are really looking for a O(n) solution, then why wouldn't that solution be used in the "merge" step of a standard merge-sort, making the merge-sort an in-place algorithm (which it is obviously not) ?
Therefore, I don't think it can be done in less than O(nlogn)

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

Actually it is possible to merge in-place in O(n) time, but it's too complex to be asked in an interview. People are still researching on the topic and many research papers are available if you want.
Practically traditional merge algorithm (which uses auxiliary space) is better than in-place merge.
If asked in an interview you should mention the O(n^2) merging like insertion sort or the Quicksort. But that would defeat the goal of giving two sorted arrays as input.

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

``````public class sortInPlace {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {1,3,5,6,2,4,7};
sortArray(arr);
}

public static void sortArray(int []a)
{
int endOfFirstArray = 0,prevNum = -1;
if(a.length < 2)
{
return ;
}

if(a.length == 2)
{
if ( a[0] > a[1]) {
int temp = a[1];
a[1] = a[0];
a[0] = temp;
}
}
prevNum = 0;
for (int i = 1; i < a.length ; i++ )
{
if ( a[prevNum] > a[i])
{
break;
}
prevNum++;
}

int ptr2 = a.length -1 ,ptr1 = prevNum;
for (; ptr2 > ptr1 ; )
{
if (a[ptr2] > a[ptr1])
{
ptr2--;
}
else
{
int temp = a[ptr2];
a[ptr2] = a[ptr1];
a[ptr1] = temp;
int tempPtr2 = ptr2;
for (int j = tempPtr2 -1 ; j >=0 ; j--)
{
if (a[tempPtr2] < a[j] )
{
temp = a[tempPtr2];
a[tempPtr2] = a[j];
a[j] = temp;
}
tempPtr2--;
}
}
}

for (int i = 0 ; i < a.length ; i++)
{
System.out.println (a[i]);
}
}

}``````

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

it is possible in O(n) and the idea is like Insertion Sort
in case of array of increasing integers:
find the first element in array that is smaller than its previous element. (start of the second sorted sub-array)
swap this element with its previous one until it becomes bigger than its prev.
continue on the next index on the second sub-array until the end.

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

You solution will be O(n^2)

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

Merging two sorted lists can be done in O(N) time. The challenge here is doing it in place, which can be done in close to O(N) time. Basically, you just need to buffer elements from the first list that aren't ready to be inserted into the final list. Your intermediate lists will look like this:

FFF1111BBB222

F = element in final position
1 = element in 1st list
B = element in buffered head portion of first list
2 = element in 1st list

Keep track of the offsets of the first 1, the first B, and the first 2. When you do the normal merge step, if there are any Bs, grab them before you grab the 1s. You can think of this like a circular array for 1s, or it might make more sense to just think of it as a scratch area to save off 1s for later processing. Either interpretation leads to the same result.

One minor slowdown is that you can get a long run of 1s that are less than 2s, which builds up your buffer of Bs. Once you get to a B that is less than a 2, you'll need to shift over all the other Bs one to the left to buffer the 1 that is displaced by the new F.

When there are no Bs and the lead 1 sorts ahead of the 2, then you simply turn the 1 into an F.

When there are no Bs and the lead 2 sorts ahead of the 1, then you put the 2 in 1's old place, turning it into an F, then put the 1 in the 2's old place, turning it into a B.

When there ARE Bs and the lead 2 sorts ahead of the lead B, then you replace the lead 1 with the lead 2 (turned into an F) and put the lead 1 in the 2's old place (turned into a B).

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

Actually, I think I'd just bubble the lead 1 down into the 2s after any instance where the 2 sorts ahead of the 1. The worst case runtime is N squared, but if the lists are roughly interlaced, it's pretty fast.

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

What about the case wherein the buffer BBB gets overridden,for example the first B in BBB might contain a number from List 1 which is now being compare against 2. if(2 < 1), then say we need to insert 2 at the first B position.where will the value of 1 at the 1st B position go, we will have to push all elements one position to the right, increasing the complexity.

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

May i know what is inplace algorithm.............?

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

you don't use any extra space for inplace algo.

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

You use O(1) space. 'Not any extra space' is misleading.

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

I cant understand..........

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

Then You have to first read the basics ao algo and then think about the question and post any comment here .

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

import java.util.Arrays;

public class SortSortedArrays {

public static void main(String[] args) {
int[] arr = {1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11 };

int left = 0;
int right = 0;
int prev = Integer.MIN_VALUE;
System.out.println(Arrays.toString(arr));

//first find the start of the next array.
for(int i = 0; i < arr.length; i++)
{
if( arr[i] < prev )
{
right = i;
break;
}
prev = arr[i];
}

//sort the array
while(left < right && right < arr.length)
{
if( arr[left] >= arr[right] )
{
//shift digits to bring the digit from right
shiftDigits(arr,left,right);
right++;
}
else
{
left++;
}
}
System.out.println(Arrays.toString(arr));
}

public static void shiftDigits(int[] arr, int left, int right)
{
int digit = arr[right];

while(right > left)
{
arr[right] = arr[--right];
}
arr[left] = digit;
}

}

Order is close to N when the original array is completely sorted. Worst case is N^2. This sorts in place no extra space necessary.

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

Reposting with formatting

``````import java.util.Arrays;

//Order is close to N when the original array is completely sorted.
//Worst case is N^2. This sorts in place no extra space necessary.

public class SortSortedArrays {

public static void main(String[] args) {
int[] arr = {1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11 };

int left = 0;
int right = 0;
int prev = Integer.MIN_VALUE;
System.out.println(Arrays.toString(arr));

//first find the start of the next array.
for(int i = 0; i < arr.length; i++)
{
if( arr[i] < prev )
{
right = i;
break;
}
prev = arr[i];
}

//sort the array
while(left < right && right < arr.length)
{
if( arr[left] >= arr[right] )
{
//shift digits to bring the digit from right
shiftDigits(arr,left,right);
right++;
}
else
{
left++;
}
}
System.out.println(Arrays.toString(arr));
}

public static void shiftDigits(int[] arr, int left, int right)
{
int digit = arr[right];

while(right > left)
{
arr[right] = arr[--right];
}
arr[left] = digit;
}

}``````

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

If first array will be size of 99999 records and second will have 3 records, you have to do much operations. You should use binary search logic to find the next array rather than linear approach.

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

i can think only about O(n^2) solution : for each element in second sub array, find its place by binary search and evaluate amount of elements of second sub array that should be copied there, i mean if i have 1 2 5 6 7 3 4, we will find place of 3 and 4 by one binary search, but it is still O(n^2)

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

``````#include<stdio.h>
#include<conio.h>

void main(){
int arr[] = {1,4,5,7,8,9,2,3,6,10,11}, startIndex2dArray = 0;
printf("Array before sorting: ");
for(int i=0; i<10; i++){
printf("%d, ",arr[i]);
}
//Finding start index of 2nd array.
for(int i=0; i<10; i++){
if(arr[i] < arr[i+1]){
startIndex2dArray++;
}else{
startIndex2dArray++; break;
}
}
for(int j=0, k=0; j<startIndex2dArray; ){
if(arr[j] < arr[startIndex2dArray+k]){
j++;
}else{
int temoElmnt = arr[startIndex2dArray+k], p=startIndex2dArray+k, temp;
while(p>=j){
arr[p] = arr[p-1]; p--;
}
arr[j] = temoElmnt; j++;k++;
}
}
printf("\n\nArray after sorting: ");
for(int i=0; i<10; i++){
printf("%d, ",arr[i]);
}
getch();
}``````

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

find the index where the trend shifts. now perform a merge sort with (0 to x-1) as one set and (x to n) as another set.

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

public static void SortTwoMergedArrays(int[] data)
{
int sIndex = 0;

for (int i = 0; i < data.Length; i++)
{
if (data[i] > data[i + 1])
{
sIndex = i + 1;
break;
}
}

for (int i = 0; i < sIndex; i++)
{
if (data[i] > data[sIndex])
{
int tmp = data[i];
data[i] = data[sIndex];
data[sIndex] = tmp;

//then replace item in second array
for (int t = sIndex; t < data.Length-1; t++)
{
if (data[t] > data[t + 1])
{
tmp = data[t];
data[t] = data[t + 1];
data[t + 1] = tmp;
}
else
break;
}
}
}
}

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

doesnt it sound like last step of merge sort?

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

this is the last step of mergesort...

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

#include<iostream>
#include<conio.h>
using namespace std;
int main()
{int i;
int a[]={1,4,5,7,8,9,2,3,6,10,11};
for(i=1;i<11;i++){
if(a[i-1]<a[i]){continue;}
else
{
int val=a[i];
for(int k=i-1;k>=0;k--)
if(a[k]>val)
{a[k+1]=a[k];}
else
{a[k+1]=val;break;}
}
}
for(int i=0;i<11;i++)
cout<<a[i];
getch();
}

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

public class a
{
public static void main(String[] args)
{
int k=0;
int a[]={1,3,5,7,9,2,4,6,8};
for(int i=1;i<a.length;i++)
if(a[i-1]<a[i])
continue;
else
{
int v=a[i];
for(;k<i&&a[k]<a[i];k++);
System.arraycopy(a,k,a,k+1,i-k);
a[k]=v;
k+=1;
}
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
}

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

``````def msort(array):
if len(array) <=1:
return
left_index = 0
right_index = 1
while right_index < len(array):
if array[right_index] < array[right_index-1]:
break
right_index += 1
if right_index == len(array):
return
#merge the left and right part
while left_index < right_index and right_index < len(array):
if array[left_index] <= array[right_index]:
left_index += 1
else:
tmp = array[right_index]
#move elements [left_index,right_index) one step to right
for i in range(right_index,left_index,-1):
array[i] = array[i-1]
array[left_index] = tmp
left_index += 1
right_index += 1
return``````

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

``````static void q4(int a[])
{	int i;

for (i=1;i<a.length;i++)
{if (a[i]<a[i-1]) break;}

for (int j=0;j<a.length && i<a.length;j++)
{
if (a[i]<a[j])
{
int temp=a[i];
for (int k=i;k>j;k--)
{
a[k]=a[k-1];
}
a[j]=temp; i++;
}
}
}``````

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

1. Using Binary search approach to find a boundary: log(n)
2. Replace elements accordingly: n
Result: n log(n)

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

Step1:-use binary search for find where the second sorted arrrey start assume it is kth position then
Step2:-merge both arreys one is start from 0 to k-1 and second one start from k to n;
so our solution will take less time as it take for merging..!!

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

I have an approximately O(n) solution. What you want to do is find the beginning of the second sub-array by starting at the end, and decrementing the reference index by 1 until either the current element is less than the element previous to it in the array, or if the reference index becomes 0 (in which case, the two sorted sub-arrays are already fully sorted). We'll call the resulting index "r". Then, set another index at the beginning of the array, we'll call that index "l".

Now, iterate the "l" pointer through the array. Compare the value at a[l] with the value at a[r]. If a[l] is less than a[r], increment l. Otherwise, swap the values at l and r, and then increment r. When both l and r have incremented past the end of the array, the sorting is finished.

Java code looks like:

``````public void sort(int[] a) {
int left = 0;
int right = a.length - 1;

// find beginning of second sub-array
while(right != left || a[right] > a[right-1]) {
right--;
}

while(right != a.length && left != a.length) {
if(a[left] < a[right]) {
left++;
} else {
swap(a, left, right);
right++;
}
}
}

public void swap(int[] a, int l, int r) {
int tmp = a[l];
a[l] = a[r];
a[r] = tmp;
}``````

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

Not most efficient way, but a pretty simple one:

``````int * sortInPlace(int * arr, int size){

int * secArr = arr;
int i = 0;

for(i=0; i<size-1; i++){

if((*secArr)>(*(secArr+1))){
secArr++;
break;
}
secArr++;
}

for(int j=i+1;j<size;j++){

int * tempArr = arr;
while(tempArr != secArr){
if(*tempArr > *secArr){

int temp = *tempArr;
*tempArr = *secArr;
*secArr = temp;

}
tempArr++;
}
secArr++;
}

return arr;
}``````

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

Here is my take on the problem.
Logic:
a. We need to know the indexes of the two arrays.
b. Start merging from the end of two arrays.
c. Compare FirstArray[i] and SecondArray[j],

``````if(SecondArray[j] > FirstArray[i])
{
j--;
}``````

That was easy. Now consider the opposite case, when FirstArray[i] > SecondArray[j]. We will swap. But now the FirstArray is o longer a sorted array as it may be possible after swapping FirstArray[i] < FirstArray[i-1].

And we do not want to bubble this element as that will only increase the time complexity. What we will do is that we will keep the element there. And if (FirstArray[i] < FirstArray[i -1]) we will decrement i, as in FirstArray[i -1] becomes the candidate for merging at the end of the array.

``````//
if (FirstArray[i] > SecondArray[j])
{
Swap(FirstArray[i], SecondArray[i]);
if (FirstArray[i] < FirstArray[i-1])
i--;
}``````

If we continue this process, then FirstArray element distribution will end up as an array of two sorted arrays. We apply the same algo on FirstArray now.

Lets look at how this will work for our sample.

``````1.    [ 1 4 5 7 8 9 2 3 6 10 11]  // i = 5, j = 10 Compare 11 and 9. Since SecondArray > FirstArray, we will decrement j
2.    [ 1 4 5 7 8 9 2 3 6 10 11] // i = 5, j = 9, Compare 10 and 9--> j needs to be decremented
3.    [ 1 4 5 7 8 9 2 3 6 10 11] // i = 5, j = 8 Compare 6 and 9 ---> values need to be swapped
4.   [ 1 4 5 7 8 6 2 3 9 10 11] // But now you can see First Array is no longer a sorted array. We will compare FirstArray[i] and FirstArray[i -1]. Since 8 > 6, we will decrement i as well
5.  [1 4 5 7 8 6  2 3 9 10 11]  // i = 4, j = 7, compare value 8 with 3, clearly a swapping is required. we will do the same thing as above step
6. [1 4 5 7 3 6 2  8 9 10 11] // i = 3, j = 6, compare 7 with 2.
7. [ 1 4 5 2 3 6 7 8 9 10 11]``````

Now if you look at the FirstArray [1 4 5 2 3 ], its again a mix of sorted array. We will do the same steps of First Array.

[ 1 4 5 2 3]
[1 4 3 2 5]
[1 2 3 4 5]

Ans we will get the sorted array.

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

1. Find the last element of both sorted sub arrays.
2. Let's say i=index of last element subarray1 j= index of last element subarray2.
3. while(j>=i) {
If(array[i] > array[j]) {
swap(array[i], array[j])
i--;
} else {
j--;
}
}
4. Finally array will contain sorted list.

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

While Loop is (j>i). Efficient and no extra memory..

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

It doesn't work for the below case..

say the array to be [1,2,3,4,5,7,6]
in this array.. the two subarrays are [1,2,3,4,5,7] [6]..

i=5(i.e. index of last element of subarray1),
j=6(i.e. index of last element of subarray2)

the 3rd step of while loop condition ( j> =i) never quits..as you keep decrementing i.. finally you get the exception when i=-1

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

Because the index of last element of subarray1 is always less than or equal to index of last element of subarray2 i.e. (i<=j).. the while loop condition should also contain condition i>0, i..e. while(i>0 && i<=j) should be the condition to successfully bypass the above use case of [1,2,3,4,5,7,6] , you will never get the codition of j<n (bcz j is decremented in the while loop) & j>0 ( bcz before j reaches negative values..it has to cross i first)

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

Yes you are correct.. Boundary conditions i missed out. Apart from that I hope its correct.

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

na ho payega babuwa....rahene do tum

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

Based on the selection sort principle.. we can perform sorting more efficiently & it's in-place too

``````say len = length of the array

for(int i=1;i<len;i++)
{
j=i-1;
key = A[i];
while(j>=0 && A[j]>key){
A[j+1]= A[j];
j=j-1;
}
A[j+1]=key;
}``````

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

randomized quick sort has expected time O(nlogn) and O(N^N) worst case,
which is also an inplace sort

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

This can be done using heap sort with has the O(nlgn)
The key is to build min heap here and keep on shrinking the array size from left which is the sorted in increasing order
The condition that the min heap needs to follow is that the value of children is greater or equal to the parent and this can be considered as the loop invariant condition => loop invariant is the condition which needs to be satisfied in every loop inorder to sort the seq

here is the algo
1) create min heap - O(n)
2) for range starting from 0 to n-1; call min_heapify on Array[ i to n]
which will push the minimum value to top and we can consider the heap from i+1 index in the next loop
there by building sorted array

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

public static int[] merge_sorted(int a[], int b[]) {

int arr[] = new int[a.length+b.length];

int end_position = a.length+b.length -1;
int first_array = a.length -1;
int second_array = b.length -1;

while (end_position >= 0) {

if (first_array >= 0 && second_array >= 0) {
arr[end_position--] = a[first_array] > b[second_array] ?
a[first_array--] : b[second_array--];
}

if (first_array >= 0 && second_array < 0) {
arr[end_position--] = a[first_array--];
}

if (second_array >= 0 && first_array < 0) {
arr[end_position--] = a[second_array--];
}
}

for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
return arr;
}

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

O(n lgm) algo where m is the length of the shorter sorted array.
Maintain two pointers beginning at each array. Compare the two current values and insert the out of place value in the other array using binary search.

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

Here is O(N) time algorithm. It's kinda hard to explain in words so I wrote a program. It may not seem O(N) because of so many loops but I guarantee that it's O(N). I have tested for given two inputs and some other special cases. You may try more others. If you have counter example then please let me know.

``````def sort(lst):
s1=0
s2=1
#Find start index of second list
while s2 < len(lst) and lst[s2-1]<lst[s2]:
s2+=1
#sorting loop
while s1<len(lst) and s2<len(lst) and s1<s2:
if lst[s1] >= lst[s2]:
index=s2
count=0
#finding the count of elements which need to be swapped
while index< len(lst) and lst[s1] >= lst[index]:
count+=1
index+=1
index=s2
#swapping elements
swap(lst,s1,index,count)
s1+=count
else:
s1+=1
print(lst)

def swap(lst,s1,s2,count):
while count!=0:
lst[s1],lst[s2] = lst[s2] , lst[s1]
s1+=1
s2+=1
count-=1

lst=[1, 5, 10, 15, 20, 2, 3, 4]
lst=[1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11]
sort(lst)``````

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

Here is the c Code for above program
It forst looks for the starting point of second array
and then sorts it

``````#include<stdio.h>

main()
{
int i,j,t,n,l,k;
printf("Enter the size of the array : ");
scanf("%d",&n);
int a[n];
printf("\n\nEnter tha array elements :\n\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);

//finding starting pos of the 2nd array
l=-1,j=n;
for(i=1;i<n;i++)
if(a[i-1]>a[i])
j=l=i;

//sorting the array
for(i=0;i<l;i++)
{
if(a[j]<a[i])
{
t=a[i];
a[i]=a[j];
for(k=j+1;k<n && a[k]<t;k++)
a[k-1]=a[k];
a[k-1]=t;
}
}

//printing result
printf("\n\n\n\n\n");
printf("The sorted array is :\n\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
}``````

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

``use second part of the array as min-heap. (second part of the array is min-heap and no need to initiate make_heap(a+n/2)``

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is how I did it:

``````import java.util.Arrays;

public class Two_Sub_Sorted_Array {
public static void main(String[] args) {
int[] arr = {1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11};
sort(arr);
}

public static void sort(int[] a) {
int sec = 0;//first index of second array

for (int i = 0; i + 1 < a.length; i++) {
if(a[i] > a[i + 1]) {
sec = i + 1;
break;
}
}
//first array
int[] a1 = Arrays.copyOfRange(a, 0, sec);
//second array
int[] a2 = Arrays.copyOfRange(a, sec, a.length);

System.out.println("a1: " + Arrays.toString(a1));
System.out.println("a2: " + Arrays.toString(a2));

//result array
int[] res = new int[a.length];
int c1 = 0, c2 = 0, limit = 0;
boolean arr1 = false;

//sorting
for (int i = 0; i < res.length; i++) {
if(a1[c1] < a2[c2]) {
res[i] = a1[c1++];
} else if(a1[c1] > a2[c2]) {
res[i] = a2[c2++];
} else if (a1[c1] == a2[c2]) {
res[i] = a1[c1++];
res[++i] = a2[c2++];
}
if(c1 == a1.length){
limit = i + 1;
arr1 = true;
break;
} else if (c2 == a2.length) {
limit = i + 1;
break;
}
}
if(arr1){
for (int i = limit; i < res.length; i++) {
res[i] = a2[c2++];
}
} else {
for (int i = limit; i < res.length; i++) {
res[i] = a1[c1++];
}
}
//printing the result
System.out.println(Arrays.toString(res));
}
}``````

Output:

``````a1: [1, 4, 5, 7, 8, 9]
a2: [2, 3, 6, 10, 11]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]``````

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

is this an in place algorithm , you are making use of another data structure res right ?

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

just find the starting position of the second subarray and do a insertion sort

Comment hidden because of low score. Click to expand.
-1
of 3 vote

It sounds like it's essentially an in-place merge operation. The code below should do it in O(N^2) time, by doing a normal merge, but inserting the element in the correct position in the second array if it's out of position in the first.

There's a solution here: h2database.googlecode.com/svn/trunk/h2/src/tools/org/h2/dev/sort/InPlaceStableMergeSort.java that is O(N*log(N)) but it's not trivial.

``````import java.util.Random;

public class SortTwoSubArrays {

//	An array contains two sub- sorted arrays. Give an inplace algorithm to sort two sub arrays.
//
//	for ex: I/P: 1 4 5 7 8 9 2 3 6 10 11
//	O/P: 1 2 3 4 5 6 7 8 9 10 11

public static void main(String[] args)
{
{
int [] arr = {1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11};
sortSub(arr);
for(int v : arr)
{
System.out.print(v + ", ");
}
System.out.println();
}

{
Random rand = new Random();
int [] arr = new int[20];
int at = 0;
for(int i = 0; i < 10; i++)
{
at += rand.nextInt(5);
arr[i] = at;
}
for(int i = 10; i < 20; i++)
{
at += rand.nextInt(5);
arr[i] = at;
}

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

public static void sortSub(int [] arr)
{
int cut = -1;
for(int i = 1; i < arr.length; i++)
{
if(arr[i-1] > arr[i])
{
cut = i;
break;
}
}
if(cut == -1)
return;
int aAt = 0;
int bAt = cut;
System.out.println("Found cut at " + cut);
while(true)
{
System.out.println(aAt + ", " + bAt);
if(aAt == bAt || bAt == arr.length)
break;
//If current a-value is largest, simple; just inc a counter
if(arr[aAt] < arr[bAt])
{
aAt++;
}
//If not, we have to put the b-value into the 'sorted' part
//and then shift the a-value into the b-array; this is O(N)
//worst case
else
{
int temp = arr[aAt];
arr[aAt] = arr[bAt];
int curBAt = bAt;
while(true)
{
//insert here
if(temp < arr[curBAt+1] || curBAt+1 == arr.length)
{
arr[curBAt] = temp;
break;
}
//keep shifting and looking
{
arr[curBAt] = arr[curBAt+1];
}
curBAt++;
}
aAt++;
//curBAt++;
}
}
}
}``````

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

Yes, this question seems to be asking for an in-place merge algorithm.

Doing the insertion sort like steps, should work to give us an O(n^2) algorithm.

Getting an O(n) time merge algorithm is quite difficult, and research papers have been written about it (after being open for some time).

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

Then why not use a simple quick sort ???? Why pick an algorithm with N^2 complexity ???
just too much hardwork for no specific reason...

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

we can do it O(n) . The given input is a two sorted array merged together . We just need to find the index of an element which has a condition (array[index-1] < array[index] ) && (array[index] > array[index+1]) . Then just a simple merge will do the job

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

@Mr.karthik.p: The issue is that a merge is really not so simple when you don't have extra space.

@Bevan: That makes sense if you want an O(n log n) solution. You wouldn't be taking advantage of the fact that the array is just two sorted arrays back-to-back (instead of being just random data), but it's still a decent algorithm all in all. You probably want to use an in-place heapsort because quicksort does use just a little bit of extra space (logarithmic).

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

@eugene my bad we can do it O(nlogn) . find the change index and consider second array as min heap and whenever the head element of array is less swap with the index of the first array , increment the count of index of first array and heapify the second array.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Apply Insertion Sort.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is my try.......... Is this in space algorithm.........?

import java.io.*;
class Inplace
{
public static void main(String q[])
{
DataInputStream dis=new DataInputStream(System.in);
int n1,n2,n,a[]=new int[20],i,j;
System.out.println("Enter the length ");

try
{
System.out.println("Enter the elements : ");
n1=n2;
for(i=0;i<n2;i++)
{
if((i!=0)&&(a[i]<a[i-1]))
{
n1=i;

}
}

i=n1-1;j=n2-1;
while((i>=0)&&(j>=n1))
{
if(a[i]<a[j])
{
j-- ;
}
else
{
int c=a[i],k;
for(k=i;k<j;k++)
a[k]=a[k+1];
a[k]=c;
i--;
j--;
n1--;
}
}
System.out.println("Sorted Numbers are");
for(i=0;i<n2;i++)
System.out.println(a[i]);
}
catch(IOException e)
{

System.out.println(e);
}

}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is my try....... Is this inspace algorithm.........?
import java.io.*;
class Inplace
{
public static void main(String q[])
{
DataInputStream dis=new DataInputStream(System.in);
int n1,n2,n,a[]=new int[20],i,j;
System.out.println("Enter the length ");

try
{
System.out.println("Enter the elements : ");
n1=n2;
for(i=0;i<n2;i++)
{
if((i!=0)&&(a[i]<a[i-1]))
{
n1=i;

}
}

i=n1-1;j=n2-1;
while((i>=0)&&(j>=n1))
{
if(a[i]<a[j])
{
j-- ;
}
else
{
int c=a[i],k;
for(k=i;k<j;k++)
a[k]=a[k+1];
a[k]=c;
i--;
j--;
n1--;
}
}
System.out.println("Sorted Numbers are");
for(i=0;i<n2;i++)
System.out.println(a[i]);
}
catch(IOException e)
{

System.out.println(e);
}

}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Make one pointer point to the beginning of the 2nd sub-array and another pointer to the beginning of the first sub-array. Keep on comparing the values of these to pointers and change position if required. O(1) space O(n) time.

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

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

Nope. You are wrong. the second swap that you did will not occur as pointer 2 will go to null. At least try and make some sense!

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

then this case 146235.......

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

If the sub arrays are already sorted, just use pointers and iterate through them

``````a = {[1,3,5], [2, 4, 6]}
...
a = {[1,2,5], [3, 4, 6]}
...
a = {[1,2,3], [5, 4, 6]}
...
a = {[1,2,5], [4, 5, 6]}``````

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

Last line is suppose to be

``a = {[1,2,3], [4, 5, 6]}``

obviously

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

also you write a simple swap method that swaps the two values in place

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

insertion sort

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

But it is not that much easy.........
if a={[1,4,6],[2,3,7]}
how will you proceed...........?

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.