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

- ZSGoldberg January 26, 2014 | Flag Reply
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;
	}

- IvgenyNovo January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how does XOR give you the missing element ?

- juny January 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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.

- ZSGoldberg January 26, 2014 | Flag
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?

- Roxanne January 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- ZSGoldberg January 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Mohit Goel February 19, 2014 | Flag
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

- Kirill January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kirill January 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 26, 2014 | Flag
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.

- sameer.careercup January 26, 2014 | Flag
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));
					}
			}
	}

- nitin466 January 27, 2014 | Flag Reply
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;
                }
            }
            Console.ReadLine();

it works

- Anonymous January 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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];
		}
		return total-numbervalue;
	}

- Anonymous January 28, 2014 | Flag
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);
	}

- gourahari.das January 28, 2014 | Flag Reply
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() ))) - Jeff January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Jeff January 29, 2014 | Flag
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);
		
	}

}

- Ravi Kumar February 20, 2014 | Flag Reply
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;
}

- Danish Shaikh (danishshaikh556@gmail.com) February 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Danish Shaikh (danishshaikh556@gmail.com) February 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sum the numbers and subtract it by 5050.

- rishi January 26, 2014 | 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