I found an interesting blog post today. The writer had shared some programming questions he had received during job interviews, they looked fun so I had a crack at them and here are my results.

I noticed that there's an error with the GESHI-script, it replaces all brackets with lt/gt-signs when they surround the character i. So please remember this if you want to copypasta the code.

    public static void main(String[] args) {
        int[] largestSum = {-10, 2, 3, -2, 0, 5, -15};
        System.out.println(largestContinousSum(largestSum));

        int[] missing = {1, 2, 3, 4, 5, 6, 7, 9, 10};
        System.out.println(findMissing(missing));

        int[] duplicate = {1, 2, 3, 4, 2, 5, 9, 6, 7, 8, 10};
        System.out.println(findDuplicate(duplicate));

        int[] findLargest = {0, 1, 2, 2, 2, 3, 6, 7, 7, 8, 9};
        System.out.println(sumNLargest(findLargest, 3));

        int[] cards = {12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        shuffle(cards);
        for (int c : cards)
            System.out.print(c + " ");
    }
    
    /*
     * Implement Shuffle given an array containing a deck of cards 
     * and the number of cards. Now make it O(n). 
     */
    public static void shuffle(int[] cards)
    {
        // We need a RNG here, I can't see any other way.
        for(int i = 0; i < cards.length; i++)
        {
            int remaining = cards.length - i;
            int swapSpot = (int) (remaining * Math.random());
            int tmp = cards[swapSpot];
            cards[swapSpot] = cards_;
            cards_ = tmp;
        }
    }
    
    /*
     * Return the sum two largest integers in an array
     * int SumTwoLargest(int* anData, int size)
     * 
     * I made this one after I made the sumNLargest...
     */
    public static int sumTwoLargest(int[] numbers)
    {
        return sumNLargest(numbers, 2);
    }
    
    /*
     * Sum n largest integers in an array of integers where every integer 
     * is between 0 and 9
     * int SumNLargest(int* anData, int size, int n)
     */
    public static int sumNLargest(int[] numbers, int n) {
        int[] available = new int[10];
        for (int i = 0; i < numbers.length; i++) {
            int num = numbers_;
            available[num]++;
        }        
        int realSum = 0;
        for (int i = 9; n > 0; i--)
        {
            int fromBucket;
            for (fromBucket = 0; available_ > 0 && n > 0; n--)
            {
                fromBucket++;
                available_--;
            }
            realSum += i*fromBucket;
        }
        return realSum;
    }

    /*
     * Returns the largest sum of contiguous integers in the array
     * Example: if the input is (-10, 2, 3, -20, 0, 5, -15), 
     * the largest sum is 5
     */
    public static int largestContinousSum(int[] selection) {
        int currSum = Integer.MIN_VALUE;

        for (int i = 0; i < selection.length; i++) {
            for (int sub = i; sub < selection.length; sub++) {
                int subSum = subSectionSum(selection, i, sub);
                if (subSum > currSum) {
                    currSum = subSum;
                }
            }
        }
        return currSum;
    }
    
    /*
     * Helper function for the summation problem
     */
    private static int subSectionSum(int[] array, int start, int stop) {
        int sum = 0;
        for (int i = start; i <= stop; i++) {
            sum += array_;
        }
        return sum;
    }
    
    /*
     * You are given an array with integers between 1 and 1,000,000. 
     * One integer is missing. How can you determine which one? 
     * Can you think of a way to do it while iterating through the array 
     * only once. Is overflow a problem in the solution? Why not? 
     */
    public static int findMissing(int[] nums) {
        long actualSum = 0;
        for (int i : nums) {
            actualSum += i;
        }
        int n = nums.length + 1;
        long expectedSum = (n * n + n) / 2;

        return (int) Math.abs(expectedSum - actualSum);
    }
    
    /*
     * You are given an array with integers between 1 and 1,000,000. 
     * One integer is in the array twice. 
     * How can you determine which one? 
     * Can you think of a way to do it using little extra memory. 
     */
    public static int findDuplicate(int[] nums) {
        long actualSum = 0;
        for (int i : nums) {
            actualSum += i;
        }
        int n = nums.length - 1;
        long expectedSum = (n * n + n) / 2;

        return (int) Math.abs(expectedSum - actualSum);
    }

This is just a subsection of the original blogpost, as I didn't have time for more. I thought I'd start off with the "Arrays" part. This is written in Java because it's what I feel the most comfortable with, but I know I don't use any "magic" which trivializes the task at hand. Except for the shuffle. :)

Can you spot any flaws? Do you know a better method? Let me know.

The original post can be seen in it's entirety here: http://maxnoy.com/interviews.html