Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 4 vote

Compare A[k/2] and B[k/2].
If A[k/2] < B[k/2], it means these A[1] to A[k/2] elements are part of first k elements.
Now, the kth element can be in A[k/2 + 1] to A[k] or B[1] to B[k/2].
Hence, we reduced the problem to half its original size.
Repeating the comparison of mid-elements of this subproblem, we reduce it to further half.
Hence at the end of logK iterations, the lesser value will be the kth element.
So, complexity is O( log K)

- Kalyan May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Does it work for all the cases?

- Anonymous June 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

"Now, the kth element can be in A[k/2 + 1] to A[k] or B[1] to B[k/2]."

This is wrong. Should be A[k/2 + 1] to A[k] or B[1] to B[k].

- Anonymous June 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is wrong!!

You said:
"
If A[k/2] < B[k/2], it means these A[1] to A[k/2] elements are part of first k elements.
"

Well, not necessarily

consider the case

A[] = {2,3,4,5,6,7}
B[] = {1,6,9,10,11,12}
Consider k = 4
now comparing 4 & 10 , 10 is greater
So by your algo algo {2,3,4} should be three smallest
but answer should be {1,2,3}

Answer must be either in of the array and within first k elements in each so total data to be looked at is 2k
Correct solution will eliminate half of it after each iteration. Its easy to see how it can be done!
Think more!

- words&lyrics July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

this sln is O(log(n)) not O(log(k)) like the OP wanted.

- citisushi August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@word&lyrics

This is wrong!!
{2,3,4} are part of the first k elements. That much is correct.
Think more!

- Anonymous September 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The above is O(k) soln,..

- Anonymous May 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

using namespace std;

#include <iostream>

int main()
{
	int k = 5;
	int a[] = {1, 5,  7,  8,      10, 15, 17,  20,          25,  38,                 50,           61,  95, 200, 305, 645};
	int b[] = {6, 10, 18, 20,     31, 57, 107, 117,         210, 510,                608,          730, 850};
	
	int la, ra, ma;
	int lb, rb, mb;
	
	//index starts from 1; subtract 1 for actual index
	ra = rb = k;
	
	while (ra+rb != k) {
		if (a[ra-1] == b[rb-1] && ra+rb==k)
			break;
		
		if (a[ra-1] > b[rb-1]) {
			la = k - rb;
			ra = (la + ra) / 2;
		}
		else {
			lb = k - ra;
			rb = (lb + rb) / 2;
		}
	}
	
	if (ra == 0)
		cout << b[rb-1];
	else if (rb == 0)
		cout << a[ra-1];
	else if (a[ra-1] > b[rb-1])
		cout << a[ra-1];
	else
		cout << b[rb-1];
	cout << endl;
	
	cout << "la ra: " << la << " " << ra << endl;
	cout << "lb rb: " << lb << " " << rb << endl;
}

- ss May 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

please explain the algo

- student June 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

output for k=6
{1,2,3,4,5,7},
{6,9,10,11,12,13}
will be 7 according to ur algo
but ans is 6

- guneesh June 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

fill or delete some elements ,make the 2 array with same size k, problem turn into find (m+n)/2 th elements in2sorted array(with size m and n), i remember it'sO(max(logm,logn)) ,in this case k=m=n , so its done. not sure, maybe works :)

- NGLOOM May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if the 2 sorted array are both larger than k, remain the k elements of the beginning, because the rest are useless. now we has 2 k-length array, problem turn into find k th in those two array as you said

- zxthirteen May 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] A = {10,20,80};
		int[] B = {30,40,50,60,70,90};
		
		int k=7,i=0,j=0,val=-1;
		
		for (int z= 0; z<k ; z ++) {
			
			if (A[i] < B[j]) {
				val = A[i];
				i ++ ;
			} else {
				val = B[j];
				j++;
			}
		}
		
		System.out.println(val);

Space Complexity O(1), Time Complexity O(k)

- Brian May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
 * Two sorted array. Find kth smallest element
O(logK)
 */
	static int findKFromTowSortedArray(int []a , int [] b, int k){
		
		int i = Math.min(k, a.length - 1);
		int j = Math.min(k, b.length - 1);
		int medianA, medianB;
		int medianAindex, medianBindex;
		//pre condition: i<k, j<k; 
		while (i+j > k){
			int d = Math.abs(i-j);
			if (i> j){
				
				medianAindex = (k + d) /2 +1;
				medianBindex = (k - d) /2 +1;
				
			}else{
				medianAindex = (k - d) /2 +1;
				medianBindex = (k + d) /2 +1;
			}
			
			medianA = a[medianAindex -1]; // -1, becaue array is 0-based
			medianB = b[medianBindex -1];
			
			if (medianA < medianB){
				j = medianBindex -1;
			}else {
				i = medianAindex -1;
			}
		}
		
		return Math.max(a[i-1], b[j-1]);
	}

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

your order will be O(K) not log(k)

- tomb May 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

could u plse justify how would order be O(K)???

- nikhil May 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your while loop (i+j>k ) . think both array >k so i=j=k and than analyse

- tomb May 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

not correct on edge cases k1=1 or k=sum_length-1

- nobrainer September 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I did not wrote code for it .... but i think this will work.

Take the first k elements from each array(I mean just index). then do the comparison.

arr1_si = 0;
arr1_ei = k;
arr2_si = 0;
arr2_ei = k;

if (arr1[arr1_si] > arr2[arr2_ei)
---------------------k is in arr2;
if (arr1[arr1_ei] < arr2[arr2_si])
---------------------k is in arr1;

Now run this same logic by dividing the array from k to k/2 to k/4 to k/8 .........(diving and arr#_si & arr#_ei will be chosen as index)....

Each stage if cross comparison occurs then get a flag for it,,,,,,,,
At each stage when we are diving the array do this boundary check only ..... by this we will getting closer to the value set who actually serves for making kth element in the merged array

- soumyajuit May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

public static int findKthValue(int[] a, int[] b, int k) {
	int alen = a.length;
	int blen = b.length;
	int d = k;
	if (k > alen + blen) return -1; 
	if (alen == 0) { return b[k-1]; }
	if (blen == 0) { return a[k-1]; }
	int i;
	int j;
	i = k > alen ? alen-1 : k-2;
	j = k - i -2;
	while (true) {
		if (a[i] > b[j]) {
			if (j == blen-1 || a[i] <= b[j+1]) return a[i]; 
			if (j+d < blen && i-d > -2) { j += d; i -= d; } 
		} else {
			if (i == alen-1 || b[j] <= a[i+1]) return b[j];
			if (i+d < alen && j-d > -2) { i += d; j -= d; } 
		}
		if (i == -1) return b[j];
		if (j == -1) return a[i];
		d = d/2;
		if (d == 0) d = 1;
	}
}

O(logK)

- sqw May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice solution ........:)

- soumyajuit May 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please eleborate how this code is working..?

- Abhishek May 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont think you need these 2 lines:

if (alen == 0) { i = -1; }
if (blen == 0) { i = k-1; }

- devesh chanchlani May 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

someone please do some commenting or explain the algo...

not able to make out anything out of it

- student June 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

does not do a good job of checking boundary conditions. if first array of is size 100 and the second array is of size 5, and k=70, we end up with array out of bounds exception in the very first loop.

- online chesstle February 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi, could someone please explain me what this question is about?..I mean why were 2 arrays given in the first place?

Thanks,
Pavan.

- Pavan Dittakavi May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * 
 */
package com.amazon;

/**
 * @author Gaurav Gupta
 *
 */
public class KthElementofTwoSortedArrays {
	
	public long[] mergeSortedArrays(long[] aSortedArray,long[] bSortedArray) throws Exception{
		long[] finalMergeArray = new long[aSortedArray.length+bSortedArray.length];
		
		try{
			//copying the b array into the final array to make a single array for insertion sort
			for (int i = 0; i < bSortedArray.length; i++) {
				finalMergeArray[i] = bSortedArray[i];
			}
			//seeing if the length of the final array is still addition of two array's length
			System.out.println(finalMergeArray.length);
			//performing insertion sort
			for (int i = 0; i < aSortedArray.length; i++) {
				for (int j = 0; j < finalMergeArray.length; j++) {
					if(aSortedArray[i]<finalMergeArray[j]){
						for (int j2 = finalMergeArray.length-1; j2 >= j+1; j2--) {
							finalMergeArray[j2]=finalMergeArray[j2-1];
						}
						finalMergeArray[j] = aSortedArray[i];
						break;
					}
				}
			}
			return finalMergeArray;
		}catch(Exception ex){
			ex.printStackTrace();
			throw ex;
		}
	}
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try{
			long[] aSortedArray = {1,3,5,34,56,78,90,123};
			long[] bSortedArray = {2,4,9,67,87,90,156,273};
			long[] finalMergedArray = null;
			//get the merged sorted array
			KthElementofTwoSortedArrays obj = new KthElementofTwoSortedArrays();
			finalMergedArray = obj.mergeSortedArrays(aSortedArray, bSortedArray);	
			System.out.println("final merged array is formed as : "+finalMergedArray);
			long finalValue = finalMergedArray[(int) (new Long(args[0])-1)];
			System.out.println("the value of the "+args[0]+"th array object is : "+finalValue);
		}catch (Exception e) {
			// TODO: handle exception
			System.out.println("An Exception has occuered : "+e.getMessage());
		}		
	}
}

- gaurav.erg May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity: Log(k)

int firstK(vector<int> &a, vector<int> &b, size_t k)
{
	if (a.size() + b.size() < k){
		return -1;
	}

	int aidx = k < a.size() - 1 ? k : a.size() - 1;
	int bidx = k < b.size() - 1 ? k : b.size() - 1;
	int ahead = 0, atail = aidx, bhead = 0, btail = bidx;

	while (aidx+bidx+2 != (int)k){
		if (aidx+bidx+2 > (int)k){
			if (a[aidx] > b[bidx]){
				atail = aidx;
				aidx = (ahead + aidx)/2;
			}
			else{
				btail = bidx;
				bidx = (bhead + bidx)/2;
			}
		}
		else{
			if (a[aidx] > b[bidx]){
				bhead = bidx;
				bidx = (btail + bidx)/2;
			}
			else{
				ahead = aidx;
				aidx = (atail + aidx)/2;
			}
		}
	}

	return (b[bidx]>a[aidx] ? b[bidx] : a[aidx]);
}

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

If array A is of size m, B is of size n, just consider first k elements of A and first k elements of B. Now A is of size k and B is of size k. Find the median of the merged array of these two arrays using median finding algorithm.

Check my video in youtube with username ThrillAndJoyAlgos for median finding problem.

- Pramod Ganapathi July 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

FindElementKth(A, B : array ; K : wanted position)
	e = k/2
	x = e
	y = e
	While e > 1
		e = e / 2 
		if A[y] < B[x]
			y = y + e
			x = x - e
		else
			x = x + e
			y = y - e
	endWhile
	if A[y] < B[x]
		B[x] is the one !!!
	else
		A[y] is the one !!!

- Smendes May 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

fixed version

FindElementKth(A, B : array ; K : wanted position)
	e = k/2
	x = e
	y = e
	While e > 1
		if A[y] < B[x]
			y = y + e
			x = x - e
		else
			x = x + e
			y = y - e
		e = e / 2 
	endWhile
	if A[y] < B[x]
		B[x] is the one !!!
	else
		A[y] is the one !!!

- Smendes May 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

class Program
    {
        static void Main(string[] args)
        {
            Int32[] first = { 10,20, 80  };
            Int32[] second = { 30, 40,50,60,70,90 };
            Int32 Kth = 9;
            Int32 iCounter = 1;
            Int32 firstArrayIndex = 0;
            Int32 secondArrayIndex = 0;
            Int32 arrNum = 0;

            if (Kth > first.Length + second.Length)
                Console.WriteLine("Error");
            else
            {
                while (iCounter <= Kth)
                {

                    if (firstArrayIndex < first.Length && (secondArrayIndex >= second.Length || first[firstArrayIndex] < second[secondArrayIndex]))
                    {
                        firstArrayIndex++;
                        arrNum = 1;
                    }
                    else if (secondArrayIndex < second.Length)
                    {
                        secondArrayIndex++;
                        arrNum = 2;
                    }

                    if (iCounter == Kth)
                    {
                        if (arrNum == 1)
                            Console.WriteLine(first[firstArrayIndex - 1] + " from first Array");
                        else
                            Console.WriteLine(second[secondArrayIndex - 1] + " from second Array");


                    }

                    iCounter++;

                }
            }

                

            
            Console.WriteLine("done..");
            Console.ReadLine();
        }

- Lazy May 19, 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