## Amazon Interview Question for Interns

• 0

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.

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

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

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

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

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;
}
}

//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;``````

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

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

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

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

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

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

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

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

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

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

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
}

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];
}
for(int i = min; i<=max; i++){
if(!set.contains(i)){
System.out.println(i);
break;
}
}
}``````

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++) {
}

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

return min;
}
}``````

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

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

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

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?

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;
}
}``````

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

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

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

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++) {
}
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;
}
}

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;
}
}
}``````

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;
}
}
}``````

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;
}
}
}``````

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

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

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;``````

}

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

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;
}``````

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;
}

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

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;
}``````

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])){
}
}
for(int l: num){
if(l<result){
result=l;
}
}
if(result<0){
result= result+1;
}
else{
result= result-1;
}
return result;
}

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};
}
private static int findMinimumNotPresentInArray(int[] a){
for(int i=0 ; i< a.length ; i++){
if(a[i] < answer - 1 ){
}
}

}

}
}

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

Instead of finding the minimum number of the given array and then finding the minimum not present in the array, one can find the maximum number of the given array and flip to negative.

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.