Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

This is in place Array transpose.
Working code!

http://codepad.org/GzIUMLjy

#include <stdio.h>
 
int get_index(int idx, int N) {
    return (idx % 3) * N + (idx / 3);
}
 
void swap(int *a,int *b)
{
        int t=*a;
        *a=*b;
        *b=t;
}
 
void transform_array2(int *s, int len) {
    int N = len / 3,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;

}

- words&lyrics July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the running time?

- Anonymous July 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Time complexity is O(n)
Awesome code...

- coderBon August 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

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

- dtx July 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

in the while loop, the function calls are getA(), then getB(), getC().. sry for the typo

- dtx July 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

when i = n-1 getB(i) returns array[2n-2] and getC(i) returns array[3n-2]... which is array out of bound exception

- cobra July 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- dtx July 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cobra July 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@dtx your code will not work properly after 1st iteration

- sc August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 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.
}
}

- Anonymous July 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- deadman July 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void rearrange(String[] strs){
int j=0;
for(int i=strs.length/3 *2+1;i<strs.length;i+=2){
strs[j++] = strs[i];
strs[j++] = "a";
strs[j++] = strs[i];
strs[j++] = "b";
strs[j++] = strs[i];
strs[j++] = "c";
}
}

- Anonymous July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous August 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous August 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

String convert(String s1,String s2,String s3)
{
char c1,c2,c3,temp; c1=s1.charAt(0); c2=s2.charAt(0); c3=s3.chatAt(0); temp=s1.charAt(s1.length()-1);
String s="";
for(int i=1;i<=temp;i++)
{
s=s+c1+i+c2+i+c3+i;
}
System.out.println(s);
}

- Anonymous July 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

}

- daemon July 31, 2012 | Flag Reply


Add a Comment
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.

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