1) Given an array containing positive and negative integers, how would you find the sub-array with maximum sum. In other words, given A[1..n] how would you find A[j..k] such that A[j] + ... + A[k] is maximum.

package personal.puzzles;

public class LargestSumSubarray {
    
    public static Pair getLargestSumSubarray(int[] array) {
        int finalLeft = 0;
        int finalRight = 0;
        int left = 0;
        int right = 0;
        int sum = Integer.MIN_VALUE;
        int runningSum = 0;
        while (right < array.length) {
            runningSum += array[right];
            if (runningSum >= sum) {
                sum = runningSum;
                finalLeft = left;
                finalRight = right;
            }
            if (runningSum < 0) {
                runningSum = 0;
                left = right + 1;
            }
            right++;
        }
        return new Pair(finalLeft, finalRight);
        
    }
    
    public static void main(String[] args) {
        int array[] = {-11, -2, -3, -8, 6, -22};
        Pair idx = LargestSumSubarray.getLargestSumSubarray(array);
        System.out.println(idx.getX() + "  " + idx.getY());
    }
    
    
    private static class Pair {
        private int x;
        private int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public int getX() {
            return x;
        }
        public int getY() {
            return y;
        }
    }
}

Instant messengers gaim a pain?

Do you use gaim in Linux to sign in to your messenger accounts? If so, beware before ticking the remember password option while using public computers. Gaim stores the username and password in plain text located in the accounts.xml file under ~/.gaim.

Video suggested that, here, a simple rot13 would still add to some obfuscation.

Here is the relevant unix command to encrypt and decrypt ciphertexts in rot13.

tr "[a-m][n-z][A-M][N-Z]" "[n-z][a-m][N-Z][A-M]"

Given n integers, how can you determine the largest and the second largest in n + logn comparisons. Note it is not O(n + logn)which is equal to O(n)