Amazon Interview Question for Developer Program Engineers






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

so i thinks there must be enough space in a for b's elewments to store
code if it is what i think
void Merge(int a[],int n,int b[],int m)
{
int i,j;
k=n+m-1;
i=n-1;
j=m-1;
while(i>0 &&j>0)
{
if(a[i]<b[j])
{a[k--]=a[i];
i--;
continue;
}
else
a[k--]=b[j--];

}


}

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

Above code does not work. I tried following which works,

void Merge(int a[],int n,int b[],int m)
{
int i,j;
int k=n+m-1;
i=n-1;
j=m-1;
while(k>=0)
{
if(a[i]<b[j])
{
a[k]=b[j];
k--;
j--;
}
else
{
a[k]=a[i];
k--;
i--;
}
}

//Print the array..
for(int i = 0;i<n+m;i++)
{
cout << a[i] << endl;
}
}

- Jigar Mehta July 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Guess the while loop should run until k>0

public class MergeArrays {


		public static void main(String args[]){
		int a[]={1,3,5,0,0,0};
		int [] b={2,4,6};
		merge (a,3,b,3);
		print (a);
		}


	public static void merge(int[] a,int m,int[] b,int n){
		int i=m-1;
		int j=n-1;
		int k=m+n-1;
		while(k>0){
			if(a[i]<b[j]){
				a[k]=b[j];
				k--;
				j--;
			}
			else{
				a[k]=a[i];
				k--;
				i--;
			}	
		}
	}
		public static void print(int[] a){
			for(int i=0;i<a.length;i++){
				System.out.print(a[i]+",");
			}
		}
}

- krantboy July 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

All code above have a bug.
ie. a = {1,2,3, , , ,} b ={4,5,6}
j will decrement to -1 while i is still 2
next loop, you are comparing a[2] to b[-1],
the correct code should be
void Merge(int a[],int n,int b[],int m)
{
int i,j;
int k=n+m-1;
i=n-1;
j=m-1;
while(i>=0 && j>=0)
{
if(a[i]<b[j])
{
a[k--]=b[j--];
}
else
{
a[k--]=a[i--];
}
}
while(j>=0) {
a[k--] = b[j--];
}
}

- sddys August 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@jigar @geeks
u both coded it correctly. Let me make it more readable.
this code gives u the soln in O(n) complexity

void merge(int a[],int b[], int M)
{
int i=M-1,j=M-1,k=M+M-1;

while(i>=0 && j>=0)
{
if(a[i]>b[i])
a[k--]=a[i--];

while(a[i]<=b[i])
{
a[k--]=b[j--];
if(j<0)
break;
}
}

}

cheers

- vicky July 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no need for second while it should be if..

- Hari29 August 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nonsense you can merge two arrays within the same array unless you got extra space.

- WellSaid August 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@wellsaid yes you can................ array a has more space and it can accomodate array b

- vicky August 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Treat array a[] as Heap. Insert element from b[] on by one at the end of array a[] and then re-heapify. The complexity is O(log(A+B))

- AmIWrong August 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

that might work, but heap enforces only weak ordering. so by reheapification you might break the sortedness of the first array?

- anon August 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just an idea...assuming array 'a' has enough space to hold all the elements from array 'a' and 'b'(so 'a' has to be a dynamic array'), first append all the elements from 'b' to 'a' and apply a merge sort. For example

Step 1:
a[] = { 1, 3, 5, 7, 9,...., n}
b[] = { 2, 4, 6, 8, 10,...., m}

Step 2:
now append b to a
a[] { 1, 3, 5, 7, 9,...., n, 2, 4, 6, 8, 19, ...., m}

step 2 takes O(n + m)...for convenience let's say x = n + m i.. O(x)

Step 3:
apply merge sort on the modified array a whose length is "X" now
and we know the merge sort complexity is Xlog(x)

Finally, I think I could say x + xlogx ----> xlogx (ignoring the x)

What do you guys say?

- Jay August 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

int main()
{
int a[10]={1,2,4,6,8};
int b[5]={
3,5,7,9,10
};
int i=4;
int j=4;
int k=9;
while(i>-1 || j>-1)
{
if(a[i]>b[j])
{
a[k]=a[i];
i--;
}
else
{
a[k]=b[j];
j--;

}
k--;
}
if(i==-1 && j!=-1)
{
while(j!=-1)
{
a[k]=b[j];
j--;
k--;

}

}

for(i=0;i<10;i++)
{

printf("%d\n",a[i]);
}

}

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

2-way merge backward...

Void	MergeSort( int a[], int lena, int b[], int lenb )
{
	int a_tail = lena – 1;
	int b_tail = lenb – 1;
	int ab_tail = lena + lenb – 1;

	while( a_tail >= 0 && b_tail >= 0 )
	{
		if ( a[a_tail] >= b[b_tail] )
			a[ab_tail--] = a[a_tail--];
		else
			a[ab_tail--] = b[b_tail--];
	}
	
	// if a[] finished first, copy b[] left to a[]
	if (a_tail == -1)
		while( b_tail >= 0 )
			a[b_tail] = b[b_tail] ;
}

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

#include <stdio.h>
#include <string.h>

   int main()
   {
      int a1[5] = {1, 2, 3, 4, 5};
      int a2[10] = {2, 4, 6, 8, 10, 0};
   
      int i = 4;
      int j = 4;
      int k = 9;
   
      while((i >= 0) && (j >= 0))
      {
         if(a1[i] < a2[j])
         {
            a2[k] = a2[j];
            j--;
         }
         else
         {
            a2[k] = a1[i];
            i--;
         }
         k--;
      }
      
      while(i >= 0)
      {
         a2[i] = a1[i];
         i--;
      }
   
      for(i=0; i<10; i++)
         printf("%d\t", a2[i]);
   }

- Anonymous June 05, 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