## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone 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++;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

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{
}
return found;
}

}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

This algo would be nlogn

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); }
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;
}``````

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;
}

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

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

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

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

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.

### 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.