Friday, February 8, 2013

Points to be considered while taking white Board Interviews (Find missing number in an array)

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