Adobe Interview Question
I think we need to take under consideration that the sequence of numbers are already sorted in groups or may be not?
Actually, it doesn't make sense. any random set of numbers can be said as increasing and decreasing. For example, I just pressed numbers randomly on the keyboard and,
2 8 0 5 4 2 3 8 0 4 8
If you observe then, it increases to 8 then decreases to 0 then increases to 5 then decreases to 2..so on
any set of random numbers will have the behavior described in this problem. So its just a sort problem?
Agreed, I also couldn't think something else either. Does it make a difference if the question states each alternate increasing/decreasing sequences are of length 'k'?
Hey, just saw your comment.
Ya. It would make a difference. If the length of sequences are 'k' then there are n/k subsets which monotonically increase and then decrease. So once we find where the shift happens for a subset, now we can split this into two sorted arrays and merge. total: operations for every subset would be 2k (worst case)
In this way, we get all n/k subsets sorted in (n/k)*2k => 2n operations, now we merge n/k sorted arrays which should take (n/k)log(n/k). So total complexity would be O(2n + (n/k)log(n/k))
==> O(n/k * (2k+log(n/k) ) )
Best case would be O(n/k * log(n/k))
All of this with the condition that every k subset increases to a point and then decrease once. (Ex: the whole array can be a sine curve)
Correct me if am wrong. Thanks
I've edited the comment to change complexity analysis, it didnt change. Complexity would be
==> O(n/k * (k+log(n/k) ) )
Best case would be O(n/k * log(n/k))
I have a small doubt..
How is the merging of k n/k sorted arrays n/k log (n/k).
For merging 2 sorted arrays of length n/k, its O(n/k)
but after this we need to merge 2n/k with n/k, 3n/k with n/k, ... (k-1)n/k with n/k,
So the complexity will be O(n/k+2n/k+3n/k+...+(k-1)n/k) = n/k * (k * (k-1)/2) = O(n*k)
if we keep just one element in a block its O(n*n)
we can choose this method provided k<logn
and even merging requires additional space.
Merging in above explanation @anonymous I mean that I am referring to merge of merge sort algorithm.
Is there any other merging algorithm that you were discussing?
I think you got confused.
There are n/k sorted arrays of length k. (you are thinking the other way i.e. there are k arrays of length n/k. thats wrong understanding)
So merging two arrays of length k is O(k), it's basically merge sort. For example, in merge sort you start of with k=1, so complexity is O(n/1 log (n/1)) ==> O(n logn). Thanks.
@shashi: Well, merge sort can be done inplace but complicated. thomas baudel has a variant of inplace merge sort.
But if there's a simpler inplace sort for merging k sorted arrays then please suggest. Thanks
@chennavarri
One more clarification plzz....
Even if there are n/k arrays of length k. For sorting first two we need O(k). now we need to sort 2k with k, so O(2k) .... O(n/k.k). Totally its O(k+2k+3k+...+(n/k -1)*k)
= O(k * (1+2+3...+n/k - 1)) = O((n*n)/k)
am I wrong?
You were telling that we are merging the n/k "k" length sorted arrays using merge operation right ?
How are we getting that log term, please explain...
Thanks
Shashi
@Shashi sure I can explain. Consider u have 8 arrays of length k. Merge 1&2 and then 3&4 then 5&6 n 7&8. Now we have 4 2k length arrays. Repeat again. Merge 1&2 , 3&4
We r left with 2 arrays of size 4k each. Now merge these two we get an 8k length array.
Now why the log term. At every step we compare all 8k elements but how many steps are there??
One thing we observe is in the first step we had 8 arrays
Next step we had 4
& then we had 2. So basically the number of arrays halve every step sonnymver of steps = log8==3. Now to make it generic replace 8 with n/k.
If u want a pictorial representation wiki merge sort. The image explains it. Thanks
@Anonymous: Thanks for explanation. But going with ur explanation itself, it means that totally 8k elements will b compared and there r totally log8 such steps. Therefore the complexity should b O(8k log8). correct me if i m wrong...
now as u said, i will replace 8 with 'n/k'. then the complexity turns out to b: O((n/k)*k log 8)=O(n log 8)
Am I right???
@Chennavarri: good job. But if i have to merge 2 arrays of size n/2, then there will b totally n-1 comparisons in the worst case making it O(n).
Coming back to ur solution, to begin with we have 2 sorted arrays of k elements...merging them will take O(2k)...to generalize...if we have n/k sorted arrays of size k each...then at each step we will compare ((n/k)*k)=n elements making it of O(n)complexity...and there will b totally log(n/k) such steps...therefore the complexity of this solution should be O(n log n/k)...
in case of merge sort k=1 therefore O(n log n)
Correct me if i m wrong...
ya, thats right. complexity is O(n log(n/k)) for merging k sorted arrays totaling n elements. I replaced n with n/k for merge sort's complexity and wrote the above comment, hmmm... guess thats not the right way for writing complexities.
This can be done in O(N) time complexity. Keep on comapring the consecutive numbers until you get to the start of decreasing series, then make a note of this index and keep on going until you get the increasing series. Now make for reverse of this decreasing series.
Finally worst case time will be 2N, which is O(N).
The list in question is equivalent to a an unordered list, otherwise we could have said, 1) increasing or 2) decreasing or 3) increasing up to point then decreasing till the end or 4) decreasing up to a point then increasing till the end.
The only interesting part is "monotonically" increasing/decreasing, I don't think that would make much difference.
So, something like a Sine wave, sorting a sine curve?
- chennavarri November 05, 2010In any case, you can use any in place sorting algorithm such as QuickSort or heapsort with complexity O(nlogn) [best case]. Are we looking for better complexity?