Amazon Interview Question
Quality Assurance EngineersCountry: India
Interview Type: In-Person
Set two pointers at the very last number of the two arrays. Compare with the two numbers at the pointers, put the bigger one at the end of first array and move that pointer one left. Continue this process until both pointer move at the head of the arrays.
public static void main(String[] args)
{
int[] arr1=new int[]{7,10,11,20,0,0,0}//0 at the end should be assumed as empty space
int arr2 = new int[]{1,3,7};
int i2=arr2.length() -1;
int i1 = arr1.length() -1 - i2;
int j = arr1.length()-1;
while(i1>0 && i2 > 0 && j > 0)
{
if(arr1[i1] > arr2[i2])
arr[j--] = arr[i1--];
else
arr[j--] = arr[i2--];
}
if(i2>=0)
{
while(i2>=0)
{
arr[j--] = arr[i2--]
}
}
if(i1>=0)
{
while(i1>=0)
{
arr[j--] = arr[i1--]
}
}
}
/*
a[] is the bigger array;
b[] is the smaller array;
n is the size of bigger array;
m is the size of smaller array
*/
merge(int a[], int b[], int n, int m)
{
int c[n];
int i = n-m-1;
int j = m-1;
int k = n-1;
while(i>=0 && j>=0 && k>=0)
{
if(a[i] > b[j])
{
c[k] = a[i];
i--;
}
else
{
c[k] = b[j];
j--;
}
k--;
}
if(i<0)
{
while(j>=0 && k>=0)
{
c[k] = b[j];
k--;
j--;
}
}
else if(j<0)
{
while(i>=0 && k>=0)
{
c[k] = a[i];
k--;
i--;
}
}
}
public int[] mergeSortedArray(int[] array1, int sizeA, int[] array2)
{
int i=sizeA;
int j = array2.length-1;
int k = array1.length -1;
while(k>=0 && i>=0 && j>=0)
{
if(array1[i] > array2[j])
{
array1[k]=array1[i];
k--;
i--;
}
else
{
if(j>=0)
{
array1[k]=array2[j];
}
k--;
j--;
}
}
return array1;
}
The empty space in a is equal to the number of element in b, so we can merge from last element without extra space.
void mergeSortAB(int *a, int *b)
{
int ia = 3;
int ib = 2;
int last = 6;
while (ib >= 0)
{
if (ia >= 0 && a[ia] > b[ib])
{
a[last--] = a[ia--];
}
else
{
a[last--] = b[ib--];
}
}
}
static int a[7] = {4, 10, 11, 20, 0, 0, 0};
static int a_len = 4;
static int b[3] = {1, 3, 7};
void merge_sort()
{
int store_pos = 6;
int a_cur = a_len-1;
int b_cur = 2;
while(a_cur >= 0 && b_cur >= 0) {
if (a[a_cur] > b[b_cur]) {
a[store_pos--] = a[a_cur--];
} else {
a[store_pos--] = b[b_cur--];
}
}
if (a_cur < 0) {
memmove(a, b, (b_cur+1)*sizeof(int));
}
}
pos is the positon of largest element in longarray
j is the positon of largest element in small arry i.e. size
int main()
{
int longarr[7] = { 4,10,11,20 };
int smallarr[3]= { 1,3,7 };
int i =0,pos=3, n=7, j=2;
while(j>=0 && pos >=0)
{
if ( longarr[pos] > smallarr[j])
{
longarr[--n] = longarr[pos];
pos--;
}
else
{
longarr[--n] = smallarr[j];
j--;
}
}
if(pos < 0)
{
while( j>=0)
longarr[j--]=smallarr[j];
}
for(int k=0;k<7;k++)
cout<<longarr[k]<<"\t";
return 0;
}
Merge and then sort :
int a[] = {4, 10, 11, 20, 0, 0, 0};
int b[] = {1,3,7};
int c = a.length+b.length;
int d[] = new int[c];
int num = 0;
for(int i=0;i<a.length;i++){
d[num] = a[i];
num++;
}
for(int j=0;j<b.length;j++){
d[num] = b[j];
num++;
}
for(int i=0;i<d.length;i++){
int temp=0;
for(int j=0;j<d.length-1;j++){
if(d[j]>d[j+1]){
temp = d[j];
d[j] = d[j+1];
d[j+1] = temp;
}
}
}
for(int k=0;k<d.length;k++){
System.out.print(d[k] + " ");
}
int[] big = new int[] {4,10,11,20,0,0,0};
int[] small = new int[] {1,3,7};
int smallLength = small.length -1 ;
int bigvalue = big.length -1 -smallLength-1;
int bigLength = big.length -1;
while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
if(small[smallLength]>big[bigvalue]){
big[bigLength] = small[smallLength];
bigLength--;
smallLength--;
}
else if (big[bigvalue]>small[smallLength]){
big[bigLength] = big[bigvalue];
bigLength--;
bigvalue--;
}
if (smallLength>=0){
while(smallLength>=0){
if(small[smallLength]<big[bigLength]){
big[bigLength] = small[smallLength];
}
smallLength--;
bigLength--;
}
}
int[] big = new int[] {4,10,11,20,0,0,0};
int[] small = new int[] {1,3,7};
int smallLength = small.length -1 ;
int bigvalue = big.length -1 -smallLength-1;
int bigLength = big.length -1;
while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
if(small[smallLength]>big[bigvalue]){
big[bigLength] = small[smallLength];
bigLength--;
smallLength--;
}
else if (big[bigvalue]>small[smallLength]){
big[bigLength] = big[bigvalue];
bigLength--;
bigvalue--;
}
if (smallLength>=0){
while(smallLength>=0){
if(small[smallLength]<big[bigLength]){
big[bigLength] = small[smallLength];
}
smallLength--;
bigLength--;
}
}
int[] big = new int[] {4,10,11,20,0,0,0};
int[] small = new int[] {1,3,7};
int smallLength = small.length -1 ;
int bigvalue = big.length -1 -smallLength-1;
int bigLength = big.length -1;
while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
if(small[smallLength]>big[bigvalue]){
big[bigLength] = small[smallLength];
bigLength--;
smallLength--;
}
else if (big[bigvalue]>small[smallLength]){
big[bigLength] = big[bigvalue];
bigLength--;
bigvalue--;
}
if (smallLength>=0){
while(smallLength>=0){
if(small[smallLength]<big[bigLength]){
big[bigLength] = small[smallLength];
}
smallLength--;
bigLength--;
}
int[] big = new int[] {4,10,11,20,0,0,0};
int[] small = new int[] {1,3,7};
int smallLength = small.length -1 ;
int bigvalue = big.length -1 -smallLength-1;
int bigLength = big.length -1;
while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
if(small[smallLength]>big[bigvalue]){
big[bigLength] = small[smallLength];
bigLength--;
smallLength--;
}
else if (big[bigvalue]>small[smallLength]){
big[bigLength] = big[bigvalue];
bigLength--;
bigvalue--;
}
if (smallLength>=0){
while(smallLength>=0){
if(small[smallLength]<big[bigLength]){
big[bigLength] = small[smallLength];
}
smallLength--;
bigLength--;
}
int[] big = new int[] {4,10,11,20,0,0,0};
int[] small = new int[] {1,3,7};
int smallLength = small.length -1 ;
int bigvalue = big.length -1 -smallLength-1;
int bigLength = big.length -1;
while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
if(small[smallLength]>big[bigvalue]){
big[bigLength] = small[smallLength];
bigLength--;
smallLength--;
}
else if (big[bigvalue]>small[smallLength]){
big[bigLength] = big[bigvalue];
bigLength--;
bigvalue--;
}
if (smallLength>=0){
while(smallLength>=0){
if(small[smallLength]<big[bigLength]){
big[bigLength] = small[smallLength];
}
smallLength--;
bigLength--;
}
int[] big = new int[] {4,10,11,20,0,0,0};
int[] small = new int[] {1,3,7};
int smallLength = small.length -1 ;
int bigvalue = big.length -1 -smallLength-1;
int bigLength = big.length -1;
while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
if(small[smallLength]>big[bigvalue]){
big[bigLength] = small[smallLength];
bigLength--;
smallLength--;
}
else if (big[bigvalue]>small[smallLength]){
big[bigLength] = big[bigvalue];
bigLength--;
bigvalue--;
}
if (smallLength>=0){
while(smallLength>=0){
if(small[smallLength]<big[bigLength]){
big[bigLength] = small[smallLength];
}
smallLength--;
bigLength--;
}
public class MergeNew {
static int[] merge(int[] a, int[] b) {
int i= a.length-4 ;
int k = a.length-1;
int j = b.length-1;
while( i != -1 && j != -1) {
if(a[i] > b[j]) {
a[k] = a[i];
i--;
} else {
a[k] = b[j];
j--;
}
k--;
}
while(i != -1) {
a[k] = a[i];
i--;
k--;
}
while(j != -1) {
a[k] = b[j];
j--;
k--;
}
return a;
}
public static void main(String[] args) {
int a[] = {4, 10, 11, 20, 0, 0, 0};
int b[] = {1,3,7};
int[] c = (merge(a,b));
for(int k : c) {
System.out.print(k + " ");
}
}
}
merge sort from right to left, placing the result in "a" as you go. return a.
- Anonymous February 24, 2014