Interview Question Software Engineer / Developers
How about this?
array: arr[0:N-1]
shift: k
for(i=0;i<n;i++)
{
arr[i]=arr[i]^arr[(i+k)%n];
arr[(i+k)%n]=arr[i]^arr[(i+k)%n];
arr[i]=arr[i]^arr[(i+k)%n];
}
The idea is to swap arr[i] and arr[(i+k)%N], using X-OR.
We can also check in the beginning if K%N==0, then shift is not required.
I assume you are saying that this wont work.
Can you please provide any input array where it wont work ?
array: 1 2 3 4
k: 2
the formula: i -> (i+2)%4
loop from 0 to 3
0 -> 2 : 3 2 1 4
1 -> 3 : 3 4 1 2
2 -> 0 : 1 4 3 2
3 -> 1 : 1 2 3 4
the result will be (3 4 1 2) but we get (1 2 3 4).
The problem here is that i is swapped with i+k, but in cases where (i+k)%N is already swaped, the algorithm flunks.
So the correct approach (i believe) is:
for(i=0;i<n;i++)
{
if(i+k<n)
{
arr[i]=arr[i]^arr[(i+k)%n];
arr[(i+k)%n]=arr[i]^arr[(i+k)%n];
arr[i]=arr[i]^arr[(i+k)%n];
}
else
{
arr[i]=arr[i]^arr[(i+k)%n+k];
arr[(i+k)%n+k]=arr[i]^arr[(i+k)%n+k];
arr[i]=arr[i]^arr[(i+k)%n+k];
}
}
Basically the idea is
1) swap elements at i & i+k if i+k<=N-1
2) swap elements at i & (i+k)%N + k otherwise
the reason for the case 2 is that element at (i+k)%n is already swapped at (i+k)%n+k
void CyclicShift(int a[], int N, int K)
{
if (K > N) K %= N;
if (!K) return;
int processed_elements = 0, loop_start_index = 0;
while (processed_elements < N)
{
int current_index = loop_start_index;
int memory = a[current_index];
do
{
int mapped_index = (current_index + K) % N;
// swap
a[mapped_index] ^= memory ^= a[mapped_index] ^= memory;
++processed_elements;
current_index = mapped_index;
} while (current_index != loop_start_index);
++loop_start_index;
}
}
"Optimal" my ass. In my benchmarks, this is 8 times slower than ftfish's method (shift a 2^20 element array by 2^10).
@fiddler.g
Really nice one.
But I am thinking whether we really need the external loop of "while (processed_elements < N)"?
I am sure you must have thought of some case for which we need this condition. Can you give one example for this?
I got it
for an array of size N and shift K, if we have an i such that i<N and K*i%N==0, then we will need this condition.
Regarding the three reverse solution, I have seen the same solution on different websites too but i am not sure how it works.
Let me give an example:
arr={1 2 3 4 5}, N=5, shift =2
after 1st reverse, arr= 2 1 3 4 5
after 2nd reverse, arr= 2 1 5 4 3
after 3rd reverse, arr= 3 4 5 1 2
But the answer should be: 4 5 1 2 3
So am i missing something here-in?
i think the reversing solution should be:
reverse a[0,n-k-1]
reverse a[n-k,n-1]
reverse a[0,n-1]
EX1:
arr={1 2 3 4 5}, N=5, shift =2
after 1st reverse, arr= 3 2 1 4 5
after 2nd reverse, arr= 3 2 1 5 4
after 3rd reverse, arr= 4 5 1 2 3 ---> ANS
EX2
arr={1 2 3 4 5 6}, N=6, shift =2
after 1st reverse, arr= 4 3 2 1 5 6
after 2nd reverse, arr= 4 3 2 1 6 5
after 3rd reverse, arr= 5 6 1 2 3 4 ---> ANS
Let the array be A[1..n]
- ftfish July 10, 2010reverse A[1..k]
reverse A[k+1..n]
reverse A[1..n]
O(n) Time and O(1) extra space.