Brackets - number of possible soltions

Given a string containing only the symbols '?', '(' and ')'. You can replace the '?' with either '(' or ')'. Your task is to write a function that tells the number of possible solutions where brackets are used correctly.
Example:
Given the string "?(????)?" the function should return 6.
The correct possible solutions are:
((()()))
(((())))
(())(())
(()(()))
((())())
(()()())

Here is one recursive solution. Three parameters are passed to the function - the given string, the current index of the string and count - an integer calculated based on the brackets - if '(' we add 1 to count and if ')' we decrease count by one. We start iteration over the string's characters starting from the first. If the current symbol is '(' or ')', the the count is recalculated and the iteration goes on. If the current symbol is '?', then there are 2 possibilities either '(' or ')' and that gives 2 branches of the recursion.

long bracket(String str, int index, int count) {
    int n = str.length() - 1;
    long solution = 0;

    if (index > n) {
        if (count == 0)
            solution = 1;
        else
            solution = 0;
    } else {
        if (count < 0)
            solution = 0;
        else

        if (str.charAt(index) == '(')
            solution = bracket(str, index + 1, count + 1);
        else if (str.charAt(index) == ')')
            solution = bracket(str, index + 1, count - 1);
        else if (str.charAt(index) == '?') {
            solution = (bracket(str, index + 1, count + 1) + bracket(str, index + 1, count - 1));
        }
    }

    return solution;
}

The next solution uses the Dynamic Programming method. Here we create a table where we build a row based on the previous row. Here is an explanation of the table. Let's look the string "??(???". We consider two parameters - our two dimensions of the table:
- count: number_of_opening_brackets - number_of_closing_brackets
- index: this is the index of the current character we look at
If the last one is a "?" or ')' - there is one possible solution and if it is '(' there is no solution. That means the last row of our table will be 0, 1, 0, 0... Only in case the last symbol is '(', there will be, obviously, no solutions at all. This is a special case. Imagine, we are now considering the penultimate symbol. Based on the count number and the symbol staying in this position, we calculate the penultimate row. In our case the penultimate symbol is '?'. If count is 0, then we place '(' instead of the '?' and continue. If count is 1, there is no way we can have count 0 in the end no matter what we place instead of the '?'. If count is 2, then we write ')' in place of the '?' and continue. The rest of the count values - 3, 4, 5, won't give a solution. That means our penultimate row will be 1, 0, 1, 0, 0...
We actually build row i based on row (i+1). The logic is the following:
if the symbol is ')' then cell[i][j] = cell[(i + 1)][j - 1];
if the symbol is '(' then cell[i][j] = cell[(i + 1)][j + 1];
if the symbol is '?' then cell[i][j] = cell[(i + 1)][j - 1] + cell[(i + 1)][j + 1];

Our answer is the value in cell[0][0].

long bracketDP(String str) {
    int strLength = str.length() - 1;

    for (int i = 0; i <= strLength; i++) {
        arr[strLength][i] = 0;
    }

    if (str.charAt(strLength) != '(')
        arr[strLength][1] = 1;

    for (int i = strLength - 1; i >= 0; i--) {// index
        for (int j = 0; j <= strLength; j++) {// count
            if (j == 0) {
                if (str.charAt(i) == ')')
                    arr[i][j] = 0;
                if (str.charAt(i) == '(')
                    arr[i][j] = arr[(i + 1)][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i][j] = arr[(i + 1)][j + 1];
                }
            } else {
                if (str.charAt(i) == ')')
                    arr[i][j] = arr[(i + 1)][j - 1];
                if (str.charAt(i) == '(')
                    arr[i][j] = arr[(i + 1)][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i][j] = arr[(i + 1)][j - 1] + arr[(i + 1)][j + 1];
                }
            }
        }
    }
    return arr[0][0];
}

In fact, constructing each row all we need is the previous row. It means that we can do with memory reserved for only two rows - we use one to construct the second and then we use the second and write the results to the first one. Then we again use row one to construct the second row, and so on. Here is an optimization we can do:

long bracketDP2(String str) {
    int strLength = str.length() - 1;

    for (int i = 0; i <= strLength; i++) {
        arr[strLength % 2][i] = 0;
    }

    if (str.charAt(strLength) != '(')
        arr[strLength % 2][1] = 1;

    for (int i = strLength - 1; i >= 0; i--) {// index
        for (int j = 0; j <= strLength; j++) {// count
            if (j == 0) {
                if (str.charAt(i) == ')')
                    arr[i % 2][j] = 0;
                if (str.charAt(i) == '(')
                    arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
                }
            } else {
                if (str.charAt(i) == ')')
                    arr[i % 2][j] = arr[(i + 1) % 2][j - 1];
                if (str.charAt(i) == '(')
                    arr[i % 2][j] = arr[(i + 1) % 2][j + 1];
                if (str.charAt(i) == '?') {
                    arr[i % 2][j] = arr[(i + 1) % 2][j - 1] + arr[(i + 1) % 2][j + 1];
                }
            }
        }
    }
    return arr[0][0];
}

For more brackets problems visit "Bracket combinations"

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.

Delete node in LinkedList

Delete a given node in a singly linked list. You don't have an access to the root node of the list. You have only access to the given node. Let's suppose this is your definition of a node.

class Node {
    Node next;
    int data;
}

Deleting a node in the middle of a singly linked list could happen if you copy the value from the next node over the given node and then to delete the next node.

public static void deleteMiddleNode(Node n){
    if(n == null){
        System.out.println("Node value is incorrect");
    }
    // in case of last element
    if(n.next == null){
        n = null;
    }
  
    Node next = n.next;
    n.data = next.data;
    n.next = next.next;
}

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

Fibonacci numbers - 4 solutions

Find the n-th Fibonacci number. The Fibonacci numbers are integers 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Wikipedia says:

By definition, the first two numbers in the Fibonacci sequence are 0 and 1 (alternatively, 1 and 1), and each subsequent number is the sum of the previous two. 

For example the 7-th Fibonacci number in the sequence is 8. Here are a few solutions. The first one is a trivial one and follows the definition - i.e. it uses recursion.

long fibonacciRecursive(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

The second solution is iterative. A drawback here is that the size of the array which is used to store the Fibonacci numbers needs to be defined statically.

long fibonacciIterative(int n) {
    int size = 100;
    long[] fibonacciNumbers = new long[size + 1];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;
  
    for (int i = 2; i <= n; i++) {
        fibonacciNumbers[i] = fibonacciNumbers[i - 1]
                            + fibonacciNumbers[i - 2];
    }
    return fibonacciNumbers[n];
}

The third solution is again iterative. The difference here is that it uses an array with size 3. This is a very elegant and optimized solution.

long fibonacciIterativeLowMem(int n) {
    int[] fibonacciNumbers = new int[3];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;

    for (int i = 2; i <= n; i++) {
        fibonacciNumbers[i % 3] = fibonacciNumbers[(i - 1) % 3]
                                + fibonacciNumbers[(i - 2) % 3];
    }
    return fibonacciNumbers[n % 3];
}

Here is one more solution that uses an optimization called memoization. The idea here is that we avoid the calculation of the tasks we already had calculated.

long fibonacciMemoization(int n) {
    int size = 100;
    long[] fibonacciNumbers = new long[size+1];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;
    for (int i = 2; i < size; i++) {
        fibonacciNumbers[i] = -1;
    }
  
    if (fibonacciNumbers[n] != -1) {
        return fibonacciNumbers[n];
    } else {
        fibonacciNumbers[n] = fibonacciMemoization(n - 1)
                            + fibonacciMemoization(n - 2);
        return fibonacciNumbers[n];
    }
}

Reverse a LinkedList

Given a singly linked list. You have to revers it.

The first solution uses recursion.

Node reverseList(Node previous, Node current) {
    Node tmp;
    if (current.next == null) {
        current.next = previous;
        return current;
    }
    tmp = reverseList(current, current.next);
    current.next = previous;
    return tmp;
}

The second solution is non-recursive.

Node reverse(Node current) {
    Node tmp;
    Node previous = null;
    while (current != null) {
        tmp = current.next;
        current.next = previous;
        previous = current;
        current= tmp;
    }
    return previous;
}

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