Apple Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
/* // O(n) and no extra space
* Solution is same as in case when we have 0 to n-1 element in size n array
* In here if any arr[i] > size of arr ,we do not mark its index as negative since that
* index is not in array. but mark of others.
* Also, shift all negative numbers to the right of array and clip the array
*
*
*/
import java.util.*;
public class MinMissingInteger {
public static void findMinMissing(int[] arr){
//Move -ve number to end of array either shift or just remove
int ctr=0;
for(int i=0;i<=arr.length-1;i++){
if(arr[i]>0){
arr[ctr] = arr[i];
ctr++;
}
}
//array with positive numbers is till ctr-1
int maxEndLength=ctr-1; // max length of positive numbers
//Mark kth index where k=arr[i] and is in array's range
//Since +ve numbers start from 1 and array index from 0, we mark k-1 index as negative
for(int i=0;i<=maxEndLength;i++){
int index = Math.abs(arr[i])-1; // minus 1, element may be marked negative so check abs value
if(index <= maxEndLength){
arr[index] = -1*arr[index];
}
}
//find the first missing positive number
int firstMissingIndex=0;
for(int i=0;i<=maxEndLength;i++){
if(arr[i]>0){
firstMissingIndex=i+1; // since we subtracted 1
break;
}
}
System.out.println("Missing value = " + firstMissingIndex);
}
public static void main(String[] args) {
int[] arr = {1,9,2,5,7};
findMinMissing(arr);
}
}
/* *********** 1. Sorting the stack values, Here you can find the Java program for this problem************* */
- Kishore May 19, 2017