This is one of they Skype interview question
1) Write all test cases
2) Write doc
3) Keep your code as clean as possible
Question : From a given integer array find the missing number.
package codingpuzzles;
import java.util.HashMap;
import java.util.Map;
/**
* From a given integer array (of random numbers), this class returns the first number which is missing.
* Note: The array contains positive integers greater than 0.
*/
public class FindFirstMissingNumber {
public static final int MISSING_NUMBER_LOWER_BOUND = -1;
public static void main(String[] args) {
System.out.println("\n Finding the first missing number from an array containing random numbers");
//TEST CASE INPUT DATA
// int[] inputArray = null;
// int[] inputArray = {};
// int[] inputArray = {5, 1, 4, 3, 2};
// int[] inputArray = {5, 1, 4, 2};
// int[] inputArray = {1, 1, 4, 3, 2};
// int[] inputArray = {1, 4, 1, 3, 2};
// int[] inputArray = {1, 2, 3, 4, 5};
// int[] inputArray = {1, 2, 3, 4, 5, 7, 1};
// int[] inputArray = {1, 2, 3, 4, 6, 5, 1};
// int[] inputArray = {7, 6, 5, 4, 3, 2, 3};
int[] inputArray = {7, 6, 5, 4, 3, 2, 1};
try {
int firstMissingNumber = findFirstMissingNumberInArray(inputArray);
if (firstMissingNumber == MISSING_NUMBER_LOWER_BOUND) {
System.out.println("\n No missing number found");
} else {
System.out.println("\n firstMissingNumber: " + firstMissingNumber);
}
} catch(Exception e) {
e.printStackTrace();
}
}
/**
* This method would find the first missing number from the integer array which is passed as input.
*
* @param inputArray - The integer array from which the first missing number needs to be found out
* @return - The first missing number; or -1 is no missing number is found
* @throws Exception - thrown if the input integer array is null or empty
*/
public static int findFirstMissingNumberInArray(int[] inputArray) throws Exception {
int firstMissingNumber = MISSING_NUMBER_LOWER_BOUND;
if (inputArray == null) {
Exception exception = new Exception("Invalid input array. Please provide an input array which is not null");
throw exception;
}
if (inputArray.length == 0) {
Exception exception = new Exception("Invalid input array. Please provide an input array which is not empty");
throw exception;
}
Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
/**
* Populate the map with the integers from the input array.
* This is O(n) as we need to do a linear traversal of the input array.
*/
for (int i=0; i<inputArray.length; i++) {
map.put(new Integer(inputArray[i]), Boolean.TRUE);
}
System.out.println("\n map: " + map);
/**
* Find the first missing number from the input array.
* This is O(n) as we need to do a linear traversal of all the integers contiguously.
*/
for (int i=1; i<=inputArray.length; i++) {
if (!map.containsKey(new Integer(i))) {
firstMissingNumber = i;
break; //exit out of the for-loop when the first missing number is found out
}
}
//Total Big-Oh notation for this method = O(n) + O(n) = 2 x O(n)
return firstMissingNumber;
}
}
No comments:
Post a Comment