Microsoft Interview Question Software Engineer in Tests
You really should think before writing and confusing people's minds.
At least check your method with a simple example.
In your case, even without checking with an example,
one can find out that this is INCORRECT since
you are supposed to find the element in the first array that is NOT in the second array. So the result should be independent of the element(s) which is in the second array but NOT in the first array. Please tell me, by XOR'ing every element in both arrays, how can that be satisfied?
The XOR solution, as Anirvana mentioned, works perfectly for this problem with following assumption:
1. no duplicates elements in both array.
2. only one element is missing
3. the missing element is only replace by 0;
the sample inputs meet all these 3 assumptions.
And here is my code:
int Find_Missing(vector<int> &array1, vector<int> &array2)
{
int xor = 0;
vector<int>::size_type i;
for (i =0; i < array1.size(); ++i)
{
xor ^= array1[i];
}
for (i =0; i < array2.size(); ++i)
{
xor ^= array2[i];
}
return xor;
}
But I am not going to tell you why it works, since generally you should be polite especially when you don't know something.
And I also like to cite your words:
"You really should think before writing and confusing people's minds. "
1. Take the sum of all the elements of the first array in O(n)
2. Take the sum of all the elements of the second array in O(n)
3. Subtract the bigger one from the smaller one and then thats the number.
What about if there are no numbers match. Example: array1 = {1, 2, 3, 4, 5} and array2 = {6, 7, 8, 9, 10}. I guess the Triton's answer is correct.
Quesion says "which" number "is" => it is talking about single number. Hence Pallav is correct.
@jctechsan :
Take mod of the difference.
Sort both arrays. Use 2 pointers, move them by 1 each time till Pointer1 value != Pointer2 value. That is the missing number
but if memory is a concern(no hashtable):
1.then sort arr1(index is i) and arr2(index=j)
2. while (i<arr1.length && j< arr2.length)
if arr1[i]== arr2[j] then i++, j++
if arr1[i]>arr2[j] then j++
if arr1[i]<arr2[j] then print arr1[i] and i++;
time complexity: O(nlogn+mlogm+m or n)
Please comment
Sort array2
Now binary search for every element in array1
Time complexity : N(log M) + MLogM => (N+M)logM
N = no of elements in array1
M = No of elements in array2
1. Take the first array as row, we name this array as A,
2. The second one as column, we name this array as B
3. we can make an m*n matrix S, S[i][j] is equal to 1 if A[i] = B[j], for giving two arrays, we can make following matrix:
0 0 1 0 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 1
5. check each row to see if it doesn't contain 1, the element in Array A corresponding this row is not present in the second array
package test;
import java.util.HashSet;
import java.util.Set;
public class ValueNotPresentInsecondArray {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={1,2,3,4,5};
int b[]={2,3,1,0,5};
Set temp=new HashSet();
for(int i=0;i<a.length;i++)
{
for(int j=0;j<b.length;j++)
{
if(a[i]==b[j])
{
temp.add(a[i]);
System.out.println(a[i]+" present");
}
}
}
for(int i=0;i<a.length;i++)
{
if(!temp.contains(a[i])){
System.out.println(a[i]+"does not present");
}
}
}
}
#include<conio.h>
#include<iostream.h>
void main()
{int i,j,n,a[10],b[10],flag=1,c;
clrscr();
cout<<"enter number of elements\n";
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
cout<<"enter elements for the second array";
for(i=0;i<n;i++)
cin>>b[i];
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
{ if(a[i]!=b[j])
flag=0;
}
c=a[i];
break;
}
if(flag==0)
cout<<"element not present in the second array is "<<c;
getch();
}
#include<conio.h>
#include<iostream.h>
void main()
{int i,j,n,a[10],b[10],flag=1,c;
clrscr();
cout<<"enter number of elements\n";
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
cout<<"enter elements for the second array";
for(i=0;i<n;i++)
cin>>b[i];
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
{ if(a[i]!=b[j])
flag=0;
}
c=a[i];
break;
}
if(flag==0)
cout<<"element not present in the second array is "<<c;
getch();
}
i simple solution if there aren't any duplicates and you are finding the unique element in the first array
public static void main(String[] args) {
int[] a = new int[] { 1,2,3,4,5,7 }; // {1,3,5,7,11}
int[] b = new int[] { 2,3,1,0,5 }; // 19 {1,3,5,9}
findNumber(a, b);
}
public static void findNumber(int[] a, int[] b) {
Arrays.sort(a);
Arrays.sort(b);
int n1 = a.length;
int n2 = b.length;
int temp = -1;
int i = 0;
int j = 0;
while (i < n1 && j < n2) {
if (a[i] > b[j]) {
j++;
} else if (a[i] < b[j]) {
System.out.print(a[i] + " ");
i++;
} else {
i++;
j++;
}
}
while (i < n1) {
a[i] = a[i];
System.out.print(a[i]);
i++;
}
}
#include<stdio.h>
#include<conio.h>
void main()
{
int a[]={1,2,7,4,6},b[]={2,3,0,1,5};//we can give any distinct value to a or b,
int i,j,k;
int flag=0;
clrscr();
for(i=0;i<5;i++){
for(j=0;j<5;j++){
if(a[i]==b[j]){
b[j]=b[j+1];
b[j+1]='\0';
}
}
}
for(i=0;i<5;i++)
{
if(b[i]!=0){
printf("%d",b[i]);
flag++;
}
}
if(flag==0)
printf("%d",flag);
getch();
}
visit first array push all the numbers into the hash..
visit second array check if they exist in hash...
0 not in the hash,will u return it?
they want those in array 1 while not in array 2
NOT
those in array2 not in array 1
Take XOR of binary equivalents of all the numbers in 2 arrays, then complement the result and get its decimal equivalent and you have the answer :)
- Anirvana August 04, 2010