Amazon Interview Question for Quality Assurance Engineers

• 0

Country: India
Interview Type: In-Person

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

``````findMissing(int a[],int b[]){ //O(n)
return sum(a)-sum(b);
}``````

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

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

}``````

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

Why not XOR all the elements of both arrays? a ^ a = 0, so the only item which is left out is the missing element.

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

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

}

}

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

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

}

}``````

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

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

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

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

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

If the question is only about one element missing in one of the array then
probably just add two arrays to s1, s2. Let us say l1, l2 is length of both arrays respectively. Now if l1>l2 then s1-s2 gives exact element.

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

2 methods: add all elements from array1 and array2 separately, then subset act the sums. Second method: XOR all elements array1 and array2 separately, then XOR them together

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

Quick Solution

``````private static int FindMissingElement(int[] arr1, int[] arr2)
{
int sum1 = arr1.Sum();
int sum2 = arr2.Sum();

return (sum1 > sum2 ? sum1 - sum2 : sum2 - sum1);
//return Math.Abs(sum1 - sum2);
}``````

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

``````#include <stdio.h>
int a[]={1,3,5,6,8};
int b[]={1,5,6,8};

int main()
{
int i,j;
for(i=0;a[i]!=0x00;i++)
{
int missing =1;
for(j=0;b[j]!=0x00;j++)
{
if(a[i]==b[j])
missing=0;
}
if(missing == 1)
printf("%d",a[i]);
}
return 0;
}``````

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

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

for(int num:b)

set1.removeAll(set2);
System.out.println(set1);

}

}``````

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

#include<stdio.h>
int main()
{
int arr[]={1,2,3,4,5,6};
int arr1[]={1,3,4,5,6};
int i=0;
int j=0;
int k=1;
int ans=0;
for(i=0;i<6;i++)
{
if(k==0)
{
printf("%d\n",ans );
break;
}
for(j=0;j<5;j++)
{
if(arr[i]==arr1[j])
{
k=1;
break;
}
else
{
ans=arr[i];
k=0;
}
}
}
}

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

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

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

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

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

For a duplicate array:

``````public static int Findmissing2(int[] A1, int[] A2)
{

for (int i = 0; i < A2.Length; i++)            //Since second array is a copy
{
if (A1[i] != A2[i])
return A1[i];
}

return A1[A1.Length-1];
}``````

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

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

for (int i : arr2) {
if (hashSet.contains(i))
hashSet.remove(i);
}

for (int missed : hashSet)
return missed;

return -1;
}
}``````

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

In Python, we can use set() to get answers.
a = [1,2,3,4,5,6,7]
b = [1,3,4,5,6,7]

print set(a) - set(b)

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

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

}

}``````

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

binary search is actually a good solution
check the mid number is the array, say we find 5. If it should be 4, then we know that the missing number is on the left. If it's should exactly 5, then the missing number is on the right.

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

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

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

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

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

Python solution

for i in array1:
if i not in array2:
print i

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

2

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use Binary Search O(log n) time complexity and O(1) auxiliary space complexity.

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.