Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
A simple way will be using the second array and as u get a common element index it and increment the index..it is O(n2) but no memory complexity
int main()
{
int a[] = {0,1,2,3,1,1,0,1,0,4,5,8,1,2,3};
int b[] = {0,3,4,1,1,2,1,0,2,7,6,5,3,2};
int i,j,index = 0;
int temp;
for(i = 0 ; i < sizeof(a)/sizeof(int) ; i++)
{
for(j = index ; j < sizeof(b)/sizeof(int); j++)
{
if(a[i] == b[j])
{
temp = b[index];
b[index] = b[j];
b[j] = temp;
index++;
break;
}
}
}
for(i = 0; i < index ; i++)
printf("%d ",b[i]);
}
A simple way will be using the second array and as u get a common element index it and increment the index..it is O(n2) but no memory complexity
int main()
{
int a[] = {0,1,2,3,1,1,0,1,0,4,5,8,1,2,3};
int b[] = {0,3,4,1,1,2,1,0,2,7,6,5,3,2};
int i,j,index = 0;
int temp;
for(i = 0 ; i < sizeof(a)/sizeof(int) ; i++)
{
for(j = index ; j < sizeof(b)/sizeof(int); j++)
{
if(a[i] == b[j])
{
temp = b[index];
b[index] = b[j];
b[j] = temp;
index++;
break;
}
}
}
for(i = 0; i < index ; i++)
printf("%d ",b[i]);
}
int main()
{
int a[] = {0,1,2,3,1,1,0,1,0,4,5,8,1,2,3};
int b[] = {0,3,4,1,1,2,1,0,2,7,6,5,3,2};
int i,j,index = 0;
int temp;
for(i = 0 ; i < sizeof(a)/sizeof(int) ; i++)
{
for(j = index ; j < sizeof(b)/sizeof(int); j++)
{
if(a[i] == b[j])
{
temp = b[index];
b[index] = b[j];
b[j] = temp;
index++;
break;
}
}
}
for(i = 0; i < index ; i++)
printf("%d ",b[i]);
}
Make Hash of first array with noc(number off occurences) of each element..
- loveCoding January 17, 2012Now go through second array if hash contains element and noc>0, add that element in intersection array.
Time O(n+m)
Space O(n)