Adobe Interview Question
It would be better to just make a bullet list explaining your solution. Coding isn't the difficult part of the problem, coming up with a good solution is.
I agree with you.. I was in hurry and coded this directly...
The idea behind it is:
e.g [2,4,7,9,1,3,5,8]
1. start with two pointers one at the beginning of an array and one at the point where decreasing element start say i and j
2. compare elements, if a[i] >a[j].. you need to swap
3. After swapping, make sure that you maintain the decreasing order of the second half by rotating the second half
4. Continue to work through the array (incr i) until you hit position j.. stop here as the remaining array is sorted by then.
What is the time complexity Anna
I think in the worst case it will taking O(nlogn) time, right?
Which a sorting algorithm takes.
We can reverse the once which are monotonically decreasing
Now after reversing all them we have k sorted arrays.
Reversing will be done in O(x) time therefore total time O(k/2x) where x is the maximum number of elements in the subarray
If we can solve the algo given 3407664 in O(n) time then total time will be O(k/2n) time.
Step1: Find the point after which the decrease starts let us call it P1. O(logn)
Step2: From P1 reverse the array. O(n)
Step3: Mark the beginning of the array as P2.
Step4: Now start a inplace merge sort, where first array begins at P1 and other at P2. O(n)
and Keep on doing ,,,
hey bro can u plzZZ elaborate on inplace merge sort..
coz i hav nt heard nethin about inplace merge sort b4.. :(:(
Take example -> 1,2,3,4,5,4,3,6,7.
Scan through the array to find the point where elements decrease. (Position -5 in above example where array starts from 0th position). Therefore, pos1=5
Scan from that position till elements increase again (pos2=7)
Reverse_array(pos1,pos2) -> Reverses content of array between pos1 and pos2.
Repeat the following steps till end of array is reached. Therefore, you have 'k' sorted arrays which needs to be sorted into 1 big array.
This can be done using k-way merge operation ( O(n) time with extra space)
OR
Perform k-way merge ( O(nlogn) time with O(1) space)
[Sorry, can't paste the link to the paper that can do the latter solution]
static void reverseArray(int[] array, int startIndex, int endIndex)
- anna July 19, 2010{
while (startIndex < endIndex)
{
int temp = array[startIndex ];
array[startIndex ] = array[endIndex];
array[endIndex] = temp;
endIndex--; startIndex++;
}
}
static void sortIncrDecr(int[]array, int decrIndex)
{
if (decrIndex >= array.Length)
return;
for (int index = 0; index < decrIndex ; index++)
{
if (array[index] > array[decrIndex])
{
int temp = array[index];
array[index] = array[decrIndex];
array[decrIndex] = temp;
if(((decrIndex+1) < array.Length )&& (array[decrIndex]>array[decrIndex+1]))
{
int tempIndex = decrIndex;
decrIndex++;
while (decrIndex < array.Length && array[tempIndex] > array[decrIndex])
decrIndex++;
decrIndex--;
reverseArray(array, tempIndex, decrIndex);
reverseArray(array,tempIndex,decrIndex-1);
printArray(array);
decrIndex = tempIndex;
}
}
}
}