Google Interview Question
SDE1sCountry: United States
Is each element *exactly* k positions from its actual position or *at most* k positions from its actual position? If the former, simple swapping suffices. If the latter, one method is to have a moving window of length k. Find the smallest element of this window and then move the window to the right. (Represent the window as a heap to do this efficiently.)
Each number is at a distance of k from its original position -- this can only happen when we do only one swap of each position i with position i+k (conversely, i with i-k) . For example,
original numbers = [1, 2, 3, 4, 5, 6, 7, 8]. Then for k=2 we swap 1 and 3, 2 and 4, 5 and 7, 6, and 8. Final array would be [3, 4, 1, 2, 7, 8, 5, 6].
So, in the question we are given [3, 4, 1, 2, 7, 8, 5, 6] and we need to get back to original sorted array. So, we will do the same swap again and we will get back the original array (because swap is reversible).
There Can be two approaches both are easy ones.
First.
1. Insert K elements in heap
2. after that delete min and add new element
3.repeat till the end
complexity nlogk
Second
This one also provides nlogk but needs a better implementation of merge sort
1.divide array in n/k parts
2. sort those subparts O(klogk) time
3.Merge them from left
@Shankar:
Can you please give some example for this question?
I have some doubts regarding this question:
1) Output array will be fully sorted? in that case there will be only one possible position for each element in array, how can that be k from its initial position?
2) Is it possible that there is no solution of some given input?
3) Or output should be just each element should be k distance away from its initial position, but not sorted among themselves ?
In my understanding, if we want to make sure all elements are shifted k distance, k and N must satisfy: (1) N >= 2k; (2) N % 2k == 0
For example:
input: 1, 2, 3, 4, 5, 6, 7, 8
N = 8, k = 3;
1. consider input[0], it can only be moved to input[3]; and only input[3] can be moved to input[0] to fill it; thus, they are going to be swapped.
2. situation 1 applies when input[i] < k; and after doing that, all first 2k numbers are sorted.
we get 4, 5, 6, 1, 2, 3, 7, 8
3. now we need to get into next segment 7, 8; it is clear that they can not be sorted. This is the reason for the 2 conditions mentioned in the beginning.
since each number is at a distance k from its actual position, there are an even number of elements and to sort all one has to do is swap.
Let N be the size of the array
The size of the array is at least 2k
for(int i=0; i<k; ++i)
swap(a[i], a[i+k]);
if(4k <= N)
for(int i=0; i<k; ++i)
swap(a[2k+i], a[2k+i+k]);
and so on till the end of the array , i.e., divide the array into blocks of size 2k,
and inside each block swap the elements which are at a distance of k
The question says at a position k from its actual positions.
- srikantaggarwal January 28, 2014So, assuming that we can take an extra array, we start traversing the array.
For element at 0th index we put, kth element.
Similarly for any index i, we find element at (i-k), (i+k) index. We put at that position the leat of the two nos. provided the element is greater or equal to the element at (i-1) index.