Amazon Microsoft Interview Question Developer Program Engineers Software Engineer / Developers




Comment hidden because of low score. Click to expand.
15
of 19 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

- X on February 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
    }
  }
}

- jatin085 on February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bck on April 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bck on April 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice.

May I ask what is the logic behind it.

- Leon on April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Hei on May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

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

- devender on August 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

what about this O(n) time

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]+" ");
    }
}

- Ashish Gupta on January 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on March 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on March 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
4
of 6 vote

Anony and Adiser
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

- Sathya on February 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- GekkoGordan on February 07, 2011 | Flag
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

- Anon on February 08, 2011 | Flag
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)

- Sathya on February 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- chennavarri on February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

@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;
      }
   }
}

- Sathya on February 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey
Can anybody explain the algorithm for this...

- Anonymous on February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

awesome code :)

- XYZ on February 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- souravghosh.btbg on February 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 2 votes

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.

- Hei on May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}
}

- vikk on December 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about this one?

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;
}
}

- vikk on December 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sz2376@columbia.edu on November 19, 2013 | Flag
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

- Ashish on February 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aaptuster on February 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Code Saviour on February 14, 2011 | Flag
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..

- God on July 13, 2012 | Flag
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)

- coderBon on August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- kkaushi on August 04, 2014 | Flag
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.)

- Anonymous on February 14, 2011 | Flag Reply
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.

- Anurag Singh on February 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- XO on February 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
}

- Saimok on February 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anony on February 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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];
}
}
}
}

- Anurag Singh on February 06, 2011 | Flag
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;
		}
	}

- Code Saviour on February 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on February 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- blueskin.neo on February 05, 2011 | Flag
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.

- Code Saviour on February 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- blueskin.neo on February 06, 2011 | Flag
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);
}
}

- ninghsu267 on February 05, 2011 | Flag Reply
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.

- Anonymous on February 06, 2011 | Flag Reply
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?

- anony on February 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Adiser on February 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sundar on February 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sathya on February 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anurag Singh on February 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
	}
	
}

- Anony on February 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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];
}
}
}
}

- Anurag Singh on February 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Raj on March 01, 2011 | Flag
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)

- Anon on February 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not working for size = 18

- Anonymous on February 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- A on February 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on February 08, 2011 | Flag
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?

- Anony on February 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anurag Singh on February 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

yup that works :) cool soln. thx satya.

- anony on February 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

do somebody explain this.

- coolGuy on February 08, 2011 | Flag
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).

- buried.shopno on February 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- buried.shopno on February 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- my bad, was too sleepy .... on February 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- coolGuy on February 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anonymous on February 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- buried.shopno on February 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous on February 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- buried.shopno on February 13, 2011 | Flag
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)

- Steve on February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anonymous on February 10, 2011 | Flag
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;
}

- kartik on February 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Guess Who?? on February 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- abcd on February 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Nathan on February 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@karthik,
don't post some junk!!

- Anonymous on February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@kartik

fuck off

- Anonymous on June 28, 2012 | Flag
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;
}

- Ujjwal on February 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Anonymous on February 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

> Time O(n)

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

Nope, thank you for playing.

- Anonymous on February 15, 2011 | Flag
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++;
}

- aankur.bansal on February 14, 2011 | Flag Reply
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++;
}

- aankur.bansal on February 14, 2011 | Flag Reply
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++;
}

- aankur.bansal on February 14, 2011 | Flag Reply
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 ....

- aaptuster on February 14, 2011 | Flag Reply
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

- Ashish on February 14, 2011 | Flag Reply
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;
}

- huyun on February 14, 2011 | Flag Reply
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;
}

- harshaltalele on February 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aaptuster on February 14, 2011 | Flag
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);
}

- yun hu on February 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Extra array cannot be used

- aaptuster on February 14, 2011 | Flag
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]));
}

- Anurag on February 14, 2011 | Flag Reply
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)
{

}
}

- Anonymous on February 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- awesome answer.... HUH ! on February 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anurag Singh on February 14, 2011 | Flag
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 }

- Mat on February 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Mat on February 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Tom on February 14, 2011 | Flag
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).

- Anonymous on February 15, 2011 | Flag Reply
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

- Anonymous on February 15, 2011 | Flag Reply
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

- Anonymous on February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- GekkoGordan on February 15, 2011 | Flag
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;
}}

- Nascent_coder on February 15, 2011 | Flag Reply
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;
}}

- Nascent_coder on February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Troll on February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

please comment on this solution

- Kunal Galav on February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on February 16, 2011 | Flag
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
	}
}

- yogesh on February 16, 2011 | Flag Reply
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--;
}
}
}

- hsay on February 16, 2011 | Flag Reply
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.

- hsay on February 16, 2011 | Flag Reply
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;
	}

}

- gztyjz on February 16, 2011 | Flag Reply
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();
}

- Gowd on February 17, 2011 | Flag Reply
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();
}

- Gowd on February 17, 2011 | Flag Reply
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 - Gowd on February 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ideone.com/P5aiI

Please comment on this

- Kxx on February 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dreamer on May 01, 2011 | Flag
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;
}

- Karun on February 17, 2011 | Flag Reply
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;
	}

- Anonymous on February 17, 2011 | Flag Reply
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;
}

- Anonymous on February 17, 2011 | Flag Reply
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;
   }
 }
}

- RV on February 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- RV on February 18, 2011 | Flag
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;
}

- PKT on February 19, 2011 | Flag Reply
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].

- MKey on February 20, 2011 | Flag Reply
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,

- Anonymous on February 21, 2011 | Flag Reply
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).

- Anonymous on February 21, 2011 | Flag Reply
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

- sunny on February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

complexity will be (nlogn) i think

- sunny on February 22, 2011 | Flag Reply
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;
}

- Ravi on February 24, 2011 | Flag Reply
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)

- Gaurav Gupta on March 01, 2011 | Flag Reply
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--;
}
}

- viky on March 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

pls ignore the above post... its totally wrong

- Anonymous on March 01, 2011 | Flag
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");
}

- Anonymous on March 03, 2011 | Flag Reply
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

- Anonymous on March 10, 2011 | Flag Reply
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

- Gopal on March 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good solution

- gavinashg on March 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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)

Please reply i am sure its not O(n)..isn't it..??

- Algoseekar on April 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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)

Please reply i am sure its not O(n)..isn't it..??

- Algoseekar on April 27, 2011 | Flag
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;
}
}

- my husband's solution on March 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ravikant on January 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ravikant on January 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What do you think guys about this solutions.
Put all the a0 to an in two queues
Now remove alternately from queue1 and queue1 and place it in the original array.

- Anonymous on April 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on April 23, 2011 | Flag
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>

- Anonymous on June 17, 2011 | Flag Reply
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>

- Anonymous on June 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Output for above code:

a1
b1
a2
b2
a3
b3
a4
b4
a5
b5

- Anonymous on June 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

FCuK man.. is this inplace?

- AntiCode on July 14, 2011 | Flag
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;
}

- sandygupta on November 07, 2011 | Flag Reply
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;
}

- Ravikant on January 29, 2012 | Flag Reply
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;
}

- Ravikant on January 29, 2012 | Flag Reply
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;
}

- Ravikant on January 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ravikant on January 29, 2012 | Flag
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;
}

- Jason Tu on January 17, 2013 | Flag Reply
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];
}

}

}

- Amit on August 29, 2013 | Flag Reply
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++;
}
}

- Anonymous on September 17, 2013 | Flag Reply
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);
}

- Anonymous on September 30, 2013 | Flag Reply
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

- Nitin Sharma on October 03, 2013 | Flag Reply
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] )

- kobo on October 25, 2013 | Flag Reply
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;
}

}

- Bharath on November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Bharath on November 04, 2013 | Flag Reply
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();
			finalList.add(currentValue);
			values += currentValue+" ";
		}
		
		System.out.println(values);
	}

- Fernando on December 09, 2013 | Flag Reply
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;
}

- Puneet on March 01, 2014 | Flag Reply
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;
}

- Puneet on March 01, 2014 | Flag Reply
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;
}

- Puneet on March 01, 2014 | Flag Reply
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;
}

- Puneet on March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Good!

- Anonymous on March 29, 2014 | Flag Reply
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;
			}
		}
	}

- Julie on October 15, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More