Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

My understanding of the problem is that there is an unsorted array containing 98 ints between 1 and 100, thus missing one value in that range.

The sum of numbers 1 through 100 is equal to (101*100)/2 = 5050
If we take the sum of the numbers in our array and subtract it from 5050 the result should be the one missing int.

Easy enough to code but I'm on mobile

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

One possible solution is the sum solution which was already suggested. The problem with this solution is that for a general n (n=100 in the original problem), calculating the sum may cause overflow (for example n > sqrt(Integer.MAX_VALUE)).

Another solution is to use the xor operator. Recall that xor is commutative, associative and also satisfies the following:
1. a xor a = 0
2. 0 xor a = a

Using these observation, it's easy to see the following:
missing_element = 1 xor 2 xor ... xor n xor arr[0] xor arr[1] xor ... xor arr[n-2] (the array has n-1 elements).

``````public static int findMissing(int[] arr) throws NullPointerException {
if (arr==null){throw new NullPointerException();}

int res = 0;
for (int i=0;i<arr.length;i++){res^=arr[i]^(i+1);}
res^=(arr.length+1);

return res;
}``````

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

how does XOR give you the missing element ?

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

This is really interesting! To the question above, you'll be xoring every number in the array as well as every index in the array.

Eg if the missing element is 4, you'll be evaluating the expression that includes 2 copies of each number except 4,of which there will be only one.

That is, (a xor a) xor (b xor b) xor (c xor c)... xor MISSING_NUMBER. This is equivalent to 0 xor 0 xor 0...xor MISSING_NUMBER, Which is equivalent to the missing number itself.

Obviously this solution also fails if there are duplicates in the array, we would have to know that the set of indices and set of values are the same.

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

``@ZSGoldberg "Obviously this solution also fails if there are duplicates in the array, we would have to know that the set of indices and set of values are the same."``

You are right about solution failing for duplicates in array.
But we do not necessary need to know that set of indices and set of values are same. So 1 xor 20 xor 1 will still give you 20, since xor is associative, no order needed be maintained like 1 xor 1 xor 2 xor 2 .... etc.
Hope that's clear?

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

@Roxanne - yep! Tried to capture that by saying the "the set of" indices and "the set of values" are the same. 'Sets' being lists not in any particular order

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

This solution works great if there are no duplicate values in the array.
example:
if we have missing element 5 and 4 occur twice then result has to be 5 (as expected)
but it will be 4(from array) XOR 4 (from array) XOR 4 (from Index) XOR 5 (from Index)
Now result will be from = 4 (from Index) XOR 5 (from Index) .. as both 4 from array will cancel mutual effect.

to solve this situation we can take one more array of bool(Occupancy Array). What ever value we get from array we go to that
index of occupancy array and mark it as occupied (true). After traversal of all value ... we traverse this occupancy array ...
the index which has false value will be our result.

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

it mean we have an array with 98 elements; and every cell has a unique value from 1 to 100

1. sort array
2. apply binary search to go over array and cheek values. So, array[49] must be equal to 50, if it 's 49 - then check left part, it it's 50 - check right part

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

I mean, need to check that array[index] == index + 1; and make next index = index/2;

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

Would be in efficient to sort! The below answers are better! can be done in O(n).

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

what if you dont have array size as 98. i mean to say what if array has duplicate elements too.

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

The solution suggested above:
(Sum of natural number from 1 to 100) - (sum of all the elements present in the given array) will give the missing number and infact smart way too :)
I can also think of another solution just let me know if this is efficient enough or not :

Sort the array in increasing order(if not already given in sorted fashion). Then the difference of any two consecutive number should be 1, wherever its not that is our culprit .

Java code for the same:

``````public class FindMissing {
public static void main(String[] args) {

int array[] = { here sorted input array will come};

for(int i = 0; i<array.length-1; i++){
if(array[i+1]-array[i] !=1)

System.out.println("The missing number is: " + (array[i] + 1));
}
}
}``````

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

``````int[] dizi = new int[100];
for (int i = 1; i < 101; i++)
{
dizi[i-1] = i;
}
//dizi[69]=70
//delete it from array to see is it working
dizi[69] = 0;
for (int i = 1; i < 100; i++)
{
if (dizi[i]-dizi[i-1]!=1)
{
Console.WriteLine(i+1);
break;
}
}

it works

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

``````public int findTheNumbers(int[] numbers)
{
int total = 0;
int numbervalue = 0;
int i;

for (i=1;i<=10;i++)
{
total+=i;
}
for (i=0;i<numbers.length;i++)
{
numbervalue += numbers[i];
}
}``````

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

1. First sum up all numbers from 1 thru 100. Lets say its SUM.
2. Loop thru the input array. Substract each item from SUM.
You will have the missing number in SUM finally.

``````public static void main(String[] args) {
int input[] = { 2, 3, 4, 5, 6, 7, 8, 9, 28, 29, 30, 10, 11, 12, 13, 18,
44, 45, 74, 75, 76, 77, 21, 22, 78, 79, 80, 19, 20, 23, 24, 25,
26, 27, 31, 1, 32, 33, 34, 35, 36, 50, 51, 52, 53, 62, 63, 64,
70, 71, 85, 86, 87, 54, 37, 95, 96, 92, 93, 38, 99, 100, 83,
84, 17, 90, 91, 41, 39, 40, 97, 46, 66, 67, 68, 69, 47, 48, 49,
14, 15, 16, 72, 73, 98, 42, 43, 81, 82, 60, 61, 88, 89, 94, 55,
56, 57, 58, 59 };

int sum = (100*101)/2;

for (int i : input) {
sum -= i;
}

System.out.println("Missing number: " + sum);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
Here is a solution with sets {{{ def missing_val(unsorted_array): input_set = set(unsorted_array) input_min = min(unsorted_array) input_max = max(unsorted_array) test_set = set([x+1 for x in range(input_min,input_max)]) for x in test_set.difference(input_set): return test_set.difference(input_set).pop() )))
Comment hidden because of low score. Click to expand.
0

sorry forgot the trippple action

``````def missing_val(unsorted_array):
input_set = set(unsorted_array)
input_min = min(unsorted_array)
input_max = max(unsorted_array)
test_set = set([x+1 for x in range(input_min,input_max)])
for x in test_set.difference(input_set):
return test_set.difference(input_set).pop()``````

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

``````public class FindMissingNumber {

public static void main(String[] args) {

findDuplicateNumber(10);
}

public static void findDuplicateNumber(int num)
{
int sum=10*(11)/2;

int sum1=1+2+3+5+6+7+8+9+10;

int num1=sum-sum1;
System.out.println(num1);

}

}``````

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

the solution of the missing number is

``````public int missin (int num , int[] array)
{
int missingNum = ((Array.length(Array.length +1))/2) - (Sum of all elements in the array);
return missingNum;
}``````

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

sorry it is
int missingNum = (Array.length((Array.length +1)/2)) - (Sum of all elements in the array);

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

sum the numbers and subtract it by 5050.

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.