## Microsoft Interview Question for Software Engineer / Developers

• 0

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

ques: Suppose we have an array a1,a2,... ,an, b1,b2,..., bn How to change this array to
a1,b1,a2,b2, ...,an,bn in O(n) time and in O(1) space.
Solution:

the position of a0 and bn is fixed and they wont change so we have to replace remaining n-2 elements
count=n-2;

we strat from 2nd element find its position store the element at that position in temp variable and store 2nd element at that position.
now find the position of the stored temp varible and do as above

but it ends up at the position where u start so
start again from a position which ends up relocationg maximum no of elements.

#include<stdio.h>
#define n 10

int main(){
int a[n];

int count=0,i=1,put,temp,j=0;
int start=1;

for(j=0;j<n;j++)
a[j]=j;

printf("\n\n Elements: ");

for(j=0;j<n;j++)
printf("%d ",a[j]);

put=a;

while(count < n-2){
count++;
if(i< (n/2)){
temp=a[i*2];
a[i*2]=put;
put=temp;
i=2*i;
}
else{
temp=a[2*(i- (n/2))+1];
a[2*(i-(n/2))+1]=put;
put=temp;
i=2*(i-(n/2))+1;
if(i==start){
start=start+2;
put=a[start];
i=start;
}
}
}

printf("\n\nAfter Reordering: ");
for(j=0;j<n;j++)
printf("%d ",a[j]);

}

its not working when n>62 ie n=64 66 .....

could anyone improve or get another solution......

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

By working on a few examples I realized that the if(i == start) part of the above code is executed only for odd values of 'n'.

For odd values of 'n' say n=11, the sequence of movements that we have are:

1 - 2 - 4 - 8 - 16 - 11 - 1
3 - 6 - 12 - 3
5 - 10 - 20 - 19 - 17 - 13 - 5
7 - 14 - 7
9 - 18 - 15 - 9

Each of these sequences have only one ascent. While for even values of n, say n = 10, the sequence is:

1 - 2 - 4 - 8 - 16 - 13 - 7 - 14 - 9 - 18 - 17 - 15 - 11 - 3 - 6 - 12 - 5 - 10 - 1

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

Here the number of elements cannot be odd since its given that a goes from 1 to n. and b also goes from 1 to n . Even if a and b individually have odd number of elements , they still would total up to even in the final array.

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

I am not sure if I am missing something here? This looks like a simple problem. I wrote following code for the same.

DWORD MergeArrays(int *Arr1, int *Arr2, int Len)
{
//Assumption Arr1 length is equal to 2 * Len. If not need to reallocate the memory
int i, j;
for(i = (2*Len - 1), j = Len - 1; i >= 0, j >= 0; i--, j--)
{
Arr1[i--] = Arr2[j];
Arr1[i] = Arr1[j];

}
return 0;
}

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

Am I missing something here? I thought following would be the simplest code to solve this

``````DWORD MergeArrays(int *Arr1, int *Arr2, int Len)
{
//Assumption Arr1 length is equal to 2 * Len. If not need to reallocate the memory
int i, j;
for(i = (2*Len - 1), j = Len - 1; i >= 0, j >= 0; i--, j--)
{
Arr1[i--] = Arr2[j];
Arr1[i] = Arr1[j];

}
return 0;
}``````

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

Am I missing something here? I thought following would be the simplest code to solve this

``````DWORD MergeArrays(int *Arr1, int *Arr2, int Len)
{
//Assumption Arr1 length is equal to 2 * Len. If not need to reallocate the memory
int i, j;
for(i = (2*Len - 1), j = Len - 1; i >= 0, j >= 0; i--, j--)
{
Arr1[i--] = Arr2[j];
Arr1[i] = Arr1[j];

}
return 0;
}``````

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

We need to insert value of middle element of array,immediately after first element.(take the middle element, store it in temp, shift the array to left from second position till middle of array and then insert that value stored in temp as second element of array.

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

The shift operation will prove very expensive resulting in O(n^2). does any1 have a correst solution to this problem

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

{
t=lower+1; // lower bound of array
mid=size/2; // size= array size
while(mid<n)
{
temp=a[mid];
for(i=mid;i>t;i--)
{
a[i]=a[i-1];
}
a[t]=temp;
t+=2;
mid++;

}

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

this is O(n ^ 2)

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

This algorithm works. I wonder if anybody has found any O(n) algorithm with just 0(1) space.

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

For n = 2m we've the solution :

public static void Reorder(int start, int end)
{
int abslength = end - start + 1;

for (int i = 0; i < abslength; i++)
Console.Write(array[i] + ",");

int thisstart = 0;
for (int span = abslength; span > 2; span = span / 2)
{

for (int i = start; i < end; i = i + span)
{
thisstart = i;

int quart = span / 4;
int mid = span / 2;

swapBlock(thisstart + quart, thisstart + mid, quart);
}
}
}

private static void swapBlock(int start1, int start2, int length)
{
int temp = 0;
int i = start1, j = start2;
for (; i < (start1 + length); i++, j++)
{
Console.WriteLine("Swap "+i+" with "+j);
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}

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

Does array a have enough storage to hold 2n values ? if yes the solution seems trivial, run through a from n-1 to 1 and placing the values in slots 2n-1, 2n-3..1 and run through b placing 0 to n in a's 1,3,5..2n

However, the question seems to suggest that array a has only has space for n elements.

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

Here is one solution.

``````public static int memberOfGroup(int x, int n)
{
int x1 = x;
int groupId = x;
do
{
x = n + (x-1);
while(x%2==0)
{
x = x/2;
}

if(groupId>x)
{
groupId = x;
}
}while(x!=x1);
return groupId;
}

public static int[] reorderArray(int[] a)
{
int n = a.length;
int count = 0;
int i = 1;
while(true)
{
int cur = i;
int next = i;
int temp = a[cur];
do
{
next = (2*cur)/n + (2*cur)%n;
int temp1 = a[next];
a[next] = temp;
temp = temp1;
count++;
cur = next;
}
while(next!=i);
if(count<n-2)
{
do
{
i+=2;
if(memberOfGroup(i, n)==i) break;
}while(true);
}
else
{
break;
}
}
return a;
}

public static int[] createArray(int n)
{
if(n%2==0)
{
int[] a= new int[n];
for(int i=0; i< n/2; i++)
{
a[i] = i;
}
for(int i=n/2; i< n; i++)
{
a[i] = i-(n/2);
}
return a;
}
return null;
}

public static void main(String[] args)
{
int[] a =  createArray(128);
a = reorderArray(a);
for(int i=0; i<a.length; i++)
{
System.out.println(a[i]);
}

}``````

I am not sure how to compute the time complexity of this algorithm though

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

I think I got it:
Notice that element at index i is shifted to the right by 2*i, modulo 2n-1.
Try it first to understand the pseudocode.

Pseudocode:

traverse array from i = index 0 to n
get the new index of i in variable nI
the current index i is also in variable cI

nI = 2*i % (2n -1), cI = i
do
swap values at nI and cI
cI = nI
np = 2*cI % (2n -1)
while nI is not index

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

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int main( int argc, char **argv )
{
// array in question
int array[] = { 1, 3, 5, 7, 9, 100, 200, 300, 400, 500 };

// declaration
int init = 1;
int mid = (sizeof( array ) / sizeof( array )) / 2;
int i = init;
int n = mid;

// basic algorithm
while ( init < mid )
{
i = init ++;
while ( i < mid ) swap( array[ i++ ], array[ n++ ] );
n = mid;
}

// displaying
copy( array, array + (mid * 2), ostream_iterator<int>(cout," ") );
cout << endl;

return EXIT_SUCCESS;
}

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

I don't think this algorithm is O(n)

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

Hi Solution for this problem is :
Elements of a category are : n
Elements of b category are : n
array size is 2n

1) Go to n+1 postion.
2) Pick this element is toggle it with element at nth position.
3) Now go to nth position and toggle it with element at n-1 position.
4) REPEAT step 2-3 n-1 times.
5) Once done now go to n+2 and repeat steps 2-5 n-2th times.
6) Final array will be a1, b1, a2, b2, a3, b3,...

Code................
int[] a = new int { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
int nth = 5;
for (int Z = 0; Z <= nth - 2; Z++)
{
for (int j = 0; j < nth - 1 - Z; j++)
{
int temp;
temp = a[nth - j + Z];
a[nth - j + Z] = a[nth - 1 - j + Z];
a[nth - 1 - j + Z] = temp;
}
}
// sorted array a here .

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

Read the question man, O(n) time, O(1) memory

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

Well the above solution is right but it takes O(n2)...
It has to be done in O(n)

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

``````void changeArr(int arr[]){
int temp,j=1;
int m=arr.length()/2;
temp=arr[j];
while(j<arr.length()){
arr[j]=arr[m];
m++;j++;
if(j<arr.length()){
int temp1=a[j];
arr[j]=temp;
temp=temp1;
j++;
}
}
}``````

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

Perfect solution

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

Sorry pasted the wrong one. This might work

``````void changeArr(int arr[]){
int temp,j=1;
int m=arr.length()/2;
temp=arr[j];
while(j<arr.length()){
temp=arr[j];
arr[j]=arr[m];
m++;j++;
if(j<arr.length()){
int arr[m-1]=arr[j];
arr[j]=temp;
temp=arr[m-1];
j++;
}
}
}``````

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

Above Solution is not working...
For array 1..10 try out 3 and 4 are not a correct position

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

vamsi ur code is not workin

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

I think this is a trick question. You can only create one blank space while swapping and you need to do shift operation. I dont see any way how this can be done in O(n) & O(1) iteratively. Using recursion, it can be easily solved in this way

// arr - array
// total length of array = 2n

assign(int i, int a, int b)
{
if(i < n)
{
// a = arr[i]; b = arr[n+i];
assign(i + 1, arr[i],arr[n+i]);
}
// overwrite the source array with function arguments
arr[i*2] = a;
arr[i*2 + 1] = b;
}

// to start the operation
assign(0,arr,arr[n]);

recursion has an implicit O(n) space complexity. if that is allowed, then this is the correct answer

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

works prefectly.....

#include<iostream>
using namespace std;

void print(int arr[], int start,int end)
{
for(int i=start;i<=end;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;

}

void swap(int &x,int &y)
{
int temp=x;
x=y;
y=temp;
}

void corr_arr(int arr[], int start, int end)
{

int new_end=end;

if((end-start)%2!=0)
{
new_end=end-1;
}

int mid= start + (new_end-start) /2;

while(mid!=start)
{
if(mid==new_end)
{
mid--;
}

if(mid==start)
break;

swap(arr[mid],arr[new_end]);
new_end--;

}

}

void corr_arr1(int arr[], int start, int end)
{

int check=(end-start)%2;
int new_start=start;

if((end-start)%2!=0)
{
new_start=start+1;
}
int mid= start + (end-new_start) /2 ;

if(check==1)
mid++;

while(mid!=end)
{
if(mid==new_start)
{
mid++;
}

if(mid==end)
break;

swap(arr[mid],arr[new_start]);

new_start++;

}

}

void reorder(int arr [], int size)
{
int arr1_start=0;
int arr1_end=size/2-1;

int arr2_start=size/2;
int arr2_end=size-1;

print(arr,0,size-1);

corr_arr(arr,arr1_start,arr1_end);

print(arr,0,size-1);

corr_arr1(arr,arr2_start,arr2_end);

print(arr,0,size-1);

if((size/2)%2==1)
{
for(int i=1;i<size/2;i+=2)
{
swap(arr[i],arr[i+(size/2)]);

}
}
else
{
int size1=size -2 ;

for(int i=1;i<=size/2;)
{
swap(arr[i],arr[i+(size1/2)]);
i+=2;
}

}

print(arr,0,size-1);

}

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

int size=sizeof(arr)/sizeof(int);

reorder(arr, size);
}

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

Perfect job！！！

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

Perfect job！！！

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

assume the array is A[2n], then, if i is from 0 to n-1, the final position of A[i] is 2*i; if i is from n to 2n-1, the final position of A[i] is 2(i-n)+1. So simply move all A[i] to its final position is the solution.

psuedo code is as following.

for (i =0; i< 2n; i++) {
if (i < n)
A[i] <-> A[2i];
else
A[i] <-> A[2(i-n)+1];
}

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

Have you ever thought about your solution? It is definitely not working!

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

quickswap(int* a, int len)
{
if(len<=2) return;
for(int i=len/4;i<len/2;i++)
swap(a[i],a[i+len/4]);
quickswap(a,len/2);
quickswap(a+len/2,len/2);
}

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

This algorithm is correct... O(n) time and O(1) space..

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

No, this is not correct.
It is working only if len is power of 2.
And complexity is not O(n) but O(logN)

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

did not work for n= 16
input = arr[]={1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,16};
expected out put :1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

output of ur code is : 1
5
9
13
2
6
10
14
3
7
11
15
4
8
12
16

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

Let the arrays be A and B.
A = [1, 2, 3, 4, 5]
B = [a, b, c, d, e]

Now the algorithm goes like:
1. Swap the even position elements from array A with odd position element from array B.
This will give
A = [1, a, 3, c, 5]
B = [2, b, 4, d, e]
2. Now form groups of elements from array A and array B, taking two elements at a time.
A = [(1,a),(3,c),(5)]
B = [(2,b),(4,d),(e)]
3. Repeat step 1. This time swap the even groups from array A with odd groups in array B.
Now, A = [(1,a),(2,b),(5)]
B = [(3,c),(4,d),(e)]
4. Now again form groups by grouping two adjacent groups together and repeat step 1.
This gives us : A = [(1,a,2,b),(5)] and B = [(3,c,4,d),(e)]
after repeating step 1 on the above array we get data as
(1,a,2,b),(3,c,4,d),(5),(e)
Now we cant group further, and our algo terminates with the desired output.

PS : I havent handled all the edge cases, but I feel it can be worked out with little more thinking.

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

If we look at a simple example, we will know how to handle it.
a1, a2, a3
b1, b2, b3
================
a1, a2, a3
b1, a3, b3,
tmp = b2
===============
a1, a2, a2
b1, a3, b3
===============
a1, b1, a2
b1, a3, b3
==============
a1, b1, a2
tmp,a3, b3
Here tmp is equal to b2 from the first step
so, it is O(2n), which is also O(n), and O(1) memory.
We can easily figure out the code based on which array is the data we wanna use from to fill which hole of the arrays.

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

As KK commented, I don't think one can use recursion for this problem, unless the recursive function does not take any argumentrs - because for each argument it takes, the space used is 0(n) where n is number of recursive calls.

But here's an iterative one:

// right: points to first array element
// on the right which needs to be
// brought to the left.
// len: length of the array
// arr: is the array itself
void changeArr( int *arr, int len, int *right ) {
int t1 = *arr;
int t2 = *right;
int end = arr + len;
int *pos = arr; // points to next pos that needs to be filled

while ( right < end ) {
swap(pos,t1); // temp = *pos,*pos = t1,t1 = temp; use LHS int
++pos; // advance position to fill
swap(pos,t2); // use RHS int
t1 = t2; // set the next LHS int to be used
t2 = *++right; // set the next RHS element to be used
++pos; // advance the position again
}
}

You need to call the above function with correct "right".

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

if you are implementing swap as a function, we need to make sure to pass t1 by reference, or use pointer..

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

if you are implementing swap as a function, we need to make sure to pass t1 by reference, or use pointer..

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

Have you ever tested your program? It is NOT correct at all!!!

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

Has anybody found a correct O(n) time and O(1) space solution to this problem ?

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

If Memory is not a concern, here is a quick solution:

``````public static string[] ReorderArray(string[] input)
{
int length = input.Length;
string[] output = new string[length];
int eventPos=0;
int oddPos=length/2; //start for second half of the input

for (int i = 0; i < length; i++)
{
if (i % 2 == 0)//even position 0, 2, 4, ..
{
output[i] = input[eventPos++];
}
else //odd position 1, 3, 5, ...
{
output[i] = input[oddPos++];
}
}
return output;
}``````

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

Yes there is an O(n) time, O(1) solution. Search the web for

Inshuffle in-place linear algorithm.

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

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

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int[] num = { 1, 3, 5, 7,9,11,13,15, 2, 4, 6, 8,10,12,14,16 };
int temp = 0;
int nxt = 1;

for (int i = 0; i < num.Length/2; i++)
{
temp = num[num.Length / 2 + i];
for (int t = num.Length / 2 + i; t>i+nxt ; t--)
{
num[t] = num[t - 1];

}
num[i+nxt] = temp;
nxt +=1 ;
}
for (int i = 0; i < num.Length; i++)
{
Console.Write(num[i] + " ");
}

}
}
}``````

this works, but what is the complexity of this?

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

1: a1 { a2 a3 a4 b1 b2 b2 } b4
2: a1 b1 { b2 b3 a2 a3 } a4 b4
3: a1 b1 a2 { a3 b2 } b3 a4 b4
4: a1 b1 a2 b2 a3 b3 a4 b4

Try doing the above using a program

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

This one does not work!
It takes O(n^2) time.

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

Simple C++ solution, but in O(n^2):

``````#include <iostream>

void RotateLeft(int v[], int i, int m) {
int tmp = v[i];
for(int j = i - 1; j >= i - m; --j){
v[j + 1] = v[j];
}
v[i - m] = tmp;
}

void Interleave(int v[], int n) {
for(int i = 0; i < n; ++i){
RotateLeft(v, i + n, n - i - 1);
}
}

int main() {
int v[] = {1,2,3,4, 10,20,30,40};
int len = sizeof(v) / sizeof(int);
Interleave(v, len / 2);
// 1 10 2 20 3 30 4 40
for(int i = 0 ; i < len; ++i){
std::cout << v[i] << " ";
}
std::cout << std::endl;
return 0;
}``````

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

Here is the solution:
interviewcodesnippets.com/?p=171

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

@above the code in the link is O(nlogn) not O(n)

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

I think this can be solved in O(n) using Stack.
1. Take 2 pointes say i and j
2. i points to an position and j points to bn position
3. in loop while i > 0 and j > an position
4. read element at j the position and push it to stack.
5. read element at i th position and push it to stack.
6. decrement i and j
7. repeat step 3 to 6 untill i becomes a1 or j becomes b1
8. pop all the elements from stack and assign them in the array.
9. Now the elemtns in array are a1b1a2b2.....anbn positioned.

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

But the question says no additional space to be used.

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

This is my implementation of the direct and inverse problems solutions (perfect_shuffle_permutation_backward completely answers the question and works perfect with O(n) time and O(log log n) (same as in-place) memory requirements):

``````#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cassert>
template< class V >
struct perfect_shuffle_permutation_forward
{
typedef typename V::iterator I;
typedef typename V::size_type SIZE;
void operator () (V & v) const
{
operator () (v.begin(), v.size());
}
void operator () (I const begin, I const end) const
{
operator () (begin, std::distance(begin, end));
}
void operator () (I const first, SIZE const size) const
{
SIZE sub_size;
for (SIZE offset(0); offset < size; offset += sub_size) {
sub_size = 1;
while (offset + sub_size * 3 < size) {
sub_size *= 3;
}
I const curr(first + offset);
++sub_size;
if (offset > 0) {
I const prev(first + offset / 2);
I const next(curr + sub_size / 2);
std::rotate(prev, curr, next);
}
}
}
private :
void cycle_leader(I const & begin, SIZE const & size) const
{
for (SIZE p(1); p < size; p *= 3) {
permutation permutation_(p, size);
while (++permutation_) {
using std::swap;
}
}
}
struct permutation
{
permutation(SIZE const & leader_, SIZE  const & size_)
, size(size_)
{ ; }
bool operator ++ ()
{
if ((current % 2) != 0) {
current += size;
}
current /= 2;
}
operator SIZE () const
{
return current;
}
private :
SIZE current;
SIZE const & size;
};
};
template< class V >
struct perfect_shuffle_permutation_backward
{
typedef typename V::iterator I;
typedef typename V::size_type SIZE;
void operator () (V & v) const
{
operator () (v.begin(), v.size());
}
void operator () (I const begin, I const end) const
{
operator () (begin, std::distance(begin, end));
}
void operator () (I const first, SIZE const size) const
{
SIZE sub_size;
for (SIZE offset(0); offset < size; offset += sub_size) {
sub_size = 1;
while (offset + sub_size * 3 < size) {
sub_size *= 3;
}
I const curr(first + offset);
{
SIZE const rest(size - offset);
I const first(curr + (sub_size + 1) / 2);
I const middle(curr + (rest / 2 + rest % 2));
I const last(middle + (sub_size + 1) / 2);
std::rotate(first, middle, last);
}
++sub_size;
}
}
private :
void cycle_leader(I const & begin, SIZE const & size) const
{
for (SIZE p(1); p < size; p *= 3) {
permutation permutation_(p, size);
while (++permutation_) {
using std::swap;
}
}
}
struct permutation
{
permutation(SIZE const & leader_, SIZE  const & size_)
, size(size_)
{ ; }
bool operator ++ ()
{
current *= 2;
if (!(current < size)) {
current -= size;
}
}
operator SIZE () const
{
return current;
}
private :
SIZE current;
SIZE const & size;
};
};
template< class V >
struct test
{
typedef typename V::size_type SIZE;
typedef typename V::value_type F;
typedef perfect_shuffle_permutation_forward< V > PF;
typedef perfect_shuffle_permutation_backward< V > PB;
bool operator () (SIZE const VECTOR_SIZE) const
{
V v;
v.reserve(VECTOR_SIZE);
for (SIZE i(0); i < v.capacity(); ++i) {
v.push_back(F(i));
}
V w(v);
std::copy(v.begin(), v.end(), std::ostream_iterator< F >(std::cout, " "));
std::cout << std::endl;
PF perfect_shuffle_permutation_forward_;
perfect_shuffle_permutation_forward_(v);
std::copy(v.begin(), v.end(), std::ostream_iterator< F >(std::cout, " "));
std::cout << std::endl;
PB perfect_shuffle_permutation_backward_;
perfect_shuffle_permutation_backward_(v);
std::copy(v.begin(), v.end(), std::ostream_iterator< F >(std::cout, " "));
std::cout << std::endl;
return ((v.size() == w.size()) && std::equal(v.begin(), v.end(), w.begin()));
}
};
int main(int argc, char *argv[])
{
typedef std::vector< int > V;
test< V > test_;
std::cout << std::endl;
for (std::size_t i(0); i < 30; ++i) {
assert(test_(i));
std::cout << std::endl;
}
return EXIT_SUCCESS;
}``````

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

{
actual = 2;
mid = n / 2 + 1;
for(int i=1;i<n;i++;
{
temp = a[actual];
a[actual]=a[mid];
a[mid]=temp;
actual++;
mid++;
}

}

for O(n) in time and O(1) in space

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

This would not work .

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

Won't work

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.