Amazon Interview Question for Interns


Country: India
Interview Type: In-Person




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

I suppose the answer should be -24 which is smaller than -23.
where as -22 is greater than -23.

- sv May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

even I was thinking the same. ans should be -24 and not -22.

- Anonymous May 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

look at it this way.. minimum no. between -23 and 24 which is not present in the array

- neo May 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How about maintaining a HashSet that covers the values that have already been encountered along with the minimal value found so far? O(n) memory and O(n) runtime:

public static int getSmallestUnfoundInInterval(int[] arr){
    if(arr == null){
        throw new NullPointerException();
    }
    if(arr.length == 0){
        throw new IllegalArgumentException();
    }
    
    //build the HashSet and get the min
    HashSet<Integer> set = new HashSet<Integer>();
    int minVal = Integer.MAX_VALUE;
    for(int i : arr){
        if(i < minVal){
            minVal = i;
        }
        set.add(i);
    }
    
    //search the HashSet for the first value counting up from the min that is NOT in the set
    while(set.contains(minVal)){
        minVal++;
    }
    return minVal;

- zortlord May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your idea of maintaining a min value makes sense, but I wonder if you actually need the set.

Simply keep track of a min value, but with the special property that this min value must be at least 2 less than the next min value.

Pseudocode:

int min = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++) {
    if (a[i] < (min-1)) {
        min = a[i];
    }
}
return min;

O(n) time, O(1) space

- JW May 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@JW

But, if you had that requirement, then changing min to a[i] would require rescanning the entire array from a[0] to a[i] to ensure that a[i] is 2 less than the next value.

- zortlord May 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ def getMissingMin(a = []): if a: min = a[0] for i in a: if i < min: min = i return min+1 else: return 0 - Anonymous May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def getMissingMin(a = []):
	if a:
		min = a[0]
		for i in a:
			if i < min:
				min = i
		return min+1
	else:
		return 0

- Anonymous May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Fails because min+1 could be within the array. IE: [-5, 1, -4, 2] would return -4 but -4 is in the array.

- zortlord May 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

since the question ask for the min value not in the list i believe the example given is wrong the answer given is -22 but it should be -24 since -24 < -23. With that said your solution would be correct if you replaced

min + 1

with

min - 1

- mlblount45 May 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please let me know if this is the answer:

def getMissingMin(a = []):
	if a:
		min = a[0]
		for i in a:
			if i < min:
				min = i
		return min+1
	else:
		return 0

- Anonymous May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please let me know if this is the answer:

{
def getMissingMin(a = []):
if a:
min = a[0]
for i in a:
if i < min:
min = i
return min+1
else:
return 0
}

- Anonymous May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It means the minimum value in range of min and max of elements.
Here is my solution.it works.

public static void main(String[] args) {
    	int[] arr = {-1,4,5,-23,24};
    	int min = Integer.MAX_VALUE;
    	int max = Integer.MIN_VALUE;
    	HashSet<Integer> set = new HashSet<Integer>();
    	for (int i =0;i<arr.length;i++){
    		if(arr[i]<min)
    			min = arr[i];
    		if(arr[i]>max)
    			max = arr[i];
    		set.add(arr[i]);
    	}
    	for(int i = min; i<=max; i++){
    		if(!set.contains(i)){
    			System.out.println(i);
    		break;
    		}
    	}
    }

- nasim May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here was a good idea to use HashSet, however the time complexity is presented for that solution not sharp, actually it should be O(N + M) where N is number of elements in array and M is offset which we have to go from min value in the array to the next omitted value if we sorted it. In some cases M could be significant bigger than N.

The following solution works guaranteed O(N). We just use one more HashSet to store potential answer to our question:

import java.util.HashSet;

/**
 * Created by sis on 5/27/15.
 */
public class CareerCup_5758677862580224 {
    public static void main(String[] args) {
        int[] a = {-1, 4, 5, -23, 24};
        int m = getNotPresentedMin(a);
        System.out.println(m);
    }

    private static int getNotPresentedMin(int[] a) {
        if (a.length == 0) {
            throw new IllegalArgumentException();
        }

        HashSet<Integer> real = new HashSet<>();
        HashSet<Integer> potential = new HashSet<>();

        for (int i = 0; i < a.length; i++) {
            real.add(a[i]);
            potential.add(a[i] + 1);
        }

        int min = Integer.MAX_VALUE;
        for (int i: potential) {
            if (!real.contains(i)) {
                min = Math.min(min, i);
            }
        }

        return min;
    }
}

- igor.s.sokolov May 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the above scenario of O(N+M) , M will always <=N as you can have only N distinct element in an array and we can check by increment the minimum value upto N times and also check for contains in hash set .Hence it is always going to be O(N).

- Raj Kamal Srivastava June 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another solution would be to use a Min heap. Store all the values in the min heap and pop the first value and then return one value less than that?
This would be O(n) space and time complexity..

- Rajeev May 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Probably use a min heap and pop the first value and return one less than that?

- Rajeev May 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CareerCup5758677862580224 {
	public static void main(String[] args) {
		int[] sampleArray = {-1,4,5,-23,24};
		int minimum = 0;
		
		System.out.println(minValue(sampleArray,minimum));
	}
	public static int minValue(int[] sampleArray, int min){
		for(int x = 0; x < sampleArray.length; x++){
			if(sampleArray[x] < min)
				min=sampleArray[x];
		}
		return min+=1;
	}
}

- N0tY0urTyp1c4lGuy May 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This program fails for input {-1,4,5,-23,-24};

Your program's output would be -23, but correct output should be -22.

- Raj May 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.List;

public class MinmumNotPresentInArray {
public static void main(String[] args) {
Integer[] input = { -1, 4, 5, -23, 24 };
System.out.println("Min 1= " + getMinimumMissingNumber(input));
input = new Integer[]{ -1, 4, 5, -23, 24 };
System.out.println("Min 2= " + getMinimumMissingNumber(input));
input =new Integer[] { 1,5,3,4,6};
System.out.println("Min 3= " + getMinimumMissingNumber(input));
input = new Integer[]{5,4,3,2};
System.out.println("Min 4= " + getMinimumMissingNumber(input));
input =new Integer[] {1,2,4,3};
System.out.println("Min 5= " + getMinimumMissingNumber(input));
input =new Integer[] {1,2,5,3};
System.out.println("Min 6= " + getMinimumMissingNumber(input));
input =new Integer[] {1,2,3,4};
System.out.println("Min 7= " + getMinimumMissingNumber(input));
input =new Integer[] {5,1,3,4};
System.out.println("Min 8= " + getMinimumMissingNumber(input));
}

private static long getMinimumMissingNumber(Integer[] input) {
List<Integer> array=new ArrayList<Integer>();
List<Integer> array1=new ArrayList<Integer>();
long min=Long.MAX_VALUE;
for (int i = 0; i < input.length; i++) {
array.add(input[i]);
array1.add(input[i]+1);
}
for (Integer iy:array1) {
if(!array.remove(iy) && min>iy.intValue()){
min=iy.intValue();
}

}
System.out.println();
if(array.size()==1){
return Long.MIN_VALUE;
}

return min;
}
}

- Vishnu May 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take a boolean array of size n say bool[]
Iterate over the number array once and find the minimum say it is k
Set bool[0] (Think it represents the minimum number in the array) to true and rest to false.
Iterate over the number array again if num[i]-k < n then set bool[num[i]-k] true.
Check index of first false index in bool array. Say the index is j.
The number is j+k

public int minNonArrayNum(num[]){
	int size = num.length;
	boolean bool[] = new boolean[size];
	bool[0] = true;
	int minimum = num[0];
	for (int i = 0 ; i < size ; i++) {
		if (num[i] < minimum) {
			minimum = num[i];
		}
	}
	for (int i = 0 ; i < size ; i++) {
		if (num[i]-minimum < size) {
			bool[num[i]-minimum] = true;
		}
	}

	for (int i = 1 ; i < size ; i++) {
		if (!bool[i]) {
			return i+minimum;
		}
	}
}

- Anonymous June 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take a boolean array of size n say bool[]
Iterate over the number array once and find the minimum say it is k
Set bool[0] (Think it represents the minimum number in the array) to true and rest to false.
Iterate over the number array again if num[i]-k < n then set bool[num[i]-k] true.
Check index of first false index in bool array. Say the index is j.
The number is j+k

public int minNonArrayNum(num[]){
	int size = num.length;
	boolean bool[] = new boolean[size];
	bool[0] = true;
	int minimum = num[0];
	for (int i = 0 ; i < size ; i++) {
		if (num[i] < minimum) {
			minimum = num[i];
		}
	}
	for (int i = 0 ; i < size ; i++) {
		if (num[i]-minimum < size) {
			bool[num[i]-minimum] = true;
		}
	}

	for (int i = 1 ; i < size ; i++) {
		if (!bool[i]) {
			return i+minimum;
		}
	}
}

- Bikash June 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why you need a HashSet if it can be done using a boolean array of size n say bool[]
Iterate over the number array once and find the minimum say it is k
Set bool[0] (Think it represents the minimum number in the array) to true and rest to false.
Iterate over the number array again if num[i]-k < n then set bool[num[i]-k] true.
Check index of first false index in bool array. Say the index is j.
The number is j+k

public int minNonArrayNum(num[]){
	int size = num.length;
	boolean bool[] = new boolean[size];
	bool[0] = true;
	int minimum = num[0];
	for (int i = 0 ; i < size ; i++) {
		if (num[i] < minimum) {
			minimum = num[i];
		}
	}
	for (int i = 0 ; i < size ; i++) {
		if (num[i]-minimum < size) {
			bool[num[i]-minimum] = true;
		}
	}

	for (int i = 1 ; i < size ; i++) {
		if (!bool[i]) {
			return i+minimum;
		}
	}
}

- bikas.rath June 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ignore my previous 2 redundant comments. I submitted the answer multiple times because of network issues. :)

- bikas.rath June 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int min()
{
	int a[] = {-1, 4, 5, -23, 24};
	int n=5;
	int min=a[0];
	for(int i=0;i<n;i++)
	{
		if(min<a[i])
			min=a[i];
	}
	return min-1;

}

- Arulrajnellai June 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def minimal_value_non_present(nums):
    min = nums[0]
    max = nums[0]

    for num in nums[1:]:
        if num < min:
            min = num
        elif num > max:
            max = num

    for e in range(min, max):
        if e not in nums:
            return e

    return None

- sisa989 June 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getSmallestNnumber(int[] arry)
	 {
		 
		    int smallest = arry[0];
            int largetst = arry[0];
           
            for(int i=1; i< arry.length; i++)
            {
                    if(arry[i] > largetst)
                            largetst = arry[i];
                    else if (arry[i] < smallest)
                            smallest = arry[i];
                   
            }
		 
		 return smallest+1;
	 }

- jollyboy June 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getSmallestNnumber(int[] arry)
{

int smallest = arry[0];
int largetst = arry[0];

for(int i=1; i< arry.length; i++)
{
if(arry[i] > largetst)
largetst = arry[i];
else if (arry[i] < smallest)
smallest = arry[i];

}

return smallest+1;
}

- jollyboy June 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and

public static int getSmallestNnumber(int[] arry)
{

int smallest = arry[0];
int largetst = arry[0];

for(int i=1; i< arry.length; i++)
{
if(arry[i] > largetst)
largetst = arry[i];
else if (arry[i] < smallest)
smallest = arry[i];

}

return smallest+1;
}

and

- jollyboy June 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array, then take the first value and subtract one.

private int findMinNotinList(Integer[] aList) {
        int result = 0;
        ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(aList));
        Collections.sort(list);
        result = list.get(0)-1;
        return result;        
    }

- Sfc June 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int getmin(int[] a) {
int result= Integer.MAX_VALUE;
Set<Integer>num= new HashSet<Integer>();

for(int i=0; i<a.length; i++){
if(!num.contains(a[i])){
num.add(a[i]);
}
}
for(int l: num){
if(l<result){
result=l;
}
}
if(result<0){
result= result+1;
}
else{
result= result-1;
}
return result;
}

- suy January 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//This can be done in O(n) time with O(1) space complexity.
public class Solution {
public static void main(String[] args){
int[] a = {-23,1,8,-22,-47,-46,-45,-44,100,200};
int answer = findMinimumNotPresentInArray(a);
System.out.println(answer);
}
private static int findMinimumNotPresentInArray(int[] a){
int answer = a[0];
for(int i=0 ; i< a.length ; i++){
if(a[i] < answer - 1 ){
answer = a[i];
}
if(a[i] == answer +1 ){
answer = a[i];
}

}

return answer + 1;
}
}

- sagar February 14, 2016 | 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