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?

How to find k-th element from the end of a linked list?

The solution below uses recursion to get the number of elements in the linked list and then prints only the value at the k-th node from end of the Linked List.

public static void kthElement(LinkedList list, int k) {
    ListIterator iterator = list.listIterator();
    handleNextElement(iterator, k);
}

private static int handleNextElement(ListIterator iterator, int k) {
    int elementValue = 0;
    if (!iterator.hasNext()) {
        return 0;
    }

    elementValue = iterator.next();
    int count = handleNextElement(iterator, k) + 1;

    if (count == k) {
        System.out.println(elementValue);
    }

    return count;
}

k-th node from end

Another solution is non-recursive where you run two runners/iterators in parallel with distance k between them.

Integer kthElement(LinkedList list, int k) {
    if (k < 1 || k > list.size()) {
        return null;
    }

    ListIterator iterator = list.listIterator();
    for (int i = 0; i < k; i++) {
        if (iterator.hasNext()) {
            iterator.next();
        } else {
            return null;
        }
    }

    ListIterator iterator2 = list.listIterator();
    while (iterator.hasNext()) {
        iterator.next();
        iterator2.next();
    }

    Integer result = iterator2.next();
    return result;
}

2 iterators with distance k between them

This solution takes O(n) time and O(1) space.

Are two Binary Trees mirror image of each other?

How can you check if two binary trees are mirror image of each other? It would mean that if you do an inorder traversal on the trees, the elements of the second tree will be visited in reversed order compared to the order of the elements visited in the first tree. Here is the Java code:

boolean areMirrorTrees(BinaryTree a, BinaryTree b) {
    if (a == null && b == null) {
        return true;
    }
    if (a == null || b == null) {
        return false;
    }
    return a.data == b.data && areMirrorTrees(a.left, b.right)
            && areMirrorTrees(a.right, b.left);
}

Inorder traversal of the first tree will be: 3, 4, 5, 6, 7, 8, 9, 10, 12, 13.
Inorder traversal of the second tree will be: 13, 12, 10, 9, 8, 7, 6, 5, 4, 3.

Array is transformed into Binary Tree

How will you place all elements of a given array into binary tree? The given array is unsorted.
Here is one recursive solution of the problem:

TreeNode toTree(ArrayList array){
    if (array == null || array.size() == 0) {
        return null;
    }
 
    TreeNode result = new TreeNode(array.get(0));
    for (int i = 1; i < array.size(); i++) {
        addTo(result, array.get(i));   
    }
  
    return result;  
}

void addTo(TreeNode node, int i) {
    if (i < node.d) {
        if (node.getLeft() == null) {
            node.setLeft(new TreeNode(i));
        } else {
            addTo(node.getLeft(), i);
        }
    } else {
        if (node.getRight() == null) {
            node.setRight(new TreeNode(i));
        } else {
            addTo(node.getRight(), i);
        }
    }
}

Cycle in LinkedList

There is an interesting technique how you can verify if there is a cycle in a LinkedList without using any additional data structure. All that is needed are two references (fast runner and slow runner) of the same type as the elements in the linked list. Here is the solution:

boolean hasCycle(Node linkedList) {
    if (linkedList == null) {
        return false;
    }
    Node n1, n2;
    n1 = linkedList;
    n2 = linkedList.getNext();
    while (n1 != null && n2 != null) {
        if (n1.equals(n2)) {
            return true;
        }

        n1 = n1.getNext();
        if (n2.getNext() != null) {
            n2 = n2.getNext().getNext();
        } else {
            return false;
        }

    }
    return true;
}

Check if one string is permutation of another string

You have two strings and you need to decide if the first one is a permutation of the other one. The solution uses HashMap data structure where each symbol of the first string is stored as a key and its value is the number of times this symbol appears. Then you loop through the second string and for each character which is a key in the HashMap you decrease the number of times this character appeared in the first string. In the end if the two strings are permutations of each other,  you will end up with a HashMap with all values 0:

boolean arePermutations(String str1, String str2) {
    if (str1.length() != str2.length()) {
        return false;
    }
    HashMap hashMapChars = new HashMap();
    // enter the chars and the number of times each of them appears
    for (int i = 0; i < str1.length(); i++) {
        if (hashMapChars.containsKey(str1.charAt(i))) {
            int count = hashMapChars.get(str1.charAt(i));
            hashMapChars.put(str1.charAt(i), count + 1);
        } else {
            hashMapChars.put(str1.charAt(i), 1);   }
        }
    }
    // for each char in str2 decrease the value number
    for (int i = 0; i < str2.length(); i++) {
        if (hashMapChars.containsKey(str2.charAt(i))) {
            int count = hashMapChars.get(str2.charAt(i));
            count--;
            if (count < 0) {
                return false;
            }
            hashMapChars.put(str2.charAt(i), count);
            } else {
                return false;
            }
        }
        return true;
}

Are all characters in a string unique?

Here are some Java implementations checking if all the characters in a string are unique. The first solution uses HashMap to store the characters of the string:

boolean hasAllUniqueChars(String str) {
    HashMap<Character, Object> hashMapChars = new HashMap<Character, Object>();
    for (int i = 0; i < str.length(); i++) {
        if (hashMapChars.containsKey(str.charAt(i))) {
            return false;
        } else {
            hashMapChars.put(str.charAt(i), null);
        }
    }
    return true;
}

The second one is the most trivial one and has time complexity O(n²). It uses two nested for loops:

boolean hasAllUniqueChars2(String str) {  
    for (int i = 0; i < str.length(); i++) {
        for (int j = 0; j < str.length(); j++) {
            if(i == j){
                continue;
            }
            if(str.charAt(i) == str.charAt(j)){
                return false;
            }
        }
    }
    return true;
}