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

- Prakash January 29, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree

- Amit December 07, 2012 | Flag
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.

- ananthakrishnan.s.r June 10, 2011 | Flag Reply
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.

- Rogue_Leader February 03, 2012 | Flag
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.

- vatson January 29, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The question doesn't specify that.

- Rogue_Leader February 03, 2012 | Flag
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?

- Prakash January 30, 2006 | Flag Reply
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.

- whatif March 19, 2006 | Flag Reply
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?

- ppt April 15, 2006 | Flag Reply
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.

- whatif April 15, 2006 | Flag Reply
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.

- Ravs October 10, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- chaitu December 27, 2006 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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....

- vaibhav March 29, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorting is O(nlgn)

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

so it does not work

- lvv May 24, 2007 | Flag
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.

- shawshank January 26, 2007 | Flag Reply
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)

- Kaushik March 02, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kaushik March 02, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- pvsohan March 18, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ravi Kant Pandey March 28, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Gajanan April 17, 2007 | Flag
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.

- aaska's_hub May 16, 2007 | Flag Reply
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

- Jacks July 21, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

By GCD I meant Greatest common divisor

- Jacks July 21, 2007 | Flag Reply
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 ;
}

- TheGreatOne September 18, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kevin January 17, 2008 | Flag
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)

- zdmytriv January 28, 2008 | Flag Reply
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?@_@

- chaos January 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- aswietlicki January 08, 2011 | Flag
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.

- Paras December 19, 2010 | Flag Reply
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.

- Rogue_Leader February 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rogue_Leader February 03, 2012 | Flag
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]);
}

- Rohith Shenoy March 04, 2012 | Flag Reply
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...) ?

- Hex August 22, 2012 | Flag Reply
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;

}

- Anonymous November 06, 2013 | Flag Reply
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;
}

- swapnilkant11 June 06, 2019 | Flag Reply
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;

}

- swapnilkant11 July 20, 2019 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More