Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
For the first solution, do you mean the auxiliary array can be of the size at most length of given array? I think that much should be sufficient. And look up the first missing. Ignore 0th element.
just one small bug for second solution, for sorted array -1 3 4 5,
the missing min positive int is 1. so you have to add an if before your code: if(array[i]>0 && array[i-1]<=0 && array[i]!=1) return 1;
so what i get from above is:
- first traverse the array, get number of positive elem = N.
- have an aux array of size = N,
- traverse the original array, mark all the positive numbers, which are less than N
- traverse aux array, return first unmarked position
Hi nice solution. Can u plz help me in understanding this q in more better way. m jst confuse abt edge cases. wot will be ans if 1. all zero. 2. all negetive. 3. all continous- 1,2,3,4,5 like this.
thanks
Hi, the brother upstairs, I can help you resolve these cases:first, if all zero, return 1 as the missing minimum positive; second if all the numbers are negative, also return 1 as the missing minimum positive, third, if all the numbers are like this, in my opinion this topic will missing its raw intent and I think you have no need to consider this case.
@Franky ... the space require will be O(N) where N is the largest number in the array.
So if the array have large numbers (1,-2 , 20000, 5, 4000,0, -3,8000000) then the amount of space which will be wasted in creating the auxiliary array will be huge as in this case the auxiliary array would comsume 8000000*int_size space when there are only few +ve numbers so it might not be a good idea to create the auxiliary array
Insert only positive values into a min heap (n). for i = 1 to empty heap, check the top of the heap for i else return i. Each remove is (logn) so worts case is nlogn best case is n.
step 1 : Construct a binary tree bottom up... root will minimum of 2 children. If both are negative return min of 2 negative , if one is negative, make positive number the root
step 2 : At the end of step 1 root will be the minimum positive element. Now find 2nd positive minimum.
step3 : Start from the root and find minimum among elements that competed with root. This will return second positive minimum.
step 4 : if second is next to first repeat step 3 until u find a positive elem that is not immediately the next
step 5 : return the the prev minimum + 1
complexity O( nlogn). At each iteration u need to store the 2 nodes that are under consideration
import java.io.*;
import java.util.*;
public class Answer {
public static void main (String args[]) {
FindMinPositive solution = new FindMinPositive();
solution.getAnswer(args);
}
}
class FindMinPositive {
Set<Integer> InputSet = new TreeSet<Integer> ();
public void getAnswer(String args[]) {
ArrayList<Integer> intList = new ArrayList<Integer> ();
for (String item: args) {
intList.add(Integer.parseInt(item));
}
System.out.println("input: " + intList);
InputSet.addAll(intList);
System.out.println("set: " + InputSet);
think();
}
private void think() {
int min=1;
for (int item: InputSet) {
if (item > 0 && item >= (min+1)) {
System.out.println(min+1);
break;
}
}
}
}
Sorry for mistakes:
import java.io.*;
import java.util.*;
public class Answer {
public static void main (String args[]) {
FindMinPositive solution = new FindMinPositive();
solution.getAnswer(args);
}
}
class FindMinPositive {
Set<Integer> InputSet = new TreeSet<Integer> ();
public void getAnswer(String args[]) {
ArrayList<Integer> intList = new ArrayList<Integer> ();
for (String item: args) {
intList.add(Integer.parseInt(item));
}
System.out.println("input: " + intList);
InputSet.addAll(intList);
System.out.println("set: " + InputSet);
think();
}
private void think() {
int min=1;
for (int item: InputSet) {
if (item > 0 && item > (min+1)) {
System.out.println(min+1);
break;
}
else if(item > 0) min = item;
}
}
}
public static int findTheSmallestMissingInteger(int[] array)
{
int smallest = Integer.MAX_VALUE, smallest2 = Integer.MAX_VALUE;
for(int i = 0; i< array.length; i++)
{
if(array[i] > 0 && array[i] < smallest2)
{
if(array[i] < smallest){
smallest2 = smallest;
smallest = array[i];
}
else
smallest2 = array[i];
}
}
if(smallest == 1 && smallest+1 != smallest2)
return smallest+1;
return smallest2-1;
}
complexity is O(n)
I also think the same way .I i not getting other solution of construting auxaliary array or BSt r HEAP.
findTheSmallestMissingInteger ... if I am right, this function finds the smallest 2 elements and returns the missing number based on these 2 numbers. it will not work if consecutive numbers are present... e.g and array has negative numbers and 1,2,3,4 ... for this array your code will not return the answer which is 5 ... your code will find 1 and 2 as the smallest 2 numbers and will return 2-1 = 1
Raj ... by auxiliary array, it means you declare another array ... you only have to declare the auxiliary array to be of the same size as the original array . then fill it with zeros... and use hashing(enter 1 in the index corresponding to the value of the positive integer in the original array) to enter all the positive integers into this auxiliary array ... any positive integer that is outside the limit of the size of the auxiliary array need not be entered into the array ... then traverse that array and findout the missing integer ... the first positive index that has a 0 will be the missing integer ...
there is an edge case that there is no missing integer which means an error should be returned or return the (maximum positive integer + 1) depending on what the interviewer needs
just take an example and you will get it ... this method requires extra space .... if sorting is used, it will take more time but will not need extra space ... I dont know about the heap and the binary tree versions of the solution ...
Let me know in case you have any queries
//Thanks Anand.
I want to clean up my mess so here is my solution.
public static int findTheSmallestMissingInteger(int[] array)
{
Map<Integer, Boolean> cache = new HashMap<Integer, Boolean>();
for(int i = 0; i < array.length; i++)
{
if(array[i] > 0)
{
cache.put(array[i], true);
}
}
int i = 1;
while(i <= cache.size()){
if(cache.get(i) == null)
return i;
i++;
}
return i+1;
}
Anand, I am having trouble understanding how you can use the values of the first array as the index into the aux.
Consider an array of numbers such as {90000, 90001, 90003}. You will allocate an aux array of size 3 and then try to index into this array using 90000... clearly not the result we are hoping for.
Am I missing something here?
Let N be the length of the array.
The minimum positive number that is missing must be <= N+1.
This gives us an O(N) time and O(N) bitspace algorithm.
Create a bit-vector of 1,2,..N, and mark the bits corresponding to the numbers present in the array which are <=N+1. Pick the first unmarked bit.
If we are allowed to modify the array, we can make it O(1) space.
The highest voted solution space usage is not O(N) (but idea is similar). it is O(MAX) where MAX is the highest element in the array.
O(n) time, o(n) space using hashmaps:
1. iterate through each element & store each element in a hashmap (keep the largest element)
2. iterate 1 through the largest element
for each iteration, check if that element is in the hash map ... if not -> this is the largest missing value
if you go through the entire loop, the largest missing value is largest element + 1
Apart from the above solutions we can approach in the following manner too.
1. Find the minimum positive integer, if not 1, return 1.
2. Else take it as pivot, using quick sort method, place it to its position.
3. Take any +ve number from the right of 1 and again quick sort method place it in its position. Suppose the number is x. Pos[x] - Pos[1] == x-1, then repeat the same process to sub array that is to the right side of x else to the left side of x and greater than 1.
If the array starts from 2,eg {2, 5, 3, -4, 6}, will the answer be 1? Then in that case below solution can work.
int num = 1;
for (int j = 0; j < n; j++) {
if (a[j] == num)
num++;
}
return num;
Please let me know if I have thought of something wrong.
It is a very elegant idea, but if the array is not sorted, like this one:a[] = {9, 20, -2, 3, -45, 23, 5, 2,1}, you will get the wrong number. So, you should sort the given array first, then your idea will work better.
Here is O(n) solution.
#include <iostream>
using namespace std;
int findSmallestMissNum(int ar[],int size);
int main()
{
int input[] = {9,20,-2,-45,23,5,1};
cout<<findSmallestMissNum(input,7);
getchar();
return 0;
}
int findSmallestMissNum(int ar[],int size)
{
int small1, small2;
small1 = INT_MAX;
small2 = INT_MAX;
for( int i = 0 ; i < size ; i++)
{
if( ar[i] >= 0 && ar[i] < INT_MAX )
{
small2 = small1;
small1 = ar[i];
}
}
if( small1 < small2)
return small1 + 1;
else
return small2 + 1;
}
sorry for mistake..
if( ar[i] >= 0 && ar[i] < INT_MAX )
should be
if( ar[i] >= 0 && ar[i] < small1 )
I think the fastest way would be to traverse the array and foreach positive number(ignore negatives) you mark it in an auxiliar array, and then you traverse the auxiliar array, and the first index you find in 0 would be the number your looking for. Complexity time O(n), memory O(n)
in case you don't want to use any extra memory: just order the array and traverse until you find the first positive number, then continue traversing until you find a positive number that is not consecutive to the previous one, for example, array:{1,2,3,5}, you will find the 1 but the 2 is consecutive, so you have to continue to traverse until you finde the 5 that is not consecutive to 3, and the answer would be the previous(3) +1 (4).
the complexity for this is O(nlog(n)) and the memory O(1)
the code for the first algorithm:
foreach(x in array) if(x>0) axu[x]=1; for(inti i=1;i<length(aux);i++) if(aux[i]==0) return i;and the second algorithm:
- Franky January 03, 2013sort(array); //merge, quick nlog(n) for(int i=0;i<length(array);i++) if(array[i]>0 && array[i-1]>=0 && array[i]-array[i-1]>1) return array[i-1]+1;