Amazon Interview Question for Testing / Quality Assurances

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

"Missing" word indicates that the array has numbers from 1 to 100 (which may be out of sequence though). Add all the elements in the array and subtract the sum from 5050.

(100 * 101)/2 = 5050

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

I agree

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

Please check my code:

``````#include<stdio.h>

int findmissing(int a[],int n)
{
int i=0,s=0;
for(i=0;i<n-1;i++)
{
s = s^a[i]^(i+1);
}
s = s^n;
return s;
}

int main()
{
int a[]={5,4,1,3};

printf(" %d ",findmissing(a,5));
return 0;
}``````

Feedbacks are welcome.

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

Your variable names aren't meaningful. Meaningful variable names make code more readable.

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

What if an element is missing and instead we have a duplicate value. In that case your sol doesn't work.

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

The question doesn't specify that.

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

Thats Correct ... I assumed missing slot would have 0.

Then solution would require detecting duplicate value. Another array of size 100 can be used ... traverse first array and use values as indices for the other array and mark those slots. If we encounter already marked slot, duplicate is found. Using this value and difference above, missing value can be detected.

missing value = duplicate value + difference

Solution looks a bit inefficient ... any suggestions?

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

Use an array C of size 100 initialized to all zeros... Go through original array, for every element x, increment C[x] by 1. In the end, the index in C having value 0 is the missing value, and the index with value greater than 1 is the duplicate value.

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

how can we assume that the array would have values from 1-100.. cant they be any range of 100 consecutive nos e.g. 321-420 etc?

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

yes, it could be any range of width 100, in which case i guess we would have to take the minimum value in the original array (found in O(n) time), and use it as an offset to subtract from the value to obtain the corresponding index in the array C mentioned above. so for the range 321-420, the value 400 would correspond to index 400-321 = 79.

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

The above solutions require another array of equal size. Suppose we could modify the array. Just need to perform a sort and find the duplicate value using two pointers.

Would turn out to be O(nlog n) though.(Assuming we use quick sort or merge sort.

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

hi we can do this using xor,

for(i=0; i < 100;i++)
num = num ^ array[i] ^ (i+1);

after this num = xor of all array values and numbers from 1 to 100
xor of duplicate numbers becomes zero so
so num becomes duplicatenumber ^ 100

so now xor the num with 100 we will get duplicate number.

num = num ^ 100;

so num is the required output.

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

man..this is just an array of fixed numbers so we can sort it in O(n) and with no extra memory and then the problem is solved....

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

sorting is O(nlgn)

chaitu, your algorithm has a problem:
after the iterations, num = (duplicatenumber)^(its'position)

so it does not work

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

if the numbers are any 10 consecutive numbers, then just take the remainder of the number/100 as the index to the array.

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

In case say x is the missing element and is in turn replaced by y (for say numbers in the range 1 to N)
Let A be the original series from 1 to N
Let B be the series as described above

Summation(A) - Summation(B) = y-x
Product(A) / Product(B) = x/y

Based on these 2 equations, you can obtain x and y (the missing and the duplicate element respectively)

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

I meant the series A contains no duplicate/missing values..

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

the array can be sorted in O(n) for consecutive 100 numbers. ie; start scanning from start.take the number at first position and swap number with the element at corresponsing index.if number at first position is 55.and number at 55th position in 76. then swap 55 and 76.this way we send the number to the index of same value.one scan and array is sorted.once sorted one more scan to compare adjacent numbers to give missing one

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

Insted of calculating
1*2*....*100
we can calculate 1*1+2*2... 100*100
because

n! > 1*1+2*2 ....n*n for n>4

so n! will take data type with larger range

so we have
s1=SUM(A*A)-SUM(B*B)=x*x-y*y=(x-y)(x+y)..1
and
s2=SUM(A)-SUM(B)=(x-y) ..2

dividing 1 by 2 we have

x+y= s1/s2 ..3

by 2 & 3rd eqution we find x and y

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

but how do we map x and y to duplicate and missing element. for that again we have to scan through the array for the occurance?

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

i think chaitu's sol is the best one but there can be one optimization-
int num = 100(initialization)
then after processing,we will get the odd no. directly.

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

If missing number is not filled as zero and some other number is duplicated then:

let the missing number be x
let the duplicated number be y

Existing product = P1
Actual product of N numbers = P2

Both these products have atleast a component common which is the product of the remaining n-1 numbers say that is P
therefore P1 = P * x
and P2 = P * y

here P is the GCD of P1 and P2.
Thus find the GCD of P1 and P2 and divide P1 and p2 by it and get x and y.

If the missing number is replaced by zero then P2 would be zero. In that case use the summation method discussed above

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

By GCD I meant Greatest common divisor

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

ENJOY!!!

Assumption : Array starts from 1 else find the min and work acc.

int[] a = {1,2,3,3,5};

int sum = 0;
int prodsum = 0;
int actualsum = 0;
int actualprodsum = 0;

for (int i =0; i< a.length; i++)
{
sum = sum + a[i];
prodsum = prodsum + (a[i] * a[i]);

int j = i+ 1;
actualsum = actualsum + j;
actualprodsum = actualprodsum + (j * j);
}

int repeated = 0;
int missing = 0;
if(sum != actualsum)
{
int m = sum - actualsum;
repeated= ((prodsum - actualprodsum) + (m * m))/(2*m) ;
missing = actualsum - sum + repeated ;
}

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

Excellent. but i think there was a little mistake in your calculation for the missing
missing = (repeated - 2*m)/2

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

Use bitvector.
1. insert numbers as indexes of bitvector = O(n)
2. read for missing indexes = O(n)
O(n) + O(n) = O(n)

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

the problem explicitly says "all numbers between 1 and 100 except one missing" in an array of length 99. How can we have duplicated numbers? How can the numbers be some other consecutive numbers?@_@

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

Thank you, Chaos, for for the moment of clarity. I was going to point out the same comment until I saw yours.

Many of the responses above make me want to point out something crucial in any engineering environment... before you answer a question, make sure you understand the problem and all the information you have.

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

idealSum = n*(n+1)/2
actualSum = iterate and find sum
diff = idealSum - actualSum
culprit = n-diff

here culprit is the missing/duplicate or any value that shud not be there in the array.

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

"all the numbers between 1 and 100, except for one number that has been removed"

Sort the array then Iterate through, subtracting each element from the previous element, testing the difference. When the difference == 2, return the current minuend-1

This works for arrays of n size.

There are probably more elegant ways to do it, but the problem states a 99-element array which is so small that it renders performance considerations negligible.

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

Here's the implementation in Ruby (and why I love Ruby ):)

``````#!/usr/bin/env ruby

#create array
complete_array=*(1..100)
element_to_remove = rand(max=100)
incomplete_array = complete_array
incomplete_array.delete(element_to_remove)

#Find missing value
last = 0
incomplete_array.sort.each do |value|
diff = value - last
if diff == 2
puts value-1
else
last = value
end
end``````

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

Based on chaitu's idea

``````#include<stdio.h>
int main()
{
int arr[10],num[10],pos;
for (int i=1;i<=10;i++)
arr[i-1]=i;
arr[7]=1;

for(i=0;i<10;i++)
num[i]=arr[i]^i+1;

for(i=0;i<10;i++)
if(num[i]!=0)
pos=i;

printf("%d",arr[pos]);
}``````

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

By reading the question, i can assume that there are no duplicate values present , but there is a question whether the array contain the numbers in sequential form (1,2,3,4,5...) or they are arranged in random form (9,8,3,50...) ?

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

public int findMissingNum(int[] a)
{
int[] b= new int[100];
int r =0;
for (int i =0;i<99;i++)
r^=a[i];
for (int i=0;i<100;i++)
{
b[i] = i+1;
r^=b[i];
}
return r;

}

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

One of the easiest approaches to the above problem is to use the XOR operator to find out the missing number in the array from 1 to any number (here 100), taking XOR will lead to the elimination of the repeated integers which are present in the array and from 1 to n, thus printing the result.

Implementation:

#include<bits/stdc++.h>
using namespace std;
int findfirstrepeatedelement(int arr[], int n){
int x1 = arr[0];
int x2 = 1;
for(int i = 1; i < n; i++)
x1 = x1 ^ arr[i];
for(int i = 2; i <= n + 1; i++)
x2 = x2 ^ i;
return (x1 ^ x2);
}
int main()
{
int a[] = {1, 2, 4, 5, 6};
int miss = findfirstrepeatedelement(a, 5);
cout << miss;
return 0;
}

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

For solving the above algorithm we need to first take the xor of all the numbers from 1 to 100 and then take the xor of all the array elements and then at the end collectively take the xor of both the numbers.

Implementation:

``````#include<bits/stdc++.h>
using namespace std;
int findmissing(int arr[]){
int array_xor = arr[0];
int number_xor = 1;
for(int i = 2; i <= 100; i++)
number_xor = number_xor ^ i;
for(int i = 1; i < 100; i++)
array_xor = array_xor ^ arr[i];
return number_xor ^ array_xor;
}
int main(){
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100};
cout<<findmissing(arr)<<endl;
return 0;``````

}

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.