import copy

# Print all possible encodings of a positive integer numeric value.
# The encodings are defined as follows: 11 -> aa or ord(96 + 11) -> k.

def print_encodings(permuted_list):
    string_value = ""
    for element in permuted_list:
        string_value += chr(96 + int(element))
    print string_value

def encoding_permutation(input, idx, permuted_list):
    if (len(input) == idx):
        print_encodings(permuted_list)
        return
    if len(input) - idx >= 2:
        one_gram_list = copy.deepcopy(permuted_list)
        one_gram_list.append(input[idx])
        bi_gram_list =  copy.deepcopy(permuted_list)
        bi_gram_list.append(input[idx] + input[idx + 1])
        encoding_permutation(input, idx + 1, one_gram_list)
        encoding_permutation(input, idx + 2, bi_gram_list)
    else:
        permuted_list.append(input[idx])
        encoding_permutation(input, idx + 1, permuted_list)

encoding_permutation("1111", 0, [])

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;
        }
    }
}

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)

I am a dolt. Needless to say. Missed out on one of the trivial algorithmic puzzle.

Q) Given a node in the binary search tree, each node has three pointers - lchild, rchild and parent and as an associated value, how would find the node
which was value immediately greater than the given node. (next largest).

Try out the algorithm and comment pls.