Amazon Interview Question for Software Engineer / Developers


Country: United States




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

Adding my name
Q:
1. 10 160 200 500 500
2. 4 150 160 170 500
3. 2 160 200 202 203
4. 3 150 155 160 300
5. 3 150 155 160 301

A:
Step one: compare 1. and 2. (common 160 , 500). remove other elements from Array 1.
Step two: compare new 1. (160, 500) and 3. ( common 160) remove other elements from this array i.e. 500
Step next : compare 160 with other rows .. if 160 is not there then no common data else 160 is the common data.

- Suresh February 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Choose max of arrary[i][0] and min of array[i][N] (i.e. maximum of first element and minimum of last element)., Now the answer (list of common numnbers) has to lie beteen these numbers.

Choose the array which contains maximum of first element, and for each element of this array search them in other arrays using binary search, If it is found then add them into the final list. We need to perform this search till the minimum of the last element is reached.

time: n2 log(n)

- CoolGuy February 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@suresh ... coolguy's solution is better as u need to modify the original data neither u can use extra space and since the arrays are sorted then
Time taken = n(to find max start element)+
n(elements of that array) * n (number of arrays)* logn(binary search for each element)
=n+n2logn = n2logn

However your's would be O(n3) ... if the arrays would have been unsorted then your solution would be the valid one but here we can take advantage of sorted arrays

- vik February 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

so let's do a dry run based on CoolGuy Solution:

1. 10 160 200 500 500
2. 4 150 160 170 500
3. 2 160 200 202 203
4. 3 150 155 160 300
5. 3 150 155 160 301

Maximum of first column is 10
Minimum of last column is 203
So the common element among all these rows will be between 10 and 203
10 < common element < 203
So start picking one by one all the element of row where 10 was found.In this case it was found in row 0.So let's pick 10 and search 10 in all the rows.
First iteration: 10 not found in all the rows.
Second iteration: 160 found in all the rows -keep in the final list.
Third iteration: 200 not found in all the rows.
Next number is 500 which is greater than 203.So there is no point in seraching rest of the row elements as
    10 < common element < 203

So answer is 160 which we had put in final list.

- try February 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

If the minimum complexity possible looks like to be O(n2logn) we could simply do this:

for each element v in row-1
          do binary search in rest (N-1) rows

We could improve this by comparing the min and max of each row and decide based on that whether we want to perform binary search or not, i.e. whether it is possible for a number 'num' to fall between 'min_num' and 'max_num' of that row.

Binary search -> O(log n)
For searching 1 num in n-1 rows : O(nlogn)
Binary search for each number in first row : O(n2logn)

I selected first row, we can pick any row and if a no element of the row picked is found in any of the (N-1) rows then we don't really have common data.

- Second Attempt February 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I update/correct my comment above, it can be done in O(n2) complexity. Please follow stackoverflow.com/questions/15036821/find-common-elements-in-n-sorted-arrays-with-no-extra-space

- Second Attempt March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 vote

of 0 vote
Q:
1. 10 160 200 500 500
2. 4 150 160 170 500
3. 2 160 200 202 203
4. 3 150 155 160 300
5. 3 150 155 160 301

A:
Step one: compare 1. and 2. (common 160 , 500). remove other elements from Array 1.
Step two: compare new 1. (160, 500) and 3. ( common 160) remove other elements from this array i.e. 500
Step next : compare 160 with other rows .. if 160 is not there then no common data else 160 is the common data.

- Anonymous February 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What do you think about the time complexity of your algorithm? Though this is the only solution I was able to figure out, but it seems to be linear, no?

- Sumit Gera February 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if numbers are positive O(n2)
else O(n2logn)

- huha February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

while i understand the solution for O(nlogn) , unable to get the n^2 solution. can you explain/give clue?

- SantiagoYemmiganur February 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's O(n^2) no matter the numbers are pos or neg. By tracking the largest value (say it's 'x') among the first items of n arrays, go ahead (just check the items one by one in the other n-1 arrays, binary search can be used for speeding up, but need careful design -- "parallelly" run with simple go-through) to find the items that >= x in all arrays. If all item == x, then we find a common value; otherwise, start a new iteration. It's O(n^2) because each item was checked only by once.

- liyupku2000 February 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if the element is common..we then we should be able to find it in the 1st row also.
so we need to lookup for each element in 1st row and search the same in all (n-1) row.
so it will be n* n logn time
for each element in row1
{
for each row upto N-1 rows
{
found = B_search ();
if (!found)
break;
}
}

- rahul February 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

10 160 200 500 500
4 150 160 170 500
2 160 200 202 203
3 150 155 160 300
3 150 155 160 301
what is the answer for this?

- aka February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

160

- SR February 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Obviously to find the result we have to go through all the data . So lets consider that the result will be kept in the first array. Start from the position n in the first and second array with 2 iterators: first = n and second = n;

while (second >=0 && first>=0){
   if(B[second] == A[first]) first--;
   second--;

}
remove(A,0,first); // remove all the elements in A from index 0 to first
go do the same for the first and third array, first and fourth and so on.

At the end return A (the first array).

- Kamy February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doen't work..
Ex:
first array : 10 160 200 500 500
second array : 4 150 160 170 180

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

Should be O(n2 log n), I guess. You can traverse one of the arrays and search for its existence in all the other arrays using binary search.
I think there should be something better than this.

- alex February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi all,

I think it should be the straight forward problem of - "Intersection of K-arrays"
Going ahead with the concept of "Intersection of 2 arrays" , apply the same for K-array i.e
1) you will need K pointers for these arrays.
2) find the max of first elements of these arrays.
3) Increment the pointers if AnthArray[i] < Max{A1[0],A2[0] .... An[0]} {KnthPointer++ }
4) Repeat steps 2 & 3 unless any of the array pointers reaches to end at which point you return with all of the recorded common elements

Kindly correct / comment suggestions on this ..

- Settaluri Karthik Sriharsha February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The time complexity will be n^2 for searching all elements. and logN to find the array pointer which needs incrementing. In all it would take n^2logn. Is there a solution to find the result in n^2.

- SantiagoYemmiganur February 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can think only about n^2 logn solution, subscribing to the thread.

- S.Abakumoff February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Two solutions possible.

1. Choose smallest array. Iterate over this array and do binary search for each value in other arrays. time: O(n*n*lgN), space: O(1)

2. Suppose we have arrays[][]. Choose largest value from arrays[i][0].
Do binary search, if all arrays contain this value add this value to common list,
otherwise choose as a next search value, biggest from all found.

- m@}{ February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private List<Integer> findCommonElements( int[][] arrays ){
    	
    	final List<Integer> commonElements = new ArrayList<>();  
    	
    	int maxSoFar = Integer.MIN_VALUE; 
    	
	    while( true ){ 		    	
	    	
	    	int maxValueToSearchNext = Integer.MIN_VALUE;
	    	
	    	boolean allEqual = true;
	    	
	    	for( int j = 0; j < arrays.length; j++ ){    			
	   			
				int pos = Arrays.binarySearch( arrays[j], maxSoFar );	    			
				
				if( pos < 0 ){
					
					allEqual = false;
					pos = Math.abs(pos) - 1;
					
					if( pos >= arrays[j].length ){
						break;
					}
					
					int curValue = arrays[j][pos];
					
					maxValueToSearchNext = Math.max( maxValueToSearchNext, curValue );
					
				} 	
				else {				
					if( pos + 1 < arrays[j].length ){
						int nextValue = arrays[j][pos+1];
						if( nextValue != maxSoFar ){
							maxValueToSearchNext = Math.max( maxValueToSearchNext, arrays[j][pos+1] );
						}
					}				
				}
			}
	    	
	    	if( allEqual ){
	    		
	    		commonElements.add( maxSoFar );
	    		
	    		if( maxValueToSearchNext == maxSoFar ){
	    			break; 
	    		}
	    	}	    	
       		
       		if( maxValueToSearchNext == Integer.MIN_VALUE ){
       			break;
       		}       		
       		
       		maxSoFar = maxValueToSearchNext; 
	    }
	    
    	return commonElements;
    }

- m@}{ February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are not allowed additional/extra space.

- tng February 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int N;
int findCommonElements( int[][] arrays ){
  int res=N, p0=0, p1=0, pCur=0;
  for(int i=1; i<N; i++){ 
    p0=0; p1=0; pCur=0;
    while(p0<N && p1 < N && pCur < res){
      if(arrays[0][p0] ==arrays[i][p1]){
        arrays[0][pCur++]=arrays[0][p0];
        p0++; p1++; 
      }
      else if(arrays[0][p0] >arrays[i][p1]){
        p1++;
      }
      else p0++;
    }
    res = pCur;
  }
  return res;
}

- N^2 solution February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I can think of n*n*logn solution with some optimization.
1. Find the maximum of a[i][0] for all the i {0, n-1}. Let this be curMax.
2. Clearly all the values less than curMax can not be in the common set.
3. Search for curMax in all the rows using binary search such that binary search returns the next highest value index if curMax is not present. <This is the caveat, we will need nextBeginIndex[n] to store these index values. If this is not allowed, then this optimization is not possible. > Store next highest index in nextBeginIndex[n]
4. If all the rows return successful result, curMax is common.
5. Now find maximum of a[i][nextBeginIndex[i]] for all i {0, n-1}
6. Repeat the same steps.

- SR February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given that all arrays are sorted following code can do it O(n2) time

for(i=0 ; i< (N-1); i++)
    {
        p = q = 0;
        while(p < N && q < N)
        {
            if(a[i][p] == NOT_DEFINED || a[i][p] < a[i+1][q] )
            {
                p++;
            }
            else if(a[i+1][q] < a[i][p])
            {
                a[i+1][q] = NOT_DEFINED;
                q++;
            }
            else
            {
                p++;
                q++;
            }


        }
        while(q< N)
        {
            a[i+1][q] = NOT_DEFINED;
            q++;
        }

    }
    for(i = 0 ; i< N; i++)
    {
        if(a[N-1][i] != NOT_DEFINED)
            printf("%d ", a[N-1][i]);
    }

- Anonymous February 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is NOT_DEFINED here?

- Nisha Singh February 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this works for 3 arrays

Iterator<?> iter=A.keySet().iterator();
		while(iter.hasNext())
		{
			Object key=iter.next();
			
			if(B.containsKey(key) && C.containsKey(key))
				System.out.println(key);
		}

- Anonymous February 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iterator<?> iter=A.keySet().iterator();
		while(iter.hasNext())
		{
			Object key=iter.next();
			
			if(B.containsKey(key) && C.containsKey(key))
				System.out.println(key);
		}

- Anonymous February 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Divide and conquer paradigm;
There are N arrays.

1. Apply divide till u reach base problen that is 2 arrays. we can find the common elements in O(N) time without any extra space. The return type of this function is the array which list only the common elements.(we know that we don't need a separate array to store this, i.e if we have two arrays A and B the number of common elements will be less than or equal to size of A and B , and all we need to do is return one array A or B which just contains the common elements )
2. The splitting takes O(logN) time.

Hence the run time is O(NlogN) . Anybody came with a O(N) algorithm please let me know

- pras July 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You should simply perform a merge.

- K February 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cleary mentioned not to use extra space.
so merge will take O(N) space.

- huha February 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

maybe you can do it in place so that you don't need extra space. just a guess...

- zyfo2 February 04, 2013 | Flag


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