Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Based on the above algo.
#include <stdio.h>
int main()
{
int a[] = {1, 2, 3, 5, 6, 10, 11, 12};
int b[] = {2, 3, 3, 6, 9, 10, 11};
int c[100] = {0};
int size, i, j, l, k, m, p;
i = j = m = 0;
size = (sizeof(a)/sizeof(a[0])) > (sizeof(b)/sizeof(b[0]))?(sizeof(a)/sizeof(a[0])):(sizeof(b)/sizeof(b[0]));
memset(c, 0, sizeof(int)*100);
for(;;) {
if(a[i] > b[j]) {
j++;
} else if(a[i] < b[j]) {
i++;
} else if(a[i] == b[j]){
c[m++] = a[i];
i++;
}
if(i >= size || j >= size)
break;
}
for(i=0;i<m;i++)
printf("%d\n", c[i]);
return 0;
}
You are assuming elements to be integers.
What if they are some objects? how will you sort them?
Create two hashsets using the arrays. The complexity would be n and m respectively. Now iterate through the set with smaller size and check if other set contains that element. The contains operation would be constant time operation yielding in overall complexity of n or m depending on the size of list. Ofcourse, you can do binary search but then complexity would be nlogm or mlogn.
Code:
public void intersectionOfSortedArrays(int a[], int b[]) {
int al = a.length, bl = b.length;
int c[] = new int[al + bl];
int i = 0, j = 0, k = 0;
while (i <= al - 1 && j <= bl - 1) {
if (i < al && j < bl) {
if (a[i] == b[j]) {
if (k == 0 || c[k - 1] != a[i]) {
c[k] = a[i];
k++;
i++;
j++;
} else {
i++;
j++;
}
} else if (a[i] < b[j]) {
i++;
} else
j++;
}
}
//Output
for (int n = 0; n < k; n++)
System.out.print(a[n] + " ");
}
public void printCommon(int[] A, int[] B) {
int firstIndex = 0;
int secondndex = 0;
while (firstIndex < A.length && secondndex < B.length) {
if(A[firstIndex] == B[secondndex]) {
System.out.println(A[pointer[1]);
firstIndex = increment(A, firstIndex);
secondndex = increment(B, secondndex);
}
else if(A[firstIndex] < B[secondndex]) {
firstIndex = increment(A, firstIndex);
}
else {
secondndex = increment(B, secondndex);
}
}
}
public int increment(int[] A, int i) {
int result = i;
while(i < A.length) {
if(A[result+1] == A[result]) result++;
else break;
}
return result + 1;
}
Correction:
public void printCommon(int[] A, int[] B) {
int firstIndex = 0;
int secondIndex = 0;
while (firstIndex < A.length && secondIndex < B.length) {
if(A[firstIndex] == B[secondIndex]) {
System.out.println(A[pointer[1]);
firstIndex = increment(A, firstIndex);
secondIndex = increment(B, secondIndex);
}
else if(A[firstIndex] < B[secondIndex]) {
firstIndex = increment(A, firstIndex);
}
else {
secondIndex = increment(B, secondIndex);
}
}
}
public int increment(int[] A, int i) {
int result = i;
while(result < A.length) {
if(A[result+1] == A[result]) result++;
else break;
}
return result + 1;
}
public class CommonInteger {
public static void main(String[] args) {
int a[] = {1,2,3,4,5};
int b[] = {2,4,5,7,8,9,10};
Set<Integer> set1 = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();
for(int i=0;i<a.length;i++)
set1.add(a[i]);
for(int i=0;i<b.length;i++)
{
if(!set1.add(b[i]))
{
set2.add(b[i]);
}
}
Iterator<Integer> iter = set2.iterator();
while(iter.hasNext())
System.out.println(iter.next());
}
}
algo:
- aka April 13, 2013first list: 1 2 4 5 6
second list: 3 5 6 7 8 9
start from lowest of both the lists, in this case it is 1.
Have two variables for first list and second list.
var_first = 1
var_second = 3
output = min(var_first, var_second)
pick the second element from the list where output was found.In our case it is 2
var_first = 2
var_second = 3
keeps going....
var_first = 4
var_second = 3
var_first = 5
var_second = 5
whenever both variable are same put in the third list.
third list: 5 6