Amazon Interview Question for Software Engineer / Developers


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)

- Karan March 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- EOF September 15, 2013 | Flag
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]);
		}				
	}

}

- bbarodia March 08, 2013 | Flag Reply
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.

- iman.goodarzi March 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You solution will be O(n^2)

- EOF September 15, 2013 | Flag
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).

- showell30@yahoo.com March 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- showell30@yahoo.com March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Nomad August 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anand March 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- af March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anand March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 votes

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

- Suhas March 15, 2013 | Flag
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.

- JDev March 08, 2013 | Flag Reply
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;
	}

}

- JDev March 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Digi Digi April 05, 2013 | Flag
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)

- Kirill March 08, 2013 | Flag Reply
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();
}

- Shashi Vidyarthi March 08, 2013 | Flag Reply
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.

- devil@work March 08, 2013 | Flag Reply
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;
}
}
}
}

- Kabo March 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

doesnt it sound like last step of merge sort?

- abhi March 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is the last step of mergesort...

- Anonymous March 10, 2013 | Flag Reply
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();
}

- selva March 10, 2013 | Flag Reply
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]);
}
}

- selva March 10, 2013 | Flag Reply
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

- fory March 10, 2013 | Flag Reply
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++;
			}			
		}
	}

- bling! March 11, 2013 | Flag Reply
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)

- Anonymous March 12, 2013 | Flag Reply
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..!!

- Mukesh Kumar Dhaker March 12, 2013 | Flag Reply
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;
}

- mvalent23 March 14, 2013 | Flag Reply
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;
}

- dkrtemp March 15, 2013 | Flag Reply
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.

- SR March 18, 2013 | Flag Reply
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.

- Senthilmanikandan March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- uk.senthil88 March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

according to your logic..
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

- Anonymous March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Anonymous March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Senthilmanikandan March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

na ho payega babuwa....rahene do tum

- jiyooz March 19, 2013 | Flag
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;
    }

- Anonymous March 19, 2013 | Flag Reply
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

- denny.Rongkun March 19, 2013 | Flag Reply
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

- Sandy March 21, 2013 | Flag Reply
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;
}

- Anonymous March 25, 2013 | Flag Reply
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.

- EK MACHCHAR May 05, 2013 | Flag Reply
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)

- G10 May 23, 2013 | Flag Reply
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]);
}

- D3^!L June 08, 2013 | Flag Reply
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)

- Anonymous July 15, 2013 | Flag Reply
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]

- Sam March 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Jack March 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 12, 2013 | Flag
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++;
			}
		}
	}	
}

- Anonymous March 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- Loler March 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 votes

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

- Bevan March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Mr.karthik.p March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- eugene.yarovoi March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Mr.karthik.p March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Apply Insertion Sort.

- Ashish Anand March 08, 2013 | Flag Reply
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
{
n2=Integer.parseInt(dis.readLine());
System.out.println("Enter the elements : ");
n1=n2;
for(i=0;i<n2;i++)
{
a[i]=Integer.parseInt(dis.readLine());
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);
}

}
}

- Anand March 08, 2013 | Flag Reply
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
{
n2=Integer.parseInt(dis.readLine());
System.out.println("Enter the elements : ");
n1=n2;
for(i=0;i<n2;i++)
{
a[i]=Integer.parseInt(dis.readLine());
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);
}

}
}

- Anand March 08, 2013 | Flag Reply
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.

- alex March 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

swap will not help you, for example 12563 your algorithm produce 12365

- moizik March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- alex March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

then this case 146235.......
what will be answer of your concept...........

- Anand March 08, 2013 | Flag
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]}

- Frank March 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Last line is suppose to be

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

obviously

- Frank March 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Frank March 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

insertion sort

- gkb March 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anand March 08, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More