CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview
More Questions from This Interview



Comment hidden because of low score. Click to expand.
3
of 3 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 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 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 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 June 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This algo would be nlogn

- Anonymous 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 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 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 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 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 July 07, 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