## Amazon Microsoft Interview Question for Developer Program Engineers Software Engineer / Developers

Comment hidden because of low score. Click to expand.
19
of 23 vote

Algorithm:

First swap elements in the middle pair
Next swap elements in the middle two pairs
Next swap elements in the middle three pairs
iterate n-1 steps.

Ex: with n = 4.
a1 a2 a3 a4 b1 b2 b3 b4
a1 a2 a3 b1 a4 b2 b3 b4
a1 a2 b1 a3 b2 a4 b3 b4
a1 b1 a2 b2 a3 b3 a4 b4

Comment hidden because of low score. Click to expand.
0

Thanks. Very simple and elegant solution :)

``````int interleave(int arr[], int len) {
int n = len/2;
for (int i = 1; i < n; i++) { // my step no.
for (int j = 0; j < i; j++) { // no. of swaps
swap(arr, n-i+2*j, n-i+2*j+1);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

What would be the time complexity of this code..?? is it O(n)?
For 6 elements --> 2 swaps
For 8 elements --> 3 swaps
For 10 elements --> 4 swaps
For (2n+2) elements --> n swaps needed

Comment hidden because of low score. Click to expand.
0

What would be the time complexity of this code..?? is it O(n)?
For 6 elements --> 2 swaps
For 8 elements --> 3 swaps
For 10 elements --> 4 swaps
For (2n+2) elements --> n swaps needed

Comment hidden because of low score. Click to expand.
0

Nice.

May I ask what is the logic behind it.

Comment hidden because of low score. Click to expand.
0

I think the sum of the distance that each elements have to move is in the order of n^2.

Since each swap is reducing the total distance by a constant of 2. O(n) shouldn't be possible.

Comment hidden because of low score. Click to expand.
3

i think
1+2+3+4....n-1
which give you n(n-1)/2 swaps
so the time complexity is O(n^2).

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public class NewClass {
public static void main(String[] args) {
int[] nums={1,2,3,4,5,6,7,8};   //  get 1 5 2 6 3 7 4 8
int[] newarr=new int[nums.length];
int count=0,m=0;
for(int i=0;i<nums.length/2;i++){
newarr[count]=nums[i];
count+=2;
newarr[count-1]=nums[nums.length/2+i];
}
for(int i=0;i<newarr.length;i++)
System.out.print(newarr[i]+" ");
}
}``````

Comment hidden because of low score. Click to expand.
0

Nice Solution. But there is one more optimized solution of o(nlogn) using Divide and conquer.

Comment hidden because of low score. Click to expand.
0

This is not o(n), its o(n^2). There is a better divide and conquer solution. But It only works when input is of 2^n power.

Comment hidden because of low score. Click to expand.
0

Hey,

Your code runs in O(n^2) time.
First time it does 1 swap , then 2 and in the end it will perform n/2 swaps.

I attach my solution which is also in O(n^2) but I think it is more simple.

``````public static void changeArray(int[] array){

int i = 1;
int j = (array.length / 2);
while(j < (array.length - 1)){
int temp = array[j];
int k = j;
while(k > i) {
array[k] = array[k-1];
k = k - 1;
}
array[i] = temp;
i = i + 2;
j = j + 1;
}
return;
}``````

Comment hidden because of low score. Click to expand.
4
of 6 vote

I think there is an O(n) sol for this :)
I went thro some examples and the new position of an elt can be given mathematically
new id=(2*old id)%N...here N is the final index...not the number of elts...or (no of elts-1)
Heres the code

``````Re-arrange(int[] a){
int count=0;int i=1,int temp=a[1];
while(count<(N-1)){//to keep track of no:re-arranges which is N-1 in total
swap(temp,a[(2*i)%N]);
i=(2*i)%N;
count++;
}
}``````

I believe Anon has done the same above

Comment hidden because of low score. Click to expand.
0

@Sathya:
Am not convinced it works. Can you demonstrate on this array: [a1,a2,a3,a4,a5,b1,b2,b3,b4,b5]. Thanks

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is the same solution as mine, i wrote some code for generating arbitrary length arrays to shuffle, you can run it using python and just change the size of the array.
As Sathya says this is an O(n) solution

Comment hidden because of low score. Click to expand.
1
of 1 vote

@GekkoGordan:
ya i see...thx for pointing it out.Looks like there may be more than 1 cycle in the shift pattern...still wondering how to do in O(n)

Comment hidden because of low score. Click to expand.
0

@Sathya, yep as gekko pointed out this solution can have cycles and one way to avoid cycles is by using extra space. This question is a duplicate and I posted a similar solution which had the same issue, can't find the duplicate question using CC's search

Comment hidden because of low score. Click to expand.
3

@all
This modified solution works in O(n)

``````Re-arrange(int[] a){
int count=0,start=1,i=start,temp=a[start],N=a.length-1;
boolean notBreak=true;
while(notBreak){
swap(temp,a[(2*i)%N]);
i=(2*i)%N;
count++;
if(start==i){
if(count==N-1)
notBreak=false;
start+=2;
temp=a[start];
i=start;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Hey
Can anybody explain the algorithm for this...

Comment hidden because of low score. Click to expand.
0

awesome code :)

Comment hidden because of low score. Click to expand.
0

I'm not sure it's working.
I tried running. Works fine for some input.
Endlessly loops for an array of size 100. Don't know what's wrong.
Is this just me?

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2

O(log n) should be a magical solution instead of a brillian solution.. you're going to move n elements. O(log n) shouldn't be possible.

Comment hidden because of low score. Click to expand.
0

protected void Interleave(int[] arr)
{
int left = 1;
int right = arr.Length / 2;
int temp;

while (left < right)
{
for (int i = right; i > left; i--)
{
temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
}

left += 2;
right += 1;
}
}

Comment hidden because of low score. Click to expand.
0

protected void Interleave(int[] arr)
{
int left = 1;
int right = arr.Length / 2;
int temp;

while (left < right)
{
for (int i = right; i > left; i--)
{
temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
}

left += 2;
right += 1;
}
}

Comment hidden because of low score. Click to expand.
0

How could this solution get 5 votes? This does not work even when there are 26 elements in the array......

Comment hidden because of low score. Click to expand.
3
of 3 vote

Copies from another similar question asked in this forum

Algorithm:

First swap elements in the middle pair
Next swap elements in the middle two pairs
Next swap elements in the middle three pairs
iterate n-1 steps.

Ex: with n = 4.
a1 a2 a3 a4 b1 b2 b3 b4
a1 a2 a3 b1 a4 b2 b3 b4
a1 a2 b1 a3 b2 a4 b3 b4
a1 b1 a2 b2 a3 b3 a4 b4

Comment hidden because of low score. Click to expand.
0

Thanks. I have been breaking my head, trying to solve this problem.

Comment hidden because of low score. Click to expand.
0

This might take n-1 steps, but for the kth step, it needs to do k swaps. So, total number of operations = 1 + 2 + 3 + 4 .... + n-1 + n. which is O(n*n)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Only god can solve this in O(n) time and constant space.!!!
So correct soln..

Comment hidden because of low score. Click to expand.
3
of 3 vote

This is in place array transpose.

``````#include <stdio.h>

int get_index(int idx, int N) {
return (idx % 2) * N + (idx / 2);
}

void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}

void transform_array2(int *s, int len) {
int N = len / 2,i;
for(i = 0; i < len; i++) {
int new_idx = get_index(i, N);
while(new_idx < i) {
new_idx = get_index(new_idx, N);
}
printf("i: %d; new_idx: %d\n", i, new_idx);
swap(&s[i], &s[new_idx]);
}
for(i = 0; i < len; i++) {
printf("%d ", s[i]);
}
printf("\n");
}

int main()
{
int arr[]={1,2,3,4,5,6,7,8,9,10,11,12};
transform_array2(arr,12);
return 0;
}``````

Time complexity-O(n)

Comment hidden because of low score. Click to expand.
0

Are you sure it's O(n).

``````for(i = 0; i < len; i++) {
int new_idx = get_index(i, N);
while(new_idx < i) {
new_idx = get_index(new_idx, N);
}
printf("i: %d; new_idx: %d\n", i, new_idx);
swap(&s[i], &s[new_idx]);``````

}

What about the while loop inside for. Does it always takes constant time?

I think it's O(n^2) as inner while loop is dependent on n or it's O(n)

Comment hidden because of low score. Click to expand.
1
of 1 vote

Use divide and conquer for n log n. This is faster than O(n) in-place transposes on real hardware because of caching effects. (Yes, I've tried it.)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Input:
a1,a2,a3,a4,.....an,b1,b2,b3,b4,.....,bn
Output:
a1,b1,a2,b2,a3,b3,a4,b4,..........an,bn.

If we notice, there is a pattern for all elements while shuffling.
For all elements from 1st half portion (a1 to aN)
a[i] is moved to a[2*i] where 0<= i <= n [say array name is a]
i.e.
a[0] is moved to a[0] (for i=0, i = 2*i =0)
a[1] is moved to a[2]
a[2] is moved to a[4]
a[3] is moved to a[6]
......
....
For 2nd half, same is true from opposite (OR if we see array
inverted,b1 to bN behaves same as a's)
In other words, keeping array as is, 2nd half of the array (b1 to bN)
goes like this

a[i] is moved to a[(n+1)-2*(n-i)] where n/2 < i < 2n
i.e. (Assuming 2nd half array starting with index i=7, so total array
size 12)

a[7] moved to a[1]
a[8] moved to a[3]
a[9] moved to a[5]

overall as example:
Input
a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10], a[11]
Output:
a[0], a[6], a[1], a[7], a[2], a[8], a[3], a[9], a[4], a[10], a[5], a[11]

And I believe it's pretty straightforward to implement this. using
only few extra variables [not dependent on array size](Based on
implementation).
So, O(n) time and O(1) space [IN PLACE].

Alg: [assuming all elements are > 0)

Negate all elements (a[i] = -1 * a[i];)
current_index = 0;
current_element=A[0];
do
if current_index <= n/2 then
to_index = 2*current_index
else
to_index = (size + 1) - 2*(size - current_index)
end if
current_element = A[to_index];
A[to_index] = -1 * A[current_index];
if current_element > 0 then
to_index = index of next negative element.
current_index = to_index;
while A[current_index] < 0

Algo can be modified to check in other cases like when elements can be
negative also, OR elements are characters, strings.
There can be different ways to track if all elements are processed or
not, depending on problem.
e.g. if negative elements are also in input then,
Add some very very negative no to all elements say -50000 and while
assigning it to to_index, adding 50000
If element are characters, string then attach some keyword (prefix or
suffix) to each element,
while assigning it to to_index, remove the attachment.

Comment hidden because of low score. Click to expand.
0

I went through your alg. and I got your idea but I do not think your algo works in O(n) time, though I am not quite sure about my view.
Your algo runs based on a hop step which start at A[0] and A[1]->A[2]->A[3]->A[5]->A[7]->....>A[2N-1]->A[2N-3]->....
You mark the element with a special value(nagative number in your example) to track which elements moved. And when your to_index points to an element which is moved(positive in your example), the to_index still need to point to next negative element:
to_index = index of next negative element.
This step I think is also a loop based on the number of N cuz you need to travel the array until the negative and I think, where I am not sure here, it also cost (N) time. So in this case, the upper bound of time also is O(N^2), not O(N)......

Does this make sense?

Comment hidden because of low score. Click to expand.
0

This JAVA code correct Singh super tiny bug. What he make a mistake is the it can loop back to the first position it begin with while there are some value not move yet. The solution is simply move right one element (According to my observation the problem is at the position N/2+1). Below is the correction to Singh original post. It is O(N-2) and O(2) spaces as you need to keep tracking of the position and value you replace.
public class myArray {
public myArray(){}
public static void main(String args[]){
int[] arr_int = {1,2,3,4,5,6,7,10,20,30,40,50,60,70};

myImplaceSwap(arr_int);

for(int i=0;i<arr_int.length;i++)
System.out.print(arr_int[i]+ " ");
}
/**
* Rule # if i < N/2: new pos = 2*i
* Rule # if i >= N/2: new pos = i - [N+1-i] = 2*i - N+1
* Then only keep tracking of overflow position
* @param arr_
*/
public static void myImplaceSwap(int[] arr_){
int N = arr_.length;
int temp_pos = N/2;
int temp_val = arr_[N/2];
arr_[N/2] = -1;
int hold;
int it = N-2;
do{
it--;
if(temp_pos < N/2){
hold = arr_[2*temp_pos];
arr_[2*temp_pos] = temp_val;
temp_val = hold; temp_pos = 2*temp_pos;
}else{
hold = arr_[2*(temp_pos+1) - (N+1)];
arr_[2*(temp_pos+1) - (N+1)] = temp_val;
temp_val = hold;temp_pos = 2*(temp_pos+1) - (N+1);
}
if(temp_val == -1)
temp_val = arr_[++temp_pos];
}while(it > 0);
}

Comment hidden because of low score. Click to expand.
0

this solution fails for 24 element array. Why dont u explain the logic in algo..

Comment hidden because of low score. Click to expand.
0

Here shuffling is happening as per two rules (On current index):
If current_index is < array_size/2
move current_index to 2*current_index
else
move current_index to (array_size+1)-2*(array_size-current_index)
Here 1st element(a[0]) and last element(a[n-1]) will not move at all.
From index 1st, move current element as per above rule, wherever this element goes, that will be the next element to be moved (per above rules).
Keep doing this until ALL elements are moved.

Now here the tricky part is to tracked moved element (OR yet to move element). While moving elements, we may come to an element (as current element) which has been moved already. So we have to check if there is any more element yet to move, if so, start from there OR stop shuffling.

In following, I just negated all numbers 1st (Assuming array elements are positive). For other possible inputs, I mentioned some ways in my very 1st post.
This is IN PLACE and O(n). [It may look like O(n2) but I guess it's not (I may be wrong) because we have to RELOOK(when current_element is positive, that means moved already) into array for negative element for few times only, not n times, so its not nxn but constant X n.)

If we are allowed to use extra space, we may do the tracking by using hash (OR something else) easily. Put all in hash 1st, then keep removing moved elements from hash.

public class Shuffle {
public static void main(String args[]){
int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,10,20,30,40,50,60,70,80,90,100,110,120,130};

for(int i=1;i<a.length-1;i++)
a[i]=-1*a[i];

ShuffleArray(a);

for(int i=0;i<a.length;i++)
System.out.print(a[i]+ " ");
}
public static void ShuffleArray(int[] a){
int n = a.length;
int cnt=1;
int i=1;
int hold;
int curr,c;
curr=a[i];
while(cnt<=n && i<n)
{
if(i<n/2)
hold=2*i;
else
hold=n+1-2*(n-i);
c=a[hold];
a[hold]=-1*curr;
i=hold;
curr=c;
cnt++;
if(cnt<n && curr > 0)
{
for(i=2;i<n && a[i]>0;i++);
curr=a[i];
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void reorder(char[] input, int n) {
for (int i = 1; i < input.length; i = i+2) {
int replaceElem = (2*n + i - 1)/ 2;
char swap = input[replaceElem];
for (int j = replaceElem; j > i; j--) {
input[j] = input[j-1];
}
input[i] = swap;
}
}``````

Comment hidden because of low score. Click to expand.
0

I don't see this working.
for n=6 it goes out of index

Comment hidden because of low score. Click to expand.
0

@Code Saviour: The algorithm basically moves 2n/2 elements for 2n/2 elements. i.e. has a complexity of O(n*n) . And looks very similar to insertion sort. Since you observe that the problem is a subset of a sorting problem,

we get Complexity: O(nLogn)
-> change the array values from [a1,a2,a3...,an,b1,b2...bn] to [1,3,5,7....2n-1, 2,4,6,8,....2n]
-> now sort using any inplace sorting algorithm. For quick sort, take sizeof(array)/2 as the initial pivot.
Not sure if there's a linear algorithm, even if there is it might not be complete.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@blueskin: Yes, my algorithm has O(n*n) time complexity but O(1) space complexity. Your algorithm will need additional storage to store the corresponding values.

If we are allowed O(n) space complexity, the simplest thing to do would be to just use two queues. Put values a1 to an in Q1 and b1 to bn in Q2. Now, just dequeue one element from each and keep populating the array. O(n) time.

Comment hidden because of low score. Click to expand.
0

well, I literally thought of replacing 'a1','a2' characters with '1','3'... and changing back. such as k%2==0 replace with 'b(k/2)' else replace with 'a(k/2-1)'
Yep, u r right, we would need to consider the case where a1,b1 are objects and not just characters. I guess "Insertion Sort" will definitely work and has a known complexity.

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void ReOrder(ArrayList a)
{
for(int i=a.size()/2; i<a.size(); i++){
int finalPos=((i-a.size()/2)+1)*2-1;
String temp=a.get(i).toString();
for(int j=i; j>finalPos; j--){
a.set(j, a.get(j-1));
}
a.set(finalPos, temp);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

If [a1,a2,a3...,an,b1,b2...bn] is given input change this to [a1,b1,a2,b2.....an,bn]

The idea is to move index 2 everytime, starting at 1.
swap a[i] with a[len/2+i] - a1,b1,a3,a2,b2,b3.
swap a[i+1] with a[len/2+i] - a1,b1,a2,a3,b2,b3.

The idea to start with keep every 2 things in order and move forward.

Comment hidden because of low score. Click to expand.
0
of 0 vote

lets take a0, a1, a2, a3, a4, b0, b1, b2, b3 ,b4, b5.
1) swap a1 with b0 to get

a0, b0, a2, a3, a4, a1, b1, b2, b3 ,b4.

2) shift a1 to arr[2] to get
a0, b0, a1, a2, a3, a4, b1, b2, b3 b4.

now we reduced problem from 10no.arry to 8no. array.
two steps take n/2 swaps. decreasing by 1 with each iteration. so order is O(n2).

otherthan this, i did nt see a better solution. Can any one improve this?

Comment hidden because of low score. Click to expand.
0

one thing that we could improve on is , that
for given array , convert it into following in ( o(n) swap)
a[0],a[1],a[2],a[3],b[0],b[1],b[2],b[3]
TO
a[0],a[1],b[0],b[1],a[2],a[3],b[2],b[3]

now solve recursively for both half.
complexity = nlogn.

Comment hidden because of low score. Click to expand.
0

Using recursion uses space on the stack - so this is not correct. You will need to tweak a bit.

Comment hidden because of low score. Click to expand.
0

@ Sundar..Whats wrong if we use stack of recursion???its just tail recursion and shuldnt be much of a concern
below procedure does in O(n^2).Call would be (array,0,n)

``````Re-arrange(int[] a,int start,int rem){
if(rem>1){
//rotate right once from start to end position
Right-Rotate(a,start+1,rem+start);
Re-arrange(a,start+2,--rem);
}
}``````

but i prefer the idea of Adiser...

Comment hidden because of low score. Click to expand.
0

annoy soln will work in O(n2), will be too slow on large arrays. I guess the soln given in above 2 posts (working java code for array of positive numbers in my 2nd post) by me is O(n) and much much faster. Comment on that pls..

Also I'm not getting the idea in Adiser soln. Can anyone pls explain it on array:
a0,a1,a2,a3,a4,a5,a6,a7,b0,b1,b2,b3,b4,b5,b6,b7
Here expected output is:
a0,b0,a1,b1,a2,b2,a3,b3,a4,b4,a5,b5,a6,b6,a7,b7

Comment hidden because of low score. Click to expand.
0

Adiser, ur solution is perfect...till someone improves it to less than O(nlogn) :-)
Sundar, I dont think using recursion is objectionable. agree with Satya.

Anurag Singh, Can you try ur solution on arrays of size 6-20? i dont think it works.

logic for Adiser in using array demo.

if initial array is,
a0,a1,a2,a3,a4,a5,a6,a7, b0,b1,b2,b3,b4,b5,b6,b7

reduce it to solving two arrays of half size. by changing it to
a0,a1,a2,a3,b0,b1,b2,b3, a4,a5,a6,a7,b4,b5,b6,b7.
(basically u r swapping 2nd quarter of array with 3rd quarter) and recursively call alternate on two subsets.

here is my code. (very adhoc- no boundaries * null cheks)

Call with (array, 0, length-1).

``````/**
* ArrayShifts.java
*
* Created on 07-02-2011 01:58 PM
*
*/

public class ArrayShifts {

void printArray(int[] ar)
{
if (ar == null)
return;
for(int i=0; i<ar.length; i++)
{
System.out.print(ar[i] + " ");
}
return;
}
int[] reverseArray(int[] ar, int start, int end)
{
int temp;
while (start < end)
{
temp = ar[start];
ar[start++] = ar[end];
ar[end--] = temp;
//start++; end--;
}
return ar;
}
int[] alternateElements(int[] ar, int startPos, int endPos)
{
if(endPos <= startPos) return ar;
if((endPos - startPos)<= 2) return ar;

int n= (endPos - startPos)/2;
if(n%2 == 1)
{
ar = reverseArray(ar,startPos+n/2+1,startPos+n);
ar = reverseArray(ar,startPos+n+1,startPos+n+n/2+1);
ar = reverseArray(ar,startPos+n/2+1,startPos+n+n/2+1);
if (n==1)
return ar;
printArray(ar);System.out.println( "       " + startPos +" "+endPos);
ar = alternateElements(ar,startPos,startPos+n);
ar = alternateElements(ar,startPos+n+1,endPos);

}
else
{
ar = reverseArray(ar,startPos+n/2+1,startPos+n);
ar = reverseArray(ar,startPos+n+1,startPos+n+n/2+1);
ar = reverseArray(ar,startPos+n/2+1,startPos+n+n/2+1);
printArray(ar);System.out.println( "       " + startPos +" "+endPos);
ar = alternateElements(ar,startPos,startPos+n+1);
ar = alternateElements(ar,startPos+n+2,endPos);
}
return ar;
}

}``````

Comment hidden because of low score. Click to expand.
0

OK, I didn't test my previous code for many inputs and there were some issues.
Corrected the above code I gave and following is working well for input size 2-30 like:
1,10
1,2,10,20
1,2,3,10,20,30
1,2,3,4,10,20,30,40
etc..

I made few small change in the code to track what elements has been shuffled already and should not be shuffled again.
Logic still remains the same [ONLY tricky part is to track which element is shuffled alrerady and which one is yet to shuffle. Looks like this is the best soln. Time: O(n), Space: O(1)

Please verify it and see if it looks good.
If not, pls post the error/issues you see with following:

public class Shuffle {
public static void main(String args[]){
int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,10,20,30,40,50,60,70,80,90,100,110,120,130};

for(int i=1;i<a.length-1;i++)
a[i]=-1*a[i];

ShuffleArray(a);

for(int i=0;i<a.length;i++)
System.out.print(a[i]+ " ");
}
public static void ShuffleArray(int[] a){
int n = a.length;
int cnt=1;
int i=1;
int hold;
int curr,c;
curr=a[i];
while(cnt<n-1 && i<n)
{
if(i<n/2)
hold=2*i;
else
hold=n+1-2*(n-i);
if(a[hold] < 0)
{
c=a[hold];
a[hold]=-1*curr;
i=hold;
curr=c;
cnt++;
}
else
curr=a[hold];
if(cnt<n && curr > 0)
{
for(i=2;i<n && a[i]>0;i++);
curr=a[i];
}
}
}
}

Comment hidden because of low score. Click to expand.
0

Can someone explain how recursive algorithm by Adiser work when n is odd?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I tried a recursive process of starting at pos1, moving it to its correct place, then moving the element there to its correct place in tunr, once you have done len -1 steps you are done. You wont get any cycles because you are always putting something in its correct place - no 2 elements can be in the same place. Only the first element starts off in its correct place. Not sure if stack for recursion violates in-place though

``````def switch(arr, ind, mid, curr_val, step):
if ind < mid:
new_ind = ind*2
else:
new_ind = (ind - mid) * 2 + 1
next_val = arr[new_ind]
arr[new_ind] = curr_val
print "ind: %s, new_ind: %s, next_val: %s, curr_val: %s"
print '%s' % arr
if step < mid*2-1:
switch(arr, new_ind, mid, next_val, step+1)

def gen_arr(size):
arr = []
for i in range(size):
arr.append('a%s'%(i+1))
for i in range(size):
arr.append('b%s'%(i+1))
return arr

size = 15
print gen_arr(size)
switch(gen_arr(size), 1, size, 'a2', 1)``````

Comment hidden because of low score. Click to expand.
0

not working for size = 18

Comment hidden because of low score. Click to expand.
0

It doesn't work when a value is inserted in position 1 and it is not the last element that is moved

Comment hidden because of low score. Click to expand.
0

This code works in only some cases (15 being one of them). Unless you call switch in a for loop, I don't see it working for any non-cyclic permutation, the permutation here being defined on indices from (2) through (size - 1).
By Cyclic-permutation I mean the "Definition 2" given at http ://en.wikipedia.org/wiki/Cyclic_permutation

Comment hidden because of low score. Click to expand.
0
of 0 vote

Anurag,

how many times does the nested for loop run for each iteration? does nt that change order?

Comment hidden because of low score. Click to expand.
0

Nested loop (for loop inside outer while) ONLY runs when we find an element already shuffled in the shuffling process. And depending on input size, either this case will not arise OR may arise some some time say 4 OR 5 times but this doesn't depend on n, So I take this as constant. And so I say this soln is O(n).

I found following while testing it for input size upto 40

No for loop execution for input sizes:
2,4,6,12,14,20,30,38
for loop executes one time for input sizes:
8,10,18,24,26
for loop executes two times for input sizes:
28
for loop executes three times for input sizes:
16,34,40
for loop executes four times for input sizes:
22,36
for loop executes five times for input sizes:
32

Comment hidden because of low score. Click to expand.
0
of 0 vote

yup that works :) cool soln. thx satya.

Comment hidden because of low score. Click to expand.
0

@Satya, soln do not seems to working correctly. 'temp' variable value is not changing !

do somebody explain this.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another O(n) solution based on divide-and-conquer. Recursively divides n by 2, and use the result of two halves to merge the final result.

Examples demonstrate for n = 2^k. When n is not 2^k, we can add some dummy elements, and do the same process, and finally discard those that are dummy.

``````n = 1: a1 b1
n = 2:
a1 a2 b1 b2 => a1 b1 a2 b2
n = 4:
a1 a2 a3 a4 b1 b2 b3 b4 =>  a1 a2 b1 b2 a3 a4 b3 b4
=>  a1 b1 a2 b2 a3 b3 a4 b4
n = 8:
a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8
=> a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 a7 a8 b5 b6 b7 b8
=> a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8``````

1st step takes n/2 swap, 2nd step n/4 swaps. Total steps O(log n). So, total complexity O(n).

Comment hidden because of low score. Click to expand.
0

small correction:
step 1 => n swaps
step 2 => n/2 swaps
total swaps = 2n = O(log n)
space O(1)

Comment hidden because of low score. Click to expand.
0

it's O(n) space, and O(1) space

Comment hidden because of low score. Click to expand.
0

I think it is best solution but do not seems to work for if n is odd no.

e.g a1 a2 a3 a4 a5 b1 b2 b3 b4 b5

Comment hidden because of low score. Click to expand.
0

I think it works with any n. What i understood from buried.shopno's solution is that if n is not 2^k, we can assume dummies.
Let me work with your example here:

``````n = 5:
a1 a2 a3 a4 a5 b1 b2 b3 b4 b5
assume, n = 8:
then it becomes,
a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8
for which, we get
a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8

Now chop off the last entries [a6 - b8], and you get the answer.``````

I think this is standard solution, as in many divide and conquer based approach, like recursive matrix multiplication, it assumes n is 2^k, and special things to do for n != 2^k.

Comment hidden because of low score. Click to expand.
0

Thanks for the feedback.

I found my complexity analysis was wrong. Here it's:
f(n) = 2f(n/2) + O(n)
=> applying master theorem, it's O(n logn).

Comment hidden because of low score. Click to expand.
0

What is the space complexity for this? You said we need to add extra 'dummy' elements in the end for this to work. Wouldn't that be O(n) space?

Comment hidden because of low score. Click to expand.
0

Apparently you are right. If you don't allow any space than input size n, you can apply the general divide-and-conquer with below modifications for n != 2^k.

``````n = 7
a1 a2 a3 a4 a5 a6 a7 b1 b2 b3 b4 b5 b6 b7
a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 a7 b5 b6 b7
[by in place rotation of a5 a6 a7 b1 b2 b3 b4, which takes O(n) time]
a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 a7 b5 b6 b7

for subproblem of size n = 4, we know how to get solution.
for subproblem of size n = 3, we do in place rotation again.

a1 b1 a2 b2 a3 b3 a4 b4 a5 a6 b5 b6 a7 b7

finally,
a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I took anon's code for making the list but a different approach for arranging it - I believe this is O(n) and satisfies the in-space problem

``````def gen_arr(size):
arr = []
for i in range(size):
arr.append('a%s'%(i+1))
for i in range(size):
arr.append('b%s'%(i+1))
return arr
size = 15
arr = gen_arr(size)
index = size
while index < len(arr):
arr.insert(((index-size)*2)+1,arr[index])
index += 1
del arr[index]
print arr``````

The approach iterates over the last half of the list taking each element and inserting it in its correct place then removing the next element (since the front part of the list has grown by 1)

Comment hidden because of low score. Click to expand.
0

How it could be O(n) complexity in principle? Think carefully how "arr" is implemented in your language library? If it is an array, inserting element would take O(n) time as you need to adjust the indices of following elements.

I believe if it's given as an array, best solution is O(n logn) time. If it was represented as list, it's possible to do in O(n) - which is probably not the case (as mentioned in-place rearrangement).

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) ...

``````#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>

using namespace std;

vector<string>::iterator iter;

void swap (string& s1, string& s2) {
string s = s1;
s1 = s2;
s2 = s;
}

void print (vector<string>& str_arr) {
for (iter = str_arr.begin (); iter != str_arr.end (); ++iter) {
cout << *iter << " ";
}
cout << endl;
}

void reorder(vector<string>& str_arr) {
int n = (str_arr.size () >> 1);
int t;
string s;
for (int i = 1; i < n; i += 2) {
t = i;
s = str_arr[t];
str_arr[t] = "\$\$";
do {
if (t < n) {
t = (t << 1);
} else {
t = ((t - n) << 1) + 1;
}
swap (s, str_arr[t]);
} while (s.compare("\$\$") != 0);
}
}

int main () {
int n;
cin >> n;
char c_str[3];
string* str;
vector<string>* str_arr = new vector<string>();
for (char c = 'a'; c < 'c'; ++c) {
for (int i = 0; i < n; ++i) {
sprintf (c_str, "%c%d", c, i);
str = new string (c_str);
str_arr->push_back (*str);
}
}
print (*str_arr);
reorder (*str_arr);
print (*str_arr);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

You better understand the question first :)
Here a1,a2...an & b1,b2...bn can be integers, chars(or anything).

Comment hidden because of low score. Click to expand.
0

kartik,
can you explain the logic - i could not understand the code.

Comment hidden because of low score. Click to expand.
0

How can you claim it's linear when you have 2 nested loops? You don't need a comparison function... just swap the elements in question directly and remove that and your loop.

Comment hidden because of low score. Click to expand.
0

@karthik,
don't post some junk!!

Comment hidden because of low score. Click to expand.
0

@kartik

fuck off

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>

struct demo{
char c[3];
};

void swap(struct demo *a, struct demo *b)
{
struct demo temp;
temp = *a;
*a = *b;
*b = temp;
}

int  main()
{
int size,i,j,p,x,y;
static struct demo ab[10] = {{"a1"},{"a2"},{"a3"},{"a4"},{"a5"},{"b1"},{"b2"},{"b3"},{"b4"},{"b5"}};

size = sizeof(ab)/sizeof(ab[1]);

for(i=0;i<size;i++)
{
printf("%s ",ab[i].c);
}
printf(" \n");
p=size/2;

for(i=0; i<(size/2)-1; i++)
{
for (j=0;j<=i;j++)
{
x = (p-1-i) + (2*j);
y = (p-i) + (2*j);
//printf("Index is %d %d \t",x,y);
swap(ab+x,ab+y);
}
}
printf("\n");
for(i=0;i<size;i++)
{
printf("%s ",ab[i].c);
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Pls remove extra variables....

Output:
a1 a2 a3 a4 a5 b1 b2 b3 b4 b5

a1 b1 a2 b2 a3 b3 a4 b4 a5 b5

Time O(n)

Comment hidden because of low score. Click to expand.
0

> Time O(n)

``````for(i=0; i<(size/2)-1; i++)
{
for (j=0;j<=i;j++)``````

Nope, thank you for playing.

Comment hidden because of low score. Click to expand.
0
of 0 vote

// extension of swapping problem

j=n;
for(i=1;i<n;i++)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
j++;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

// extension of swapping problem

j=n;
for(i=1;i<n;i++)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
j++;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

// extension of swapping problem

j=n;
for(i=1;i<n;i++)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
j++;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

@ankur

Please run through the code.I don't think it is correct.
REsulting order has to be
a1,b1,a2,b2,a3,b3 ....

Comment hidden because of low score. Click to expand.
0
of 0 vote

Though bad in terms of efficiency, it can be done in way of insertion sort, where pick b1 and insert at 2nd position and copy a2-an one by one till b1 position

Comment hidden because of low score. Click to expand.
0
of 0 vote

void printArray(char a[][5],int len) {
int i;
for(i=0;i<len;i++) {
printf("%s ",a[i]);
}
printf("\n");
}

void shuttleArray(char a[][5],int len) {
printArray(a,len);
int count=1; int i,j; int pos=0;
char *newbuf=(char *)malloc(5);
char *oldbuf=(char *)malloc(5); char *tmp;
int *mark=(int *)malloc(sizeof(int)*len);
for(i=0;i<len;i++)
mark[i]=0;
i=1;
strcpy(oldbuf,a[i]);
mark[0]=1;
while(count<len) {
if(i<len/2)
pos=(2*i+1)%len-1;
else
pos=(2*i)%len+1;
strcpy(newbuf,a[pos]);
strcpy(a[pos],oldbuf);
mark[i]=1;
tmp=oldbuf;
oldbuf=newbuf;
newbuf=tmp;
i=pos;
if(mark[i]==1) {
for(j=0;j<len;j++)
if(mark[j]==0)
break;
i=j;
strcpy(oldbuf,a[i]);
}
++count;
}
printArray(a,len);
}

int main(void) {
//puts("!!!Hello World!!!"); /* prints !!!Hello World!!! */
//int a[]={1,2,3,3};
//permutation(a,4,0);
char a[10][5];//={"a0","a1","a2","a3","a4","b0","b1","b2","b3","b4"};
int i,pos;
for(i=0;i<5;i++) {
sprintf(a[i],"a%d",i);
}
for(i=0;i<5;i++) {
sprintf(a[i+5],"b%d",i);
}
int len=10;
for(i=0;i<len;i++) {
if(i<len/2)
pos=(2*i+1)%len-1;
else
pos=(2*i)%len+1;
printf("%d ",pos);
}
printf("\n");
shuttleArray(a,10);
return EXIT_SUCCESS;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

for(i=1,j=n ; j<2n||i<2n; i+=2,j++)
{
temp = arr[j];
for(k=j;k>=i;k--)
arr[k]=arr[k-1];
arr[i] = temp;
}

Comment hidden because of low score. Click to expand.
0

Not sure about its correctness, but its not efficient for sure. Second for loop could be minimised!

Comment hidden because of low score. Click to expand.
0
of 0 vote

void printArray(char a[][5],int len) {
int i;
for(i=0;i<len;i++) {
printf("%s ",a[i]);
}
printf("\n");
}

void shuttleArray(char a[][5],int len) {
printArray(a,len);
int count=1; int i; int pos=0;
char *newbuf=(char *)malloc(5);
char *oldbuf=(char *)malloc(5); char *tmp;
i=len/2;
strcpy(oldbuf,a[i]);
while(count<len) {
if(i<len/2)
pos=(2*i+1)%len-1;
else
pos=(2*i)%len+1;
strcpy(newbuf,a[pos]);
strcpy(a[pos],oldbuf);
tmp=oldbuf;
oldbuf=newbuf;
newbuf=tmp;
i=pos;
++count;
}
printArray(a,len);
}

Comment hidden because of low score. Click to expand.
0

Extra array cannot be used

Comment hidden because of low score. Click to expand.
0
of 0 vote

void cyclicswap(int *arr1, int *arr2)
{
int n = arr2-arr1;
int temp = *arr2;
while(arr2!=arr1)
{
*arr2 = *(arr2-1);
arr2--;
}
*arr1 = temp;;
}

void rearrange(int *arr,int n)
{
if (n==2)
return;
swap(arr+1, arr+(n/2));
cyclicswap(arr+2,arr+(n/2));
rearrange(arr+2,n-2);
}

main()
{

rearrange(arr,sizeof(arr)/sizeof(arr[0]));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

the index i is from 1 to 2n.
if i <= n,
j=2*i-1, //the final place
else
j=2*(i-n)

use a loop from 2 to n-1 to put each element into the final place.

void rearrange(int *a, int n)
{
for(int i = 1; i < 2*n; ++i)
{

}
}

Comment hidden because of low score. Click to expand.
0

You are too smart dude! Surprise such talent on career cup :-OOOOOOOOO

Comment hidden because of low score. Click to expand.
0

I guess it should be:
(Taking total array size as n)
if(i<n/2)
j=2*i;
else
j=n+1-2*(n-i);

Apart from that above algorithm will require O(n) space where requirement is to solve it without space.

Already lots of discussion went on this at:
careercup.com/question?id=7528760

Comment hidden because of low score. Click to expand.
0
of 0 vote

+23 int chars_left = n/2;
+24 for(int position = 1; chars_left != 1; chars_left--,position = position+2)
+25 {
+26 for(int i = n - chars_left; i > position; i--)
+27 {
+28 int temp = c[i];
+29 c[i] = c[i-1];
+30 c[i-1] = temp;
+31 }
+32 }

Comment hidden because of low score. Click to expand.
0

sorry in my case when i define 'n' I mean 2N
here is an example for first iteration of main loop

1 2 3 4 5 a b c d e position = 1;
1 2 3 4 a 5 b c d e
1 2 3 a 4 5 b c d e
1 2 a 3 4 5 b c d e
1 a 2 3 4 5 b c d e

Comment hidden because of low score. Click to expand.
0

number of swaps: ((n-1)*(n-2)-1)/2
complexity = O(n*n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

If N is power of 2, swap the second half of a[i] with the first half of b[i] with O(N/2) operations.
Then recursively do rearrange of the first N elements and the second N elements.
If N is not power of 2, some spacial handling is needed to decide how many elements to swap each time. But it does not change the complexity.
The overall complexity is O(NlgN).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ch.v.Suresh:

Under line high lighted are shift elements.

One shift:

a1 a2 a3 a4 a5 a6 a7 a8 ---> Even postions
-- -- -- --
b1 b2 b3 b4 b5 b6 b7 b8 ---> Odd positions
-- -- -- --

Two shift:

a1 b1 a3 b3 a5 b5 a7 b7
----- -----
a2 b2 a4 b4 a6 b6 a8 b8
----- -----

Four shift:

a1 b1 a2 b2 a5 b5 a6 b6
-----------
a3 b3 a4 b4 a7 b7 a8 b8
-----------

Result:

a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ch.v.Suresh:

Under line high lighted are shift elements.

One shift:

a1 a2 a3 a4 a5 a6 a7 a8 ---> Even positions a2,a4,a6,a8
-- -- -- --
b1 b2 b3 b4 b5 b6 b7 b8 ---> Odd positions b1,b3,b5,b7
-- -- -- --

Two shift:

a1 b1 a3 b3 a5 b5 a7 b7 --> Even positions (a3,b3) , (a7,b7)
----- ----- --> Odd positions (a2,b2) , (a6,b6)
a2 b2 a4 b4 a6 b6 a8 b8
----- -----

Four shift:

a1 b1 a2 b2 a5 b5 a6 b6 --> Shift (a5,b5,a6,b6) with (a3,b3,a4,b4)
-----------
a3 b3 a4 b4 a7 b7 a8 b8
-----------

Result:

a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8

Comment hidden because of low score. Click to expand.
0

complexity not better than O(n*n). why not just move each element which has the same compelxity

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
/*a1b1a2b2a3b3*/
void set(char a[],int m1,int m2);
int main()
{
char a[7]={'a','c','e','b','d','f','\0'};
int m1,m2,len,i;
len=strlen(a);
m1=(len-1)/2;
m2=m1+1;
set(a,m1,m2);
for(i=0;i<len;i++){
printf("%c",a[i]);}
getchar();
getchar();
return 0;
}
void set(char a[],int m1,int m2)
{
int len;
char t;
len=strlen(a);
t=a[m1];
a[m1]=a[m2];
a[m2]=t;
while(m1>1 && (m2<(len-1)))
{
t=a[m1];
a[m1]=a[m1-1];
a[m1-1]=t;
t=a[m2];
a[m2]=a[m2+1];
a[m2+1]=t;
--m1;++m2;
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
/*a1b1a2b2a3b3*/
void set(char a[],int m1,int m2);
int main()
{
char a[7]={'a','c','e','b','d','f','\0'};
int m1,m2,len,i;
len=strlen(a);
m1=(len-1)/2;
m2=m1+1;
set(a,m1,m2);
for(i=0;i<len;i++){
printf("%c",a[i]);}
getchar();
getchar();
return 0;
}
void set(char a[],int m1,int m2)
{
int len;
char t;
len=strlen(a);
t=a[m1];
a[m1]=a[m2];
a[m2]=t;
while(m1>1 && (m2<(len-1)))
{
t=a[m1];
a[m1]=a[m1-1];
a[m1-1]=t;
t=a[m2];
a[m2]=a[m2+1];
a[m2+1]=t;
--m1;++m2;
}}

Comment hidden because of low score. Click to expand.
0

@Nascent_coder: post ur logic/pseudo code please.
and use 3 open braces before code and 3 closed braces after the code to keep it formatted

Comment hidden because of low score. Click to expand.
0

``````void change(int*arr, int index, int size){
if(index>=size)	return;
else{
int temp,pos;
if((index+1)%2 == 1){
temp = arr[index/2];

}else{
temp = arr[size/2 + (index+1)/2-1];

}
cout << temp <<" ";
pos= index;
index++;
change(arr,index,size);
arr[--index] = temp;

}

}``````

I think calling it recursively should solve it in o(n) with the space being used is the cpu stack

Comment hidden because of low score. Click to expand.
0

apparently, you didn't run your code!!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

input: "0123456789"
output: "0516273849"

``````char str[] = "0123456789"
CALL:
EvenMix(str,0,strlen(str)-1,strlen(str))

void EvenMix(char *str, int start, int end, int len)
{
if(len <= 2) return;
else{
swap(str,start,end,len);
EvenMix(str, start, ((len>>2)-1), len>>2);
EvenMix(str, start, len>>2, len-1, len>>2);

}

}

void swap(char *str, int start, int end, int len)
{
int x = len>>2
int p = (start + x)>>2;
int q = (x + end)>>2;

while(x <= q)
{
char temp = *(str + start + p);
*(str + start + p) = *(str + start + x);
*(str + start + x); = temp
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

void ArrangeIntegers(int[] numbers)
{
if (numbers != null && numbers.Length > 3)
{
int n = numbers.Length;
int ps = 1;
int pe = (n / 2) - 1;
int qs = (n / 2);
int qe = n - 2;
Queue<int> numque = new Queue<int>();
numque.Enqueue(numbers[ps]);
numque.Enqueue(numbers[qe]);
bool fAlt = true;

while (ps < qe)
{
if (fAlt == true)
{
int t1 = numbers[ps];
numbers[ps] = numbers[qs];
numbers[qe] = (ps == pe)? t1 : numbers[pe];
fAlt = false;
pe--;
qs++;
}
else
{
numque.Enqueue(numbers[ps]);
numque.Enqueue(numbers[qe]);
numbers[ps] = numque.Dequeue();
numbers[qe] = numque.Dequeue();
fAlt = true;
}
ps++;
qe--;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

ArrangeIntegers function can also written as generic function to handle the different type of data types. This is function has O(log n) time complexity.

One additional check I missed was to check (numbers.Length % 2 == 0) just to make sure 2n condition holds.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a O(n) method with O(1) space.
Since every element is not in its final position except first and last element, we can randomly pick one element at first, for example the second one(a2), record its posision(currentIndex) and do the following loop until a2 in its final position(currentIndex==2):
1. calculate which element should be in this currentIndex position
if currentIndex is even number, the element should be in this position is a1...an. We use currentIndex/2 to calculate the current position of this element(index)
if currentIndex is odd numver, the element should be in this position is b1...bn. we use (currentIndex-1)/2+n
2. swap arr[currentIndex] and arr[index].
3. record the current position of a2(currentIndex).

``````void DoChangeElement(int currentIndex, int * arr, int length)
{
if (length&1)
{
cout<<"Length must be even and big than 0."<<endl;
return;
}
if(length==1) return;
//loop until a2 is in its right position
while(currentIndex!=2)
{
//calculate the right element for this currentIndex
int index=0;
if(currentIndex&1) index=(currentIndex-1)/2+(length/2);
else index=currentIndex/2;

swap(arr[currentIndex],arr[index]);
currentIndex=index;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

//arr = {a1,a2,a3,...,an,b1,b2,b3...,bn}
//array index starts from 0 and goes to arr.length - 1

public static void main(String[] args) {
int i;
int [] arr = {11,12,13,14,15,16,17,1,2,3,4,5,6,7};
//int [] arr = {1,2,3,4,5,6,7,11,12,13,14,15,16,17};
boolean isOdd = (((arr.length /2) % 2) != 0)? true:false;

printArr(arr);
//First Loop
for (i = 1; i < (arr.length /2); i+=2) {
swap(arr,i,(arr.length /2) + i - 1);
}
printArr(arr);
//Second Loop
if(isOdd){
for (i = (arr.length/2)-1; i < arr.length-2; i++) {
swap(arr,i,i+1);
}
}
printArr(arr);
final int N = isOdd? (arr.length-2)/2:arr.length/2;
int itr = N;
int x=0;
for (i = 2; i <2*N && itr < 2*N; i+=2)
{
if(arr[i]> arr[itr])
{
if(i<itr) {
swap(arr,i,itr);
swap(arr,i+1, itr+1);
x++;
if(x==2)
{
itr+=2;
x=0;
}
}
}
else{
if(i>itr) {
swap(arr,i,itr);
swap(arr,i+1, itr+1);
}
}
}
printArr(arr);
}

static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
static void printArr(int []arr){
for(int i = 0; i < (arr.length);i++){
System.out.print(arr[i]);
if (i!=arr.length-1)
System.out.print(",");
}
System.out.println();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

//----------------REFORMATTED ABOVE-----------------------
//arr = {a1,a2,a3,...,an,b1,b2,b3...,bn}
//array index starts from 0 and goes to arr.length - 1

public static void main(String[] args) {
int i;
// int [] arr = {1,2,3,4,5,6,7,11,12,13,14,15,16,17};
int [] arr = {11,12,13,14,15,16,17,18,1,2,3,4,5,6,7,8};
boolean isOdd = (((arr.length /2) % 2) != 0)? true:false;

printArr(arr);
//First Loop
for (i = 1; i < (arr.length /2); i+=2) {
swap(arr,i,(arr.length /2) + i - 1);
}
printArr(arr);
//Second Loop
if(isOdd){
for (i = (arr.length/2)-1; i < arr.length-2; i++) {
swap(arr,i,i+1);
}
}
printArr(arr);
final int N = isOdd? (arr.length-2)/2:arr.length/2;
int itr = N;
int x=0;
for (i = 2; i <2*N && itr < 2*N; i+=2)
{
if(arr[i]> arr[itr])
{
if(i<itr) {
swap(arr,i,itr);
swap(arr,i+1, itr+1);
x++;
if(x==2)
{
itr+=2;
x=0;
}
}
}
else{
if(i>itr) {
swap(arr,i,itr);
swap(arr,i+1, itr+1);
}
}
}
printArr(arr);
}

static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
static void printArr(int []arr){
for(int i = 0; i < (arr.length);i++){
System.out.print(arr[i]);
if (i!=arr.length-1)
System.out.print(",");
}
System.out.println();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ //arr = {a1,a2,a3,...,an,b1,b2,b3...,bn} //array index starts from 0 and goes to arr.length - 1
Comment hidden because of low score. Click to expand.
0
of 0 vote

ideone.com/P5aiI

Comment hidden because of low score. Click to expand.
0

Good!! but still it's O(n*n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[10]={0,1,2,3,4,5,6,7,8,9};
int i,j;
int temp;
for(i=1, j=5;i<10;i+=2,j++)
{
temp=a[j];
for(int k=j-1;k>=i;k--)
a[k+1]=a[k];
a[i]=temp;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int a[10]={0,1,2,3,4,5,6,7,8,9};
int i,j;
int temp;
for(i=1, j=5;i<10;i+=2,j++)
{
temp=a[j];
for(int k=j-1;k>=i;k--)
a[k+1]=a[k];
a[i]=temp;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<algorithm>

using namespace std;

void rearrange(int a[],int n,int pos)
{
if(pos == n/2) { for (int i=0;i<n;i++) cout<<a[i]; return; }
int k=0;
for(int i=pos;i<n/2;i++)
{
swap(a[i],a[k++ +(n/2)]);
}
rearrange(a,n,pos+1);
}
int main()
{
int a[]={1,3,5,7,2,4,6,8};

rearrange(a,8,1);
cin.get();
cin.ignore();
return 1;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void Rearrange(int a[],int n)
{
int i,j;
for(i=0 ; i < (n/2)-1; i++)
{
int k=0;
for(j=0; j<=i; j++)
{
//calculating postion of elements need to be swapped
int pos1 = (n/2)-(i+1)+k;
int pos2 = (n/2)-(i)+k;
//Swapping
int temp = a[pos1];
a[pos1] = a[pos2];
a[pos2] = temp;
k=k+2;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

actually first for loop is from i = 0 to i <(n/2) instead of (n/2)-1

Comment hidden because of low score. Click to expand.
0
of 0 vote

we will use a function which will take three parameter :
1.[Array](char []a)
2.[index Which need to move in rite position] (int i)
3.[value to place at new position](char c)

we will initiate function as :
a=arrangeArray(a,1,a[n]);
This function is responsible for move index i value to the deserving place.It also copy the value of new place and call another function to place this value to its deserving place.when all places will be arrange i will become 'n' and the recursion will stop.

the function is:

``````char[] arrangeArray(char[]a,int i,char c)
{

int j;
char temp;

if(i<(n-1))
{
j=2*i;
}

else
{
j=2*(i-n)+1;
}
if(j!=n)
{
temp=a[j];
a[j]=c;
a=arrangeArray(a,j,temp);
}
return a;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,

I got the O(n) solution of this problem:

#include<stdio.h>
int main()
{

int n,t,i,j,t1;
int arr[100];

//n: number of elements in array.
//
scanf("%d",&n);

for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
int p,distance,count;
int ni; //new index
count=0;

for (i=1,ni=1;i<n&&count<n-2;count++)
{
//First find the distance
//based on if number is in first half or second half
//based on distance find the new index of this number.
//
if(ni<n/2){
distance=ni;
p=2*distance;
}
else{
distance=ni-n/2+1;
p=2*distance-1;
}

//swap arr[i] with arr[p].
//
t=arr[p]; arr[p]=arr[i]; arr[i]=t;

if (i==p){
i=i+2;
ni=i;
}
else
ni=p;
}

printf ("The output array is:\n");
for (i=0;i<n;i++)
{
printf ("%d ", arr[i]);
}

return 0;

}

Logic is:
Fix i on 1. Find the new index of this number. swap arr[1] with this new index. Record this new index in ni and this number is on 1. Now find the new index based on ni. and swap arr[1] with this new index. Keep doing this till you have swapped n-2 elements.

Just one trick, after some iterations correct element will come to a[1] then increment index by 2[I don't how did it work, it was just based on example of 10 element array and now I tested it works for any number of elements].

Comment hidden because of low score. Click to expand.
0
of 0 vote

this looks to me as a very simple question, why the solutions are so long??

bool reorder(int *array,int n)
{
if(array && n)
{
for(int i=n;i<2*n;++i)
{
int temp=array[i];

for(int e=i;e>(i-n)*2+1;--e)
{
array[e]=array[e-1];
}

array[(i-n)*2+1]=temp;
}

return true;
}

return false;
}

int main(int argc, char *argv[])
{

int array[]={1,2,3,4,5,6,7,8,9,0};
int n=5;

for(int i=0;i<2*n;++i)
printf("%d,",array[i]);
printf("\n");

reorder(array,5);

for(int i=0;i<2*n;++i)
printf("%d,",array[i]);
printf("\n");
}

test input:
1,2,3,4,5,6,7,8,9,0,
test output:
1,6,2,7,3,8,4,9,5,0,

Comment hidden because of low score. Click to expand.
0
of 0 vote

@above what is the run time of your code?
it should be O(n). Your code is not O(n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

1.create two heaps a1----an,b1----bn by index of element
2.Now delete the root of each and insert it at starting
3.repeat the 1st step again till end

Comment hidden because of low score. Click to expand.
0
of 0 vote

complexity will be (nlogn) i think

Comment hidden because of low score. Click to expand.
0
of 0 vote

Easy to understand code which runs in O(n^2) time

``````#include<stdio.h>
void swap(int *x,int *y);
int main()
{
int a[]={1,2,3,4,5,1,2,3,4,5};
int i,j,k;
int count =1,noswappings=0;
for(i=4;i>=1;i--)
{
for(j=i,k=0;k<count;k++,j+=2)
{
swap(&a[j],&a[j+1]);
noswappings++;
}

count++;
}
for( i = 0;i<10;i++)
printf("%d ",a[i]);

printf("\nNo of swappings:%d",noswappings);
getch();
return 0;
}
void swap(int *x,int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Here is one recursive solution I propose :

consider example a1,a2,a3,a4,b1,b2,b3,b4

1. if n is even
swap second Half of first array with first half of second array
so it would be a1,a2,b1,b2,a3,a4,b3,b4
and it  can be solved recursively
so rearrange({a1,a2,a3,a4,b1,b2,b3,b4}) = rearrange({a1,a2,b1,b2}), rearrange({a3,a4,b3,b4});
2. if n is odd (a1,a2,a3,a4,a5,b1,b2,b3,b4,b5)
swap second Half+1 of first array with first half+1 of second array
so it would be a1,a2,b1,b2,b3,a3,a4,a5,b4,b5
swap bolded elements( nth and n+1 th) a1,a2,b1,b2,a3,b3,a4,a5,b4,b5
and it  can be solved recursively by dividing in two sub parts
rearrange({a1,a2,a3,a4,a5,b1,b2,b3,b4,b5}) = swap(b3,a3), rearrange({a1,a2,b1,b2}), rearrange({a4,a5,b4,b5});

limiting case would be
if n==2 //since the pair is in required order
return;

Time complexity analysis ( n is size of total array a+b):

T(n) = 2*T(n/2) + n/4   ( n/4 is swapping time of second Half of first array with first half of second array)

T(n) = 2^k T(1) + n/4( 1+1/2+1/4+.......+1/(2^k))
= 2^k+n/4( 1-1/(2^k))*2                k = log(n)
=n+ (n-1)/2
=O(n)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This will work if element are of int/char/float types

#define SWAP(X,Y) (X=X^Y;Y=X^Y;X=X^Y;)

arrayChange(int a[]){
int size = sizeof(a)/sizoof(a[0]);
int i = 0;
while(i < size/2){
SWAP(a[i++], a[size-- - 1]);
}
}
size--;
}
}

Comment hidden because of low score. Click to expand.
0

pls ignore the above post... its totally wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<iostream>
using namespace std;
int main(int argc, char*argv[])
{
int a[] = {1,2,3,4,5,6,11,22,33,44,55,66};
int n = 6;
int temp1 = 0;
int temp2 = 0;
int changed = 2;
for(int i =1;(i<n)&&(changed!=2*n);i=i+2)
{
int start = i;
int oldIndex = i;
int newIndex = 0;
temp1 = a[oldIndex];
while(start!=newIndex)
{
if(oldIndex>=n)
{
newIndex = 2*(oldIndex-n)+1;
}
else
{
newIndex = 2*oldIndex;
}

temp2 = a[newIndex];
a[newIndex] = temp1;
changed++;
temp1 = temp2;
oldIndex = newIndex;
}
//a[start] = temp1;
}
for(int i=0;i<2*n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package arrays;

public class Exchange {
public static void exchange(int[] a){
exchange(a, (a.length/2) - 1, a.length/2);
}

private static void exchange(int[] a,int x,int y){
if(x==0 || y==a.length-1){
return;
}

for(int i=x;i<=y;i=i+2){
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
exchange(a, x-1, y+1);
}

public static void main(String[] args){
int[] a = {1,2,3,4,5,6,7,8,9,10};
exchange(a);
for(int i : a){
System.out.print(i + " ");
}
}
}``````

Output: 1 6 2 7 3 8 4 9 5 10

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package arrays;

public class Exchange {
public static void exchange(int[] a){
exchange(a, (a.length/2) - 1, a.length/2);
}

private static void exchange(int[] a,int x,int y){
if(x==0 || y==a.length-1){
return;
}

for(int i=x;i<=y;i=i+2){
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
exchange(a, x-1, y+1);
}

public static void main(String[] args){
int[] a = {1,2,3,4,5,6,7,8,9,10};
exchange(a);
for(int i : a){
System.out.print(i + " ");
}
}
}``````

Output: 1 6 2 7 3 8 4 9 5 10

Comment hidden because of low score. Click to expand.
0

good solution

Comment hidden because of low score. Click to expand.
0

@gopal..your Solution is Excepetionally Well man,,,but can provide whats the time comlaxity of ur solution .plz try to write the recursive relation e.g T(n)=aT(n/b)+c(n)

Comment hidden because of low score. Click to expand.
0

@gopal..your Solution is Excepetionally Well man,,,but can provide whats the time comlaxity of ur solution .plz try to write the recursive relation e.g T(n)=aT(n/b)+c(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

//given an array [a1,a2,a3...,an,b1,b2...bn], change it to [a1,b1,a2,b2.....an,bn], solution should be in-place
public static void exchange(int[] array, int n) {
int y = array.length - 1;
for (int x = n - 1; x >= 0; x--, y -= 2) {
int temp = array[x];
int j;
for (j = x + 1; j < y; j++) {
array[j - 1] = array[j];
}
array[j - 1] = temp;
}
}

Comment hidden because of low score. Click to expand.
0

I couldn't see it working. Pls test for input {1 2 a b}

Comment hidden because of low score. Click to expand.
0

I couldn't see it working. Pls test for input {1 2 a b}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Put all the a0 to an in two queues
Now remove alternately from queue1 and queue1 and place it in the original array.

Comment hidden because of low score. Click to expand.
0

uncle plz read the q. it says inplace. ;)

Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey51925" class="run-this">#include "stdafx.h"

int func(int index,int len)
{
if(index<len/2)
return 2*index;
else
return (2*index-len+1);
}
int main()
{
int a[]={1,2,3,4,5,6,7,8,9,10,11,12};
int count =0,hold=a[1],temp,index=1;
int length = 12;
while(count<(length-2))
{
temp = hold;
hold = a[func(index,length)];
a[func(index,length)] = temp;
index = func(index,length);
count++;
if(index == 1)
{
//temp = hold;
//hold = a[func(index,length)];
//a[func(index,length)] = temp;
index +=(length-count-2);
hold = a[index];
//count++;
}

}
for(index=0;index<length;index++)
printf("%d\t",a[index]);

return 0;
}

</pre><pre title="CodeMonkey51925" input="yes">
</pre>

Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey39796" class="run-this">class TestNumber {

public static void main(String[] args) {
String[] strAr = {"a1","a2","a3","a4","a5","b1","b2","b3","b4","b5"};
String[] sortAr = new String[strAr.length];
int j =0;
int k=strAr.length/2;
int m=0;
for(int i=0;i<strAr.length;i++){
if(i%2 == 0){
sortAr[j++]=strAr[m++];
}else{
sortAr[j++]=strAr[k++];
}
}

for(String str: sortAr){
System.out.println(str);
}
}
}

</pre>

Comment hidden because of low score. Click to expand.
0

Output for above code:

a1
b1
a2
b2
a3
b3
a4
b4
a5
b5

Comment hidden because of low score. Click to expand.
0

FCuK man.. is this inplace?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>

using namespace std;

char str[100] ;
int l ;
int global ;

void func(int idx , char ch1 ,char ch2)
{
if(idx == l/2)
return ;
ch1 = str[idx] ;
ch2 = str[idx + l/2] ;
func(idx + 1 , ch1 , ch2);
str[global] = ch2 ;
str[global -1] = ch1 ;
global -= 2 ;
return ;
}

int main()
{
scanf("%s",str);
l = strlen(str);
global = l - 1;

func(0,'\0','\0');

printf("%s\n",str);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my implementation with O(n) in time & space

``````#include <string.h>
#include <iostream>
using namespace std;
void exchange(int * a, int n) {
int start =1;
int tmp;
int i,j;
char done[n];
memset ( done, 0, n);
while ( start < n/2)
{ tmp = a[start];
i = start;
while (1)
{
if ( i%2 )
j = ( n + i - 1 ) / 2;
else
j = i / 2;
if ( j == start )
break;
a[i] = a[j];
done[i] = 1;
i = j;
}
a[i] = tmp;
done[i] = 1;
while ( done[start] && start < n/2)
++start;
}
}
int main()
{
int a[2000];
int N;
cout << "Enter N" << endl;
cin >> N;
cout << "Enter the elements"<< endl;
for ( int i = 0 ; i < N ; i++ )
cin >> a[i];
exchange ( a, N );
for ( int i = 0 ; i < N ; i++)
cout << a[i] << " ";
cout << endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my implementation with O(n) in time & space

``````#include <string.h>
#include <iostream>
using namespace std;
void exchange(int * a, int n) {
int start =1;
int tmp;
int i,j;
char done[n];
memset ( done, 0, n);
while ( start < n/2)
{ tmp = a[start];
i = start;
while (1)
{
if ( i%2 )
j = ( n + i - 1 ) / 2;
else
j = i / 2;
if ( j == start )
break;
a[i] = a[j];
done[i] = 1;
i = j;
}
a[i] = tmp;
done[i] = 1;
while ( done[start] && start < n/2)
++start;
}
}
int main()
{
int a[2000];
int N;
cout << "Enter N" << endl;
cin >> N;
cout << "Enter the elements"<< endl;
for ( int i = 0 ; i < N ; i++ )
cin >> a[i];
exchange ( a, N );
for ( int i = 0 ; i < N ; i++)
cout << a[i] << " ";
cout << endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my implementation with O(n) in time & space

``````#include <string.h>
#include <iostream>
using namespace std;
void exchange(int * a, int n) {
int start =1;
int tmp;
int i,j;
char done[n];
memset ( done, 0, n);
while ( start < n/2)
{ tmp = a[start];
i = start;
while (1)
{
if ( i%2 )
j = ( n + i - 1 ) / 2;
else
j = i / 2;
if ( j == start )
break;
a[i] = a[j];
done[i] = 1;
i = j;
}
a[i] = tmp;
done[i] = 1;
while ( done[start] && start < n/2)
++start;
}
}
int main()
{
int a[2000];
int N;
cout << "Enter N" << endl;
cin >> N;
cout << "Enter the elements"<< endl;
for ( int i = 0 ; i < N ; i++ )
cin >> a[i];
exchange ( a, N );
for ( int i = 0 ; i < N ; i++)
cout << a[i] << " ";
cout << endl;
}``````

Comment hidden because of low score. Click to expand.
0

It said "Error posting your comment" each time I tried but it actually posted it.. Please ignore the duplicate posts. Admin : I hope you delete them soon.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Meh, O(n^2).

``````#include <vector>
#include <iostream>

std::vector<int> &uninterleave(std::vector<int> &vec) {
int n = vec.size() / 2;
for (int i = 0; i < n-1; ++i) {
int start = (vec.size() - 2*i - 1) / 2;
int end   = (vec.size() + 2*i) / 2;

for (int j = start; j < end; j += 2) {
int temp = vec[j];
vec[j] = vec[j+1];
vec[j+1] = temp;
}
}

return vec;
}

int main() {
std::vector<int> vec{0, 1, 2, 3, 0, 1, 2, 3};

for (auto it : vec) {
std::cout << it << " ";
}
std::cout << std::endl;

uninterleave(vec);

for (auto it : vec) {
std::cout << it << " ";
}
std::cout << std::endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.aa.array;

public class SortedOutPut {

/**
* @param args
*/
public static void main(String[] args) {
String a [] = new String[] {"a1","a2","a3","a4","a5","a6","b1","b2","b3","b4","b5","b6"};

int n= a.length;
int j =n/2;
for(int i=0 ; i < n ; i+=2){
String tmp= a[j];
shift(a,i+1,(j));
a[i+1]=tmp;
j++;
}
for(int i=0 ; i < n ; i++){
System.out.println(a[i]);
}
}

private static void shift(String[] a, int i, int j) {
for(int k = j ; k >=i ; k-- ){
a[k]=a[k-1];
}

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

a very simple method. o(n) time and o(1) space.
assume the array
1. scan through n,n+1,...,2*n to move each bi to the right position.
2. scan through 1,3,5,7,...,2*n-1 to move each ai to the right position.
step 1 or 2 need swap n elements, total time o(n)

CODE:
void cross_swap(vector<string> &a){
if(a.size()<=0)
return;
assert(a.size()%2==0);
int n=a.size()/2;
int ind=-1;
for(int i=0;i<n;i++){
ind+=2;
swap(a[ind],a[i+n]);
}
int i=0;
char buf[10];
int count=1;
while(i!=a.size()-2){
string tmp=a[i];
tmp=tmp.substr(1);
int num=atoi(tmp.c_str());
if(num!=count)
swap(a[i],a[2*(num-1)]);
else
i+=2,count++;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

void do_this(int a[], int n)
if (n==0) return ;
for (int i=n; i >=2; i--)
swap(a[i], a[i-1]);
do_this(a+2, n-1);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int* algo(int *a,int size)
{
int n=size/2;
int j=n+1;
int i=2;
int temp=0;
int temp2=0;
while(i<2*n)
{
temp=j-i;
temp2=j;
while(temp !=0)
{
swap(a,temp2,temp2-1);
temp2--;
temp--;
}
j++;
i=i+2;
}
retur``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

s = array.length / 2;
for( int i =1; i < s; i++)
swap( array[i], array[n+i-1] )

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Arrays;

public class FindSingleDuplicate {

public static void main(String[] args) {

int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

System.out.println("Before shifting the elements::" +Arrays.toString(arr));
arr = sort(arr);
System.out.println("After shifting the elements::"+Arrays.toString(arr));
}

private static int[] sort(int[] arr) {

int mid = (arr.length-1)/2;
for(int i=1;i<=mid;i++)
{
int count = 1;

for(int j = -(i-1);count <= i; count++)
{
arr = swap(arr,(mid+j),(mid+j+1));
j+=2;
}

}
return arr;
}

private static int[] swap(int[] arr,int i, int j) {

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

return arr;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity for the above is O(n*n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this solution's time complexity O(n)?

``````public void swapElements(List<String> input) {

List<String> finalList = new ArrayList<String>();

List<String> firstList = input.subList(0, input.size() / 2);
Iterator<String> firstIterator = firstList.iterator();
List<String> secondList = input.subList(input.size() / 2, input.size());
Iterator<String> secondIterator = secondList.iterator();
String values = "";
String currentValue = "";

for(int i = 0; i < input.size(); i++) {
currentValue = i % 2 == 0 ? firstIterator.next().toString() : secondIterator.next().toString();
values += currentValue+" ";
}

System.out.println(values);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The first technique works fine:
Successively keep swapping pairs from the middle.

``````void arrangeArray(int *a){
int num_swaps = 1; //number of swaps to be done
int i = 0;
int mid=0;
int swap_start_idx = 0;
int swap_end_idx = 0;
int temp=0;

//find lenght of array
while(a[i] != '\0'){
i++;
}
mid = i/2 -1;
cout << "mid: " << mid << endl;
i=0;
while(a[i] != '\0'){
cout << a[i] << endl;
i++;
}

while(mid -num_swaps +1 > 0){
swap_start_idx = mid-num_swaps+1;
swap_end_idx = mid+num_swaps;
//cout << "num_swaps: " << num_swaps << " swap_start_idx " << swap_start_idx << "  swap_end_idx "<< swap_end_idx << endl;
while(swap_end_idx > swap_start_idx){
temp=a[swap_start_idx];
a[swap_start_idx]=a[swap_start_idx+1];
a[swap_start_idx+1] = temp;
//cout << "a[swap_start_idx]: " <<  a[swap_start_idx] << "  a[swap_end_idx]: " << a[swap_end_idx] << endl;
swap_start_idx += 2;
}
num_swaps++;
//cout << "num_swaps" << num_swaps << endl;
}
return;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The first technique works fine:
Successively keep swapping pairs from the middle.

``````void arrangeArray(int *a){
int num_swaps = 1; //number of swaps to be done
int i = 0;
int mid=0;
int swap_start_idx = 0;
int swap_end_idx = 0;
int temp=0;

//find lenght of array
while(a[i] != '\0'){
i++;
}
mid = i/2 -1;
cout << "mid: " << mid << endl;
i=0;
while(a[i] != '\0'){
cout << a[i] << endl;
i++;
}

while(mid -num_swaps +1 > 0){
swap_start_idx = mid-num_swaps+1;
swap_end_idx = mid+num_swaps;
//cout << "num_swaps: " << num_swaps << " swap_start_idx " << swap_start_idx << "  swap_end_idx "<< swap_end_idx << endl;
while(swap_end_idx > swap_start_idx){
temp=a[swap_start_idx];
a[swap_start_idx]=a[swap_start_idx+1];
a[swap_start_idx+1] = temp;
//cout << "a[swap_start_idx]: " <<  a[swap_start_idx] << "  a[swap_end_idx]: " << a[swap_end_idx] << endl;
swap_start_idx += 2;
}
num_swaps++;
//cout << "num_swaps" << num_swaps << endl;
}
return;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The first technique works fine:
Successively keep swapping pairs from the middle.

``````void arrangeArray(int *a){
int num_swaps = 1; //number of swaps to be done
int i = 0;
int mid=0;
int swap_start_idx = 0;
int swap_end_idx = 0;
int temp=0;

//find lenght of array
while(a[i] != '\0'){
i++;
}
mid = i/2 -1;
cout << "mid: " << mid << endl;
i=0;
while(a[i] != '\0'){
cout << a[i] << endl;
i++;
}

while(mid -num_swaps +1 > 0){
swap_start_idx = mid-num_swaps+1;
swap_end_idx = mid+num_swaps;
//cout << "num_swaps: " << num_swaps << " swap_start_idx " << swap_start_idx << "  swap_end_idx "<< swap_end_idx << endl;
while(swap_end_idx > swap_start_idx){
temp=a[swap_start_idx];
a[swap_start_idx]=a[swap_start_idx+1];
a[swap_start_idx+1] = temp;
//cout << "a[swap_start_idx]: " <<  a[swap_start_idx] << "  a[swap_end_idx]: " << a[swap_end_idx] << endl;
swap_start_idx += 2;
}
num_swaps++;
//cout << "num_swaps" << num_swaps << endl;
}
return;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

But a better O(n) solution is that
new idx = (old idx * 2)/(num_elements - 1)

//working C++ code

``````void arrangeArrayVer2(int *a){
int i = 1;
int len = 0;
int swap_pos = 0;
while(a[len] != '\0'){
len++;
}
cout << "length: " << len << endl;
if(len <= 2){
cout << "length too small, no need to rearrange" << endl;
}

int b[len];
i = 0;
b[0] = a[0];
b[len-1] = a[len-1];
while(i < len - 1){
//ith element, new pos = 2*i/len-1;
swap_pos = (2*i)%(len-1);
cout << "i: " << i << " swap_pos: " << swap_pos << endl;
b[swap_pos] = a[i];
i++;
}
cout << "original array:" << endl;
i=0;
while(a[i] != '\0'){
cout << a[i] << endl;
i++;
}

cout << "rearranged array:" << endl;
i=0;
while(b[i] != '\0'){
cout << b[i] << endl;
i++;
}
return;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Good!

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void interSwap(){
String[] array = {"a1","a2","a3", "a4", "a5", "b1", "b2", "b3","b4","b5"};

for(int i=0; i<array.length/2-1; i++) {
int m = array.length/2 - i;
for(int j=0; j<i+1; j++) {
String temp = array[m];
array[m] = array[m-1];
array[m-1] = temp;
m = m+2;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Implementation and Test code.
This one is O(n) complexity,

``````#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

class testInput
{
public:
testInput(int n)
{
count = n;
input.resize(2*n);

for(int i = 0; i<n; i++)
{
input[i]	= i*2;
input[i+n]	= (i*2+1);
}
cout<<"input:"<<endl;

for(int i = 0; i<n; i++)
{
cout<<input[2*i]<<" "<<input[2*i+1]<<" ";
}
cout<<endl;
for(int i = 1; i<2*n-1; i++)
{
input[i] *= -1;
}
cout<<"result:"<<endl;
run();
cout<<endl;
}

int mapindex(int a,int n,int q)
{
int i = a/n;
int j = a%n;
return i + j*q;
}

void run()
{
for(int it = 0; it<count;it++)
{
int tmp = input[it];
if( tmp > 0)
continue;
int src = mapindex(it,2,count);
int dst = it;

while(src!=it)
{
input[dst] = -input[src];
dst = src;
src = mapindex(src,2,count);
}
input[dst] = -tmp;
}

for(int i = 0; i<count; i++)
{
cout<<input[2*i]<<" "<<input[2*i+1]<<" ";
}

cout<<endl;
}
int count;
vector<int> input;
};

int _tmain(int argc, _TCHAR* argv[])
{

testInput a(5);
testInput b(20);
testInput c(30);
testInput c(100);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the idea A1(A2'B1')'B2=A1B1A2B2
Do it recursively,time complexity will be O(nlogn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the idea A1(A2'B1')'B2=A1B1A2B2
Do it recursively,time complexity will be O(nlogn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static void rearrange(string[] s)
{
char[] str = s.ToCharArray();
int len = s.Length;
int[] v = new int[len];
len--;
v[0] = 0;
v[len] = len;
for(int i=0;i<len;i++)
v[i]=(i*2)%len;

int k=1;
int temp=v[k];
int count=0;
while(k<len)
{
if(k==temp)
{
k++;
temp=v[k];
}
else
{
Swap<char>(ref str[k],ref str[temp]);
Swap<int>(ref v[k],ref v[temp]);
temp=v[k];
}
}
}

static void Swap<T>(ref T lhs, ref T rhs)
{
T temp;
temp = lhs;
lhs = rhs;
rhs = temp;
}``````

here's one possible solution. I can't really claim but it runs in o(n) time. I have tried it for array size as big as 5000, n the loop always executed a little less than 2*N times.
The idea is to calculate the expected position of the array elements and store them. While swapping elements also swap the expected positions.

Comment hidden because of low score. Click to expand.
0

correction: It will be "rearrange(string s)" not rearrange(string []s).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void ReArrangeAlternte(int[] input)
{
int n = input.Length;
for (int i = 1; i < n / 2; i++)
{
int start = n / 2 - i;
int end = n / 2 + i;
for (int j = start; j < end; j += 2)
{
int tmp = input[j];
input[j] = input[j + 1];
input[j + 1] = tmp;
}
}
}``````

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.

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

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

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