Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
here is a solution, i think this is similar to what 'dead' says. dont mind minor holes in the logic, i just made it up. and please tab your answers when you type
int i = 0;
while(i < n){
array[3i] = swap(getA(i), array[3i]);
array[3i+1] = swap(getA(i), array[3i+1]);
array[3i+2] = swap(getA(i), array[3i+2]);
}
getA(i){
return array[i];
}
getB(i){
return array[(n+i)-1];
}
getC(i){
return array[(2n+i)-1];
}
in the while loop, the function calls are getA(), then getB(), getC().. sry for the typo
when i = n-1 getB(i) returns array[2n-2] and getC(i) returns array[3n-2]... which is array out of bound exception
lol what are you talking about? It's a working code,
n
is not the size of the array
n
is the order of elements.
we have a total of 3n elements in the array as per the question. Ask first before down-voting.
Sorry for down voting for incorrect reason... but i am not yet convinced with your method..
do you have full working code?
check ideone.com/0sCod .. check the expected output in the comment and the actual output.. it differs.. if i am wrong .. correct it and repost.. and then i up-vote..
void convert(int *a,int n)
{
int size=n/3;//frame size(since there are three frame of equal size)
int i=0; //starting of first frame
int j=size; //starting of second frame
int k=2*size //starting of third frame
int t1,int t2;
while(i<n)
{
t1=a[j]; t2=a[k];
r_shift(a,++i,size) //right shift
a[i]=t1;
r_shift(a,++i,size) //right shift
a[i]=t2;
j=j+2;k=k+2;//changes due to right shift
j++;k++;//next no.
}
}
This will be a O(n^2) solution. I think in this case O(n) solution is possible.
The approach will be something like this:
Start traversing from left to right keeping a count of number of elements processed. For each of the position, find the element which should be there (like for position 3i, ai should be there, for 3i+1 -> bi and 3i+2 ->ci and so on). Get the position of ai(or bi or ci) which is derivable and swap it with current element. Next try to find the correct position of swapped element and so on. When your counter reaches n, all you elements will be in correct order.
start_mid points to b1 and start_hi points to c1
public static void arrange(int[] a, int start_mid, int start_hi) {
int low = 0;
while((start_hi<=(a.length-1))) {
low++;
int T = a[start_mid];
for(int k = start_mid-1; k>=low;k--) {
a[k+1] = a[k];
}
a[low++] = T;
start_mid++;
T = a[start_hi];
for(int k = start_hi-1; k>=low; k--) {
a[k+1] = a[k];
}
a[low++] = T;
start_mid++;
start_hi++;
}
}
start_mid points to b1 and start_hi points to c1
public static void arrange(int[] a, int start_mid, int start_hi) {
int low = 0;
while((start_hi<=(a.length-1))) {
low++;
int T = a[start_mid];
for(int k = start_mid-1; k>=low;k--) {
a[k+1] = a[k];
}
a[low++] = T;
start_mid++;
T = a[start_hi];
for(int k = start_hi-1; k>=low; k--) {
a[k+1] = a[k];
}
a[low++] = T;
start_mid++;
start_hi++;
}
}
#include<stdio.h>
int main()
{
int m;
char arr1[11]={'a','1','a','2','a','3','a','4','a','5'};
char arr2[11]={'1','b','2','b','3','b','4','b','5','b'};
char arr3[11]={'1','c','2','c','3','c','4','c','5','c'};
char arr4[31];
for(int i=0,k=0,j;i<10;i+=2)
{
arr4[k++]=arr1[i];
arr4[k++]=arr1[i+1];
j=i+1;
arr4[k++]=arr2[j--];
arr4[k++]=arr2[j];
j=i+1;
arr4[k++]=arr3[j--];
arr4[k++]=arr3[j];
}
for(int k=0;k<30;k++) printf("%c",arr4[k]);
scanf("%d",&m);
return 0;
}
This is in place Array transpose.
Working code!
http://codepad.org/GzIUMLjy
}
- words&lyrics July 26, 2012