Amazon Interview Question
Quality Assurance EngineersCountry: India
Interview Type: In-Person
traverse both arrays at the same time, when you find an element in array 1 which is different or non-existant in array 2, return array1[i]. treat edge cases.
int findMissing(int a[], int b[]) {
if (a.len < b.len || b.len != a.len-1) {
return -1; // error
}
for (int i = 0; i < a.len; i ++) {
if (i == b.len) {
return a[a.len-1];
} else if (i < b.len && a[i] != b[i]) {
return a[i];
}
}
return -1; // not found
}
import java.util.HashMap;
public class FindMissingandDuplicate {
static int flag=0;
public static void main(String[] args) {
int a[]={1,3,5,6,8};
int b[]={1,5,6,8};
FindMissingandDuplicate obj=new FindMissingandDuplicate();
obj.findMissing(a,b);
if(flag==0)
System.out.println("No missing number");
// TODO Auto-generated method stub
}
private static void findMissing(int[] a, int[] b) {
// TODO Auto-generated method stub
int len1=a.length;
int len2=b.length;
HashMap <Integer,Integer> map=new HashMap<Integer,Integer>();
if(len1<len2)
{
for(int i=0;i<len1;i++)
{
map.put(a[i], 1);
}
for(int i=0;i<len2;i++)
{
if(map.containsKey(b[i]))
{
int val=map.get(b[i]) +1;
map.put(b[i], val);
}
if(!map.containsKey(b[i]))
{
flag=1;
System.out.println("Missing number is :- " + b[i]);
}
}
}
else
{
for(int i=0;i<len2;i++)
{
map.put(b[i], 1);
}
for(int i=0;i<len1;i++)
{
if(map.containsKey(a[i]))
{
int val=map.get(a[i]) +1;
map.put(a[i], val);
}
if(!map.containsKey(a[i]))
{
System.out.println("Missing number is :- " + a[i]);
}
}
}
}
}
import java.util.HashMap;
public class FindMissingandDuplicate {
static int flag=0;
public static void main(String[] args) {
int a[]={1,3,5,6,8};
int b[]={1,5,6,8};
FindMissingandDuplicate obj=new FindMissingandDuplicate();
obj.findMissing(a,b);
if(flag==0)
System.out.println("No missing number");
// TODO Auto-generated method stub
}
private static void findMissing(int[] a, int[] b) {
// TODO Auto-generated method stub
int len1=a.length;
int len2=b.length;
HashMap <Integer,Integer> map=new HashMap<Integer,Integer>();
if(len1<len2)
{
for(int i=0;i<len1;i++)
{
map.put(a[i], 1);
}
for(int i=0;i<len2;i++)
{
if(map.containsKey(b[i]))
{
int val=map.get(b[i]) +1;
map.put(b[i], val);
}
if(!map.containsKey(b[i]))
{
flag=1;
System.out.println("Missing number is :- " + b[i]);
}
}
}
else
{
for(int i=0;i<len2;i++)
{
map.put(b[i], 1);
}
for(int i=0;i<len1;i++)
{
if(map.containsKey(a[i]))
{
int val=map.get(a[i]) +1;
map.put(a[i], val);
}
if(!map.containsKey(a[i]))
{
System.out.println("Missing number is :- " + a[i]);
}
}
}
}
}
import java.util.HashMap;
public class FindMissingandDuplicate {
static int flag=0;
public static void main(String[] args) {
int a[]={1,3,5,6,8};
int b[]={1,5,6,8};
FindMissingandDuplicate obj=new FindMissingandDuplicate();
obj.findMissing(a,b);
if(flag==0)
System.out.println("No missing number");
// TODO Auto-generated method stub
}
private static void findMissing(int[] a, int[] b) {
// TODO Auto-generated method stub
int len1=a.length;
int len2=b.length;
HashMap <Integer,Integer> map=new HashMap<Integer,Integer>();
if(len1<len2)
{
for(int i=0;i<len1;i++)
{
map.put(a[i], 1);
}
for(int i=0;i<len2;i++)
{
if(map.containsKey(b[i]))
{
int val=map.get(b[i]) +1;
map.put(b[i], val);
}
if(!map.containsKey(b[i]))
{
flag=1;
System.out.println("Missing number is :- " + b[i]);
}}}
else
{
for(int i=0;i<len2;i++)
{
map.put(b[i], 1);
}
for(int i=0;i<len1;i++)
{
if(map.containsKey(a[i]))
{
int val=map.get(a[i]) +1;
map.put(a[i], val);
}
if(!map.containsKey(a[i]))
{
System.out.println("Missing number is :- " + a[i]);
}}}}}
import java.util.HashMap;
public class FindMissingandDuplicate {
static int flag=0;
public static void main(String[] args) {
int a[]={1,3,5,6,8};
int b[]={1,5,6,8};
findMissing(a,b);
if(flag==0)
System.out.println("No missing number");
// TODO Auto-generated method stub
}
private static void findMissing(int[] a, int[] b) {
// TODO Auto-generated method stub
int len1=a.length;
int len2=b.length;
HashMap <Integer,Integer> map=new HashMap<Integer,Integer>();
if(len1<len2)
{for(int i=0;i<len1;i++){map.put(a[i], 1);}
for(int i=0;i<len2;i++)
{if(map.containsKey(b[i]))
{ int val=map.get(b[i]) +1;
map.put(b[i], val);
}if(!map.containsKey(b[i]))
{ flag=1;
System.out.println("Missing number is :- " + b[i]); }}}
else{for(int i=0;i<len2;i++){map.put(b[i], 1);}
for(int i=0;i<len1;i++)
{if(map.containsKey(a[i])){
int val=map.get(a[i]) +1;
map.put(a[i], val);}
if(!map.containsKey(a[i]))
{System.out.println("Missing number is :- " + a[i]);}}}}}
package Test;
import java.util.HashSet;
import java.util.Set;
public class ABCD {
public static void main(String[] args) {
int a[]={1,2,3,4,5,6,7};
int b[]={1,3,4,5,6,7};
Set<Integer> set1=new HashSet<Integer>();
Set<Integer> set2=new HashSet<Integer>();
for(int num:a)
set1.add(num);
for(int num:b)
set2.add(num);
set1.removeAll(set2);
System.out.println(set1);
}
}
It seems that no one has thought of the solution using bitwise tricks. :-) I like the solution with sums, but it has the obvious problem that it can overflow; sure, we could mitigate that with clever interleaving, but that complicates the solution.
First recall that n XOR n = 0 for any integer n. More generally, if we XOR an integer with itself an even number of times, we'll always get zero.
Now the two arrays contain exactly the same elements with exactly the same multiplicity, except for the missing element. Thus all elements---except the missing one---have even multiplicity. It follows that if we XOR all the elements---from both arrays---they all cancel out, except the element with odd multiplicity, which is the element we're looking for.
In C++, you could do this as follows.
int find_missing(const std::vector<int>& a, const std::vector<int>& b) {
int missing = 0;
for (const auto& num : a) missing ^= num;
for (const auto& num : b) missing ^= num;
return missing;
}
C# code:
//Time Complexity: O(n)
public static int Findmissing(int[] A1, int[] A2)
{
Dictionary<int, int> D = new Dictionary<int, int>();
for (int i = 0; i < A1.Length; i++)
{
if (D.ContainsKey(A1[i]))
D[A1[i]]++;
else
D[A1[i]] = 1;
}
for (int i = 0; i < A2.Length; i++)
{
if (D.ContainsKey(A2[i]))
D[A2[i]]++;
else
D[A2[i]] = 1;
}
int missing=0;
foreach (KeyValuePair<int, int> pair in D)
{
if (pair.Value == 1)
{
missing = pair.Key; // Found
break;
}
}
return missing;
}
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
public class ArrayUtil {
private static void checkPreConditions(int arr1[], int arr2[]) {
if (Objects.isNull(arr1) || Objects.isNull(arr2)) {
throw new NullPointerException("Arrays Shouldn't be null");
}
if (arr1.length != arr2.length + 1) {
throw new IllegalArgumentException("Illegal Arguments");
}
}
public static int approach1(int arr1[], int arr2[]) {
checkPreConditions(arr1, arr2);
int data = arr1[0];
for (int i = 1; i < arr1.length; i++) {
data ^= arr1[i];
data ^= arr2[i - 1];
}
return data;
}
public static int approach2(int arr1[], int arr2[]) {
checkPreConditions(arr1, arr2);
int sum1 = arr1[0], sum2 = 0;
for (int i = 1; i < arr1.length; i++) {
sum1 = sum1 + arr1[i];
sum2 = sum2 + arr2[i - 1];
}
return sum1 - sum2;
}
public static int approach3(int arr1[], int arr2[]) {
checkPreConditions(arr1, arr2);
Set<Integer> hashSet = new HashSet<>();
for (int i : arr1) {
hashSet.add(i);
}
for (int i : arr2) {
if (hashSet.contains(i))
hashSet.remove(i);
}
for (int missed : hashSet)
return missed;
return -1;
}
}
package com.my.algo.problemsolving;
public class MissingElement {
public static void main(String[] args) {
int[] a1 = {1,2,3,4,5,6,7};
int[] a2 = {1,2,4,5,6,7};
int sum1 = 0; int sum2 = 0;
if (a1.length == a2.length) {
System.out.println("Both arrays are identical.. not missing");
System.exit(0);
}
for (int i = 0; i < a1.length; i++) {
sum1 += a1[i];
}
for (int i = 0; i < a2.length; i++) {
sum2 += a2[i];
}
if (a1.length > a2.length)
System.out.println("Missing element : " + (sum1 - sum2));
else
System.out.println("Missing element : " + (sum2 - sum1));
}
}
public class MissingElement {
public static void main(String args[]) {
int[] arr1 = { 1, 2, 3, 4, 6, 7, 8, 9 };
int[] arr2 = { 1, 2, 3, 6 };
System.out.println("The missing elements are: ");
for (int i = 0; i < arr1.length; i++) {
if (MissingElement(arr1[i], arr2)) {
} else {
System.out.println(arr1[i]);
}
}
}
private static boolean MissingElement(int arr1, int[] arr2) {
for (int i = 0; i < arr2.length; i++) {
if (arr2[i] == arr1) {
return true;
}
}
return false;
}
}
public void missingElement(Integer[] a, Integer[] b){
List<Integer> ls = Arrays.asList(a);
List<Integer> ls1 = Arrays.asList(b);
Set<Integer> set1 = new HashSet<Integer>(ls);
set1.removeAll(ls1);
Iterator<Integer> iths = set1.iterator();
while(iths.hasNext()){
System.out.println(iths.next());
}
}
I could think of 3 options below:
1) The one user Tal suggested at first --> sum of Array1 - Sum of Array2
2) Using linear search to go through each element of both the arrays and find what's missing
3) Another linear approach, but this time convert the arrays to ArrayList and use contains function to find whether the element is exist or not
- Tal May 07, 2016