Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    0
    of 0 votes
    10
    Answers

    How to most efficiently find duplicates/commons in two sorted arrays of integers. No extra space should be used. My answer as below

    public class Duplicate {
    
    	//private HashSet<Integer> duplicates = new HashSet<Integer>();
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		
    		int a[] = {0,2,2,4,6,8,8,9,9,10};
    		int b[] = {0,3,3,4,8,8,10,12};
    		
    		new Duplicate().mergeAndCheck(a, b);
    
    	}
    	
    	private void mergeAndCheck(int[] arr1, int[] arr2){
    		int len1 = arr1.length;
    		int len2 = arr2.length;
    		
    		int pointArr1 = 0;
    		int pointArr2 = 0;
    		while((pointArr1<len1)&&(pointArr2<len2)){
    			if(arr1[pointArr1]<=arr2[pointArr2]){
    				if((arr1[pointArr1]==arr2[pointArr2])){
    					
    					if(pointArr1==0){
    						System.out.print(" "+arr1[pointArr1]);
    					}else if(arr1[pointArr1]!=arr1[pointArr1-1]){
    						System.out.print(" "+arr1[pointArr1]);
    					}
    					//duplicates.add(arr1[pointArr1]);
    					
    				}
    				pointArr1++;
    				
    			}else{
    								
    				pointArr2++;
    							
    			}
    		}
    		
    		/*for(Integer iNT:duplicates){
    			//System.out.print("  "+iNT);
    		}*/
    		
    	}
    
    }

    - banerjees36 on June 22, 2012 in India Report Duplicate | Flag
    Amazon Software Engineer / Developer

Country: India
Interview Type: Phone Interview


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

Agreed.. O(n)

static int a1[] = {1,2,3,4,5,11,12};
	static int a2[] = {2,3,4,5,6,7,8,9,10,11,15};
	
	public static void main(String[] args) {
		int length;
		if(a1.length >= a2.length)
			length = a2.length;
		else
			length = a1.length;
		//
		for(int i=0,j=0;i<length;){
			if (a1[i] == a2[j]){
				System.out.println(a1[i]);
				i++;
				j++;
			}
			else{
				if(a1[i] < a2[j]){
					i++;
				}
				else{
					j++;
				}
			}
		}
	}

- nil_dream on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This method will not show duplicates within the same array.
So, at each step, need to test for consecutive numbers for duplicates in each of the arrays too.

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

The logic -- find out smaller array.. for each element in smaller array lookup in larger array using binary search. so complexity will be O(nlgn)
Here is the working code--

public class findCommon {

	/**
	 * @param args
	 */
	static int a1[] = {1,2,3,4,5,6};
	static int a2[] = {2,3,4,5,6,7,8,9,10,11,15};
	public static void main(String[] args) {
				
		// larger one should be binary searched.
		// add logic based on array length to iterate over smaller array and 
		// binary search larger array.
		boolean found =false;
		int i;
		//complexity  - O(nlgn)
		for(i=0;i<a1.length;i++){
			found = binarySearch(a1[i]);
			if(found){
				System.out.println(a1[i]);
				found = false;
			}	
		}
		
	}
	public static Boolean binarySearch(int num){
		
		int start = 0;
		int end = a2.length - 1;
		int mid = start + end / 2;
		//System.out.println(mid);
		
		boolean found = false;
		//binary search condition - Search continues till 
		// element not found AND start index < end index (means only on element left) 
		while(!found && start < end){
			if(num == a2[mid])
				found = true;
			else
				if(num < a2[mid]){
					end = mid-1;
					mid = (start + end) / 2;
				}
				else{
					start = mid + 1;
					mid = (start + end) / 2;
				}
		}
		//compares the last element remaining. (condition useful for boundary elements)
		if(num == a2[mid]){
			found = true;
		}
		
		if(found){
			//System.out.println("found at "+mid);
		}
		else{
			//System.out.println("not found");
		}
		return found;
	}

}

- nil_dream on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This approach is only taking advantage of the fact that one of the two arrays is sorted (the array you're binary searching). The other array could be unsorted and this algo would still work. However, it's possible to take advantage of the fact that both arrays are sorted to produce an O(n) algo. This is the merge algorithm used as part of mergesort.

- Anonymous on June 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This algo would be nlogn

- Anonymous on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ int[] a = { 1, 3, 5, 2, 3, 8 }; int[] b = { 2, 4, 5, 6, 7, 6, 5}; foreach (int k in a.Intersect(b).Union(a.GroupBy(i => i).Where(g => g.Count() > 1).Select(g => g.Key)).Union(b.GroupBy(i => i).Where(g => g.Count() > 1).Select(g => g.Key))) { Console.WriteLine(k); } - quickest work out on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n)

static void commonNum(int* arr1, int* arr2, int n, int m)
	{
		int i, j;
		i = 0;
		j = 0;
		while (i < n && j < m)
		{
			if (arr1[i] == arr2[j])
			{
				cout << arr1[i] << ' ';
				for (++i; i < n; i++)
				{
					if (arr2[j] < arr1[i])
					{
						break;
					}
				}
			}
			else if (arr1[i] < arr2[j])
			{
				for (++i; i < n; i++)
				{
					if (arr2[j] <= arr1[i])
					{
						break;
					}
				}
			}
			else if (arr1[i] > arr2[j])
			{
				for (++j; j < m; j++)
				{
					if (arr2[j] >= arr1[i])
					{
						break;
					}
				}
			}
		}
		cout << endl;
	}

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

static void commonNum(int* arr1, int* arr2, int n, int m)
{
int i, j;
i = 0;
j = 0;
while (i < n && j < m)
{
if (arr1[i] == arr2[j])
{
cout << arr1[i] << ' ';
i++;
j++;
}
else if (arr1[i] < arr2[j])
{
i++;
}
else
{
j++
}
}
cout << endl;
}

- coder on June 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Jay: They are saying "no extra space should be used".

- Jay on July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@banerjees36: They are saying "no extra space should be used".

- Anonymous on July 07, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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