Binary Tree - sum of two nodes (Google Interview Question)

Here is another Google Interview problem:

Given a BST and a value x. Find two nodes in the tree whose sum is equal x. Additional space: O(height of the tree). It is not allowed to modify the tree.

The solution uses two stacks and the size of the binary tree. The approach is recursive and is similar to the binary search algorithm in arrays. The two stacks contain candidate answer numbers and on each iteration based on a calculation we pop or add new number in a stack. The binary tree size is used in cases where no answer exists. In these cases the algorithm starts endless loop.

void algorithm(Stack stk1, Stack stk2,
   double x, int size) {
    if (size == 0){
        System.out.println("No answer is found!");
        return;
    }
    if (!stk1.isEmpty() && !stk2.isEmpty()) {
        if (stk1.peek().data + stk2.peek().data == x) {
            System.out.println("Nodes are:\n" + stk1.peek().data + "\n"
            + stk2.peek().data);
            return;
        }
        if (stk1.peek().data + stk2.peek().data > x) {
            if(stk2.size()==1){
                BinaryTree node = stk2.pop();
                stk2.add(node);
                addRightNodes(stk2, node.getLeft());
            } else {
                addLeftNodes(stk2, stk2.pop());
            }    
        } else if (stk1.peek().data + stk2.peek().data < x) {
            if(stk1.size()==1){
                BinaryTree node = stk1.pop();
                stk1.add(node);
                addLeftNodes(stk1, node.getRight());
            } else {
                addRightNodes(stk1, stk1.pop());
            }    
        }
    }
    algorithm(stk1, stk2, x, --size);
}

See also the "Sum of nodes at odd and even levels of Binary Tree" problem.

Bracket combinations (Google Interview Question)

Write a function that prints all combinations of well-formed brackets. The input is a number which says how many pairs of brackets will the different outputs have. For Brackets(3) the output would be:
((()))  (()())  (())()  ()(())  ()()().

The solution below uses recursion. The logic here is very simple - every output is constructed starting with its first symbol. On each step a new symbol is added following these rules:

• rule 1: if the number of opened brackets is equal to the number of closing brackets, then the only next possible symbol to add is '('
• rule 2: if the number of opened brackets is more than the number of closing brackets, then there are two options - either we add ')' or '('
• rule 3: if the number of opened brackets is more than half the number of all brackets, then the construction went wrong and we break the whole case
• rule 4: if the number of opened brackets is less than the number of closing brackets, then the construction went wrong and we break the whole case
• rule 5: the last symbol of the output cannot be '('

private void Brackets(String output, int open, int close, int total) {
    if (output.length() == total * 2 && output.charAt(total * 2 - 1) != '(') {
        System.out.println(output);
    } else if (open > total || open < close) {
        return;
    } else {
        if ((open == close)) {
            Brackets(output + "(", open + 1, close, total);
        }
        if ((open > close)) {
            Brackets(output + "(", open + 1, close, total);
            Brackets(output + ")", open, close + 1, total);
        }
    }
}

public void Brackets(int total) {
    Brackets("", 0, 0, total);
}

This is an Interview Question for Software Engineers at Google. Here you can find more information.

Travel from string to string (Google Interview question)

Google Interview Question (http://www.careercup.com/question?id=14947965):

Given a source string and a destination string write a program to display sequence of strings to travel from source to destination. Rules for traversing:
1. You can only change one character at a time
2. Any resulting word has to be a valid word from dictionary
Example: Given source word CAT and destination word DOG , one of the valid sequence would be
CAT -> COT -> DOT -> DOG
Another valid sequence can be
CAT -> COT - > COG -> DOG
One character can change at one time and every resulting word has be a valid word from dictionary

The solution here includes not only functions but global variables as well.

public class SourceToDestinationString {
    // Container for the valid words
    HashSet dictionary = null;
    // Container for words already passed by a word sequence
    HashSet visited;

    public SourceToDestinationString() {
        super();
        visited = new HashSet();
        dictionary = new HashSet();
        initDictionary();
    }

    private void initDictionary() {
        // Add the wrods in the dictionary
    }

    // Returns all valid words suitable for the next step of the path
    private ArrayList generateWords(String source, int position) {
        if (position < 0 || position >= source.length())
            return null;
        ArrayList result = new ArrayList();
        for (char ch = 'A'; ch <= 'Z'; ch++) {
            StringBuffer tmpWord = new StringBuffer(source);
            tmpWord.setCharAt(position, ch);
            String word = tmpWord.toString();
            if (dictionary.contains(word)) {
                result.add(word);
            }
        }

        return result;
    }

    // The sequence of words is written in the stack 'path' 
    public void sourceToDestinationString(Stack path, String destination) {
        String source = path.peek();
        if (source.equals(destination)) {
            System.out.print("Solution is ");
            System.out.println(path);
            return;
        }

        visited.add(source);

        for (int i = 0; i < source.length(); i++) {
            ArrayList words = generateWords(source, i);
            for (String nextWord : words) {
                if (visited.contains(nextWord))
                    continue;
                path.push(nextWord);
                sourceToDestinationString(path, destination);
                path.pop();
            }
        }
  
        visited.remove(source);
    }
}

Sum of nodes at odd and even levels of Binary Tree

Given a Binary Tree, write a function which calculates the difference between the sum of node values at odd levels and sum of node values at even levels, i.e. function(BinaryTree) = (sum of values of nodes at odd height) - (sum of values of node at even height). Consider the root node is at height 1.

int calculateDifference(BinaryTree root) {
    if (root == null) {
        return 0;
    }
    int result = root.getData() - calculateDifference(root.getLeft())
              - calculateDifference(root.getRight());
    return result;
};

The solution is short and uses recursion. The idea is that you negate all levels under the current one (the level of the current node) and you do that on each step of the recursion.

sum[l1] - (sum[l2] - (sum[l3] - (sum[l4] - ... = sum[l1] - sum[l2] + sum[l3] - sum[l4]...

Deifference between sum of nodes on even height and sum of nodes on odd height

Chinese number system

This problem comes from a Google interview (http://www.careercup.com/question?id=14942235). You probably know that the number "4" is considered unlucky number in China. Here is the problem:

Number '4' is considered an unlucky number in China because it is nearly homophonous to the word "death". For this reason, there is a new number system similar to the decimal system but has no '4'. For example: 1,2,3,5,6,7...13,15...23,25...33,35...39,50...
Here 5 is 4 in decimal system, and 15 is 13... Write a function which takes as an input a positive number (Chinese number) and provides an output number (decimal number or error):
1 -> 1;
2 -> 2;
5 -> 4;
4 -> illegal;
15 -> 13;

Solution:

public int chineseNumberToDecimal(String chineseNumber) {
    // check the input
    if(chineseNumber.contains("4")){
        throw new IllegalArgumentException("Digit 4 is illegal");
    }
  
    // convert to nonary number
    char[] chineseCharArray = chineseNumber.toCharArray();
    for (int i = 0; i < chineseCharArray.length; i++) {
        if (chineseCharArray[i] >= '4' && chineseCharArray[i] <= '9') {
            chineseCharArray[i]--;
        }
    }
    String nonaryNumber = new String(chineseCharArray);
  
    // get the decimal version of the nonary number
    int decimalNumber = Integer.valueOf(nonaryNumber, 9);
  
    return decimalNumber;
}

The whole idea is based on that a Chinese number is a number in the nonary system and its digits are: 0, 1, 2, 3, 5, 6, 7, 8, 9. The ordinary nonary system has the digits: 0, 1, 2, 3, 4, 5, 6, 7, 8. Therefore we can convert the given Chinese number into an ordinary number in the nonary system. Then it is easy to get the decimal number having an ordinary nonary number.

Can you think of the opposite function - decimalToChineseNumber?