Sunday, August 28, 2011

Rearranging Letters to Form Word




Question:
Rearranging the letters to form a word is a very funny algorithm problem, and it has several variants. Here we will talk about the problem – the most efficient way to find out whether we can rearrange these letters and form a word, and if yes, return all words that can be constructed.
For input [d, a, e, p, n, p], we can rearrange them into a word "append".

Answers:
We can think about our commonly-used data structure - HashMap, if we can build one HashMap from the dictionary, and then query it using some key, the running time would be O(1). Brilliant!!!

But what would be key and value? 
First the input order doesn't matter, "atc" is same as "tac", or "cta", so we can order the input, "atc", "tac", "cta" would all be sorted as "act".
Also we may construct several words from the letters, for example, we can form "act", "cat" from the letters - "atc".

So we can build the HashMap from the dictionary, the key would be the sorted letters; the value would be a list containing all words that can be constructed by rearranging the order of these letters.

Code:
The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/programmer-plus.
package org.codeexample.algorithm.wordPuzzles;
import java.io.*;
import java.util.*;
import java.util.regex.Pattern;

public class Dictionary {

    private Map<String, HashSet<String>> wordMap = new HashMap<>();

    /**
     * @param dictionaryFile, the file contains list of words, 
     * each line may contain several words that are separated by space.
     * @throws IOException
     */
    public Dictionary(String dictionaryFile) throws IOException {
        init(dictionaryFile);
    }

    private void init(String dictionaryFile) throws IOException {
        FileReader fr = new FileReader(new File(dictionaryFile));

        FileReader fr = new FileReader(file);
        BufferedReader br = new BufferedReader(fr);

        Pattern pattern = Pattern.compile("\\s+");
        while (true) {
            String line = br.readLine();
            if (line == null) {
                break;
            }
            String[] words = pattern.split(line);
            for (String word : words) {
                word = word.trim();
                if (!word.isEmpty()) {
                    String sortedWord = getMapKey(word);

                    HashSet<String> matchedWordSet = wordMap.get(sortedWord);
                    if (matchedWordSet == null) {
                        matchedWordSet = new HashSet<>();
                    }
                    matchedWordSet.add(word);
                    wordMap.put(sortedWord, matchedWordSet);
                }
            }
        }
    }

    private String getMapKey(String letters) {
        char[] chars = letters.toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    }

    /**
     * Return a list of word that can constructed by rearranging these letters.
     * 
     * @param letters
     * @return a hash set that containing all words, if can't find one, return
     *         empty list, instead of null to avoid NPE in client code.
     * @throws IllegalArgumentException if parameter is null.
     */
    public Set<String> formWords(String letters) 
            throws IllegalArgumentException {
        if (letters == null) {
            throw new IllegalArgumentException("parameter can't be null.");
        }
        Set<String> wordsSet = wordMap.get(getMapKey(letters));
        if (wordsSet == null) {
            wordsSet = new HashSet<>();
        }
        return wordsSet;
    }
}

Saturday, August 27, 2011

Learning Java Integer Code and Puzzles



1. Question - What the program would output?
int i = 127;
boolean b = (Integer.valueOf(i) == Integer.valueOf(i));
System.err.println(b);
i = 128;
b = (Integer.valueOf(i) == Integer.valueOf(i));
System.err.println(b);
We can immediately know the answer after we look at the source code.
public static Integer valueOf(int i) {
    if(i >= -128 && i <= IntegerCache.high)
        return IntegerCache.cache[i + 128];
    else
        return new Integer(i);
}
We can know it doesn't cache all Integer values, as this may consume too much memory, so it just caches the numbers between [-128, 127] in the static IntegerCache class, for other int numbers, each time it would return a new Integer. Class Long also only caches the numbers between [-128, 127].
The output of the previous program would be obvious now: true and false.
2. Autobox and Auto-unbox
2. 1 How is it implemented in JDK?
Simply put, when we call "Integer wrapper = 2;", the java compile would translate it to "Integer wrapper = Integer.valueOf(wrapper);".
When we call "int i = wrapper;", the java compile would translate it to "int i = wrapper.intValue();".
You can verify this by using javap to look. at the compiled java class: javap -c IntegerTester.
Long.valueOf(0L).equals(0)?
2.2 What would be the output of the following program?
Long l = 0L;
Integer i = 0;
System.out.println(l.equals(i));
System.out.println(i.equals(l));
The program above is same as:
So let's look at the JDK source code again:
public final class Integer extends Number 
  implements Comparable<Integer> {
    public boolean equals(Object obj) {
    if (obj instanceof Integer) {
        return value == ((Integer)obj).intValue();
    }
    return false;
    }
}
public final class Long extends Number 
  implements Comparable<Long> {
    public boolean equals(Object obj) {
      if (obj instanceof Long) {
          return value == ((Long)obj).longValue();
      }
      return false;
    }
}
From the code, we can see if the type of parameter is not same, these method would return false.
So the output of previous program would be false, false.
Autobox and auto-unbox are good features, as it will convert the primitive type or wrapper type to the needed one, and we can write less code, but we should use it carefully, as usually, it may create object under the hood, if we are unaware of this, it may cause big performance penalty.
public void test(Integer i) {
    while (i < 0) {
        --i;
    }
}
In the previous program, in each step, JVM actually does this: it calls i.intValue(), subtracts it by one, and then create a new Integer value.
For JVM, it would be same as:
while (i.intValue() &lt; 0) {
    i = Integer.valueOf(i.intValue() - 1);
}
So in each step, we would unnecessary create one Integer value and call intValue methods twice.
Try to use javap to look at the compiled class file.
If we know this, we can change our code like the below, it would be faster.
public void test(Integer i) {
      int j = i;
      while (j < 0) {
           --j;
      }
      i = j;
}
In our code, it's to better use primitive type as often as possible. 
In Integer class there are many other interesting and useful methods, some methods are listed below, is it cool and a little confusing? Try to figure it out.
public final class Integer extends Number 
  implements Comparable<Integer> {
    public static int reverseBytes(int i) {
        return ((i >>> 24)           ) |
               ((i >>   8) &   0xFF00) |
               ((i <<   8) & 0xFF0000) |
               ((i << 24));
    }
    public static int reverse(int i) {
        // HD, Figure 7-1
 i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
 i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
 i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
 i = (i << 24) | ((i & 0xff00) << 8) |
     ((i >>> 8) & 0xff00) | (i >>> 24);
 return i;
    }
    public static int bitCount(int i) {
        // HD, Figure 5-2
 i = i - ((i >>> 1) & 0x55555555);
 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 i = (i + (i >>> 4)) & 0x0f0f0f0f;
 i = i + (i >>> 8);
 i = i + (i >>> 16);
 return i & 0x3f;
    }
}
Reference:

Monday, August 22, 2011

Is Successive Array?



Question:
Given an unordered int list, except 0, each number can appear only once, 0 can be regarded as any number. Now we need determine whether the digits from the list are logically successive,

For example,
3, 2, 1 would be considered as successive.
0, 3, 1 also is successive, as 0 can be regarded as 2.
0, 0, 3, 1 also is successive as 0, 0 can be regarded as (0, 2), or (2, 4).

Answer:
First, simplify this question, if there can be only one 0, and can't be considered as any number. How we determine whether the array is successive?

In this case, we can get the maximum and minimum of this array, if (max - min) = (length of the array -1), then this array is considered as successive. This is very straightforward.

So back to the original problem, suppose the length of the array is n, and there is x 0, and thus n-x non-zeros, so we can get the inequality:  if (max - min) <= (n -1), this array is successive.
0, 3, 1 ==> (3-1) = len -1 = 2
0, 0, 3, 1 ==> (3-1) < len - 1 = 3

Code:
The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/programmer-plus.
package org.codeexample.successiveArray;

public class SuccessiveArray {

/**
* see http://programer-tips.blogspot.com/
* 2011/08/is-array-successive.html
* <p>
* Determine whether the unordered array is logically successive, 0 can be
* regarded as any number. For example, [0, 3, 1] is successive, as 0 can be
* regarded as 2.
* 
* @param array
* @return
*/
public static boolean isArraySuccessive(int[] array) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

for (int i = 0; i < array.length; i++) {
int temp = array[i];
if (temp == 0)
continue;
if (temp < min) {
min = temp;
}
if (temp > max) {
max = temp;
}
}
return (max - min) <= (array.length - 1);
}
}

Sunday, August 21, 2011

Does Two Integer arrays Come from one sequence



Question:
There is a list of int arrays; the next int array is the explanation of the previous one.
For example, if the first one is [1], the next int array would be [1, 1], it means the previous array has a number one, the next array would be [2, 1], means the previous array has two one, and so on.
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1

So the question would be: given a two int arrays A and B, you need determine whether they come form one sequence? In other word, whether you can induce from A to B, or from B to A?

Answer:
It seems that we can just induce from A, and get its next int array, and its next's next array, if one int array equals B, then we can return true.
But this problem is that what if A and B don't come from one sequence, when we stop?
We don't know.

In this problem, we can think reversely, if we starts from A, and get A's previous array, if it equals B, we can return true, if not, we continue. But if not, when we stop?

The first case: we can’t conclude previous array from the curry array:
Two cases:
1.      When the current int array has odd numbers, we stop, as it's impossible to get its previous array. The reason is simple: (a[i], b[i]) describes one item of previous array, if current array has odd numbers, (a0, b0) .. (a[n], b[n]), a[n+1], a[n+1] can't describe one item of previous array.
2.      When the current int array has even digits, but have some invalid pairs, such as (0 1).
Another case: if we deduce from A, and get it's parent, and its parent's parent, what if we get A again, if we continue, it will loop for ever. So in this case, we should return false, why?

A's parent array A[p'] is unqiue, A[p']'s parent A[p''] is also unique.
..
A[p'']
A[p']
A <--
..
...
A[p'']
A[p']
A <--
So the whole array sequence would be a loop. if we search from A, and meet A again, and no B during the path. So B would not be in the sequence.

Also remember that if the previous process determines whether B is in front of A in one sequence, we still need determine whether A is in front of B in some sequence.

Code:
The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/programmer-plus.
package org.codeexample.sameSequence;

import java.util.ArrayList;
import java.util.List;
import org.codeexample.common.Utils;

public class AlgorithmSameSequnce {

 /**
  * see
  * http://programer-tips.blogspot.com/2011/08/
         * two-integer-arrays-from-same-sequence.html
  * <p>
  * 
  * @param arrayA
  * @param arrayB
  * @return
  */
 public static boolean isInSameSequnce(int[] arrayA, int[] arrayB) {
  return isInSameSequnce(Utils.toList(arrayA), Utils.toList(arrayB));
 }

 /**
  * see
  * http://programer-tips.blogspot.com/2011/08/
         * two-integer-arrays-from-same-sequence.html
  */
 public static boolean isInSameSequnce(List<Integer> listA,
   List<Integer> listB) {
  List<Integer> listACopy = new ArrayList<Integer>(listA);
  if (isInSameSequnceImpl(listA, listACopy, listB))
   return true;
  List<Integer> listBCopy = new ArrayList<Integer>(listB);
  return isInSameSequnceImpl(listB, listBCopy, listA);
 }

 private static boolean isInSameSequnceImpl(List<Integer> listA,
   List<Integer> interim, List<Integer> listB) {
  List<Integer> previous = getPrevious(interim);
  if (previous.equals(listB))
   return true;
  // meet listA again
  if (previous.equals(listA))
   return false;
  if (previous.isEmpty())
   return false;
  return isInSameSequnceImpl(listA, previous, listB);
 }

 /**
  * Return the previous array, for example, the previous array of [2, 1]
  * would be [1, 1], the previous of [1, 2, 1, 1] would be [2, 1]. <br>
  * If the list is invalid or can't induce its previous array, return one
  * empty list.
  * 
  * @param list
  * @return
  */
 private static List<Integer> getPrevious(List<Integer> list) {
  ArrayList<Integer> result = new ArrayList<Integer>();
  // if the list has odd number, return empty list;
  if (list.size() % 2 == 1)
   return result;

  for (int i = 0; i <= list.size() - 2;) {
   int times = list.get(i++);

   // no previous row for input [0, 1],
   if (times == 0)
    return new ArrayList<Integer>();
   int digit = list.get(i++);
   for (int j = 0; j < times; j++) {
    result.add(digit);
   }
  }
  return result;
 }
}

Friday, August 5, 2011

Find all Concatenate Numbers - Sorted



In previous post, the returned results are unsorted, what we should do if we want to return these concatenate numbers in ascending order?

Question:
Given a unsorted list of positive numbers, you can concatenate them into one number in any order, how to print all unique possible numbers in ascending order?
For example, for input 2, 3, 1(or whatever order), the output would be always a sorted list of 6 integers: 123, 132, 213, 231, 312, 321.

Answer:
The main logic would still be same as the previous post. The main difference is how to ensure the returned concatenate numbers are sorted in ascending order?

One obvious way is that we sort the returned result, but this would take more time, the length of the result would be n!, so the time complexity would be O(n!log(n!)). This is undesired.

First we sort the parameter list in ascending order, then we assume the sub-result of a[1] to a[n-1] is sorted ascending order. When we add a[0] to all possible positions of previous sub result, what we need do to make the new list still sorted?

Take instance, for input, 3, 2, 1, first we sort them to 1, 2, 3, and assume the sub result of 2, 3 is sorted: [2,3], [3,2].
Now when add 1 to the zero index of [2,3], [3, 2], and we get [1,2,3], [1,3,2].
Now we loop each element, for each element, we add 1 to the possible positions from 1 to 2(length of the each element), so we get [2, 1, 3], [2, 3, 1], and [3, 1, 2], [3, 2, 1].

Code:
The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/programmer-plus.
package org.codeexample.concatNumber;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import org.codeexample.common.OverflowException;
import org.codeexample.common.Utils;
public class AllConcatNumberSorted {
 /**
  * This method would concatenate each integer value of the list in ascending
  * order.
  * 
  * @param la,
  *            a list of positive integer numbers
  * @return all unique concatenate integer numbers from the list in ascending
  *         order.
  * @throws IllegalArgumentException,
  *             if the parameter list contains negative value.
  * @throws OverflowException,
  *             it one possible concatenate integer number is greater than
  *             Integer.MAX_VALUE
  */
 public static List<Integer< concatNumbersSored(
   List<Integer< la)
   throws IllegalArgumentException,
   OverflowException {
  Collections.sort(la);
  Set<List<Integer<< permutations = concatNumbersSortedImpl(
    la, 0);
  List<Integer< results = new ArrayList<Integer<();
  for (List<Integer< intList : permutations) {
   int result = 0;
   for (int tmpInt : intList) {
    result = Utils.concat(result, tmpInt);
   }
   results.add(result);
  }
  return results;
 }
 private static Set<List<Integer<< concatNumbersSortedImpl(
   List<Integer< la, int level) {
  // use linked hash set to keep the inserted order.
  Set<List<Integer<< permutations = new LinkedHashSet<List<Integer<<();
  // base case
  if (level == la.size() - 1) {
   if (la.get(level) < 0)
    throw new IllegalArgumentException(
      "Invalid number: " + la.get(level));
   List<Integer< result = new LinkedList<Integer<();
   result.add(la.get(level));
   permutations
     .add(new LinkedList<Integer<(result));
   return permutations;
  }
  int head = la.get(level);
  if (head < 0)
   throw new IllegalArgumentException(
     "Invalid number: " + head);
  Set<List<Integer<< subPermutations = concatNumbersSortedImpl(
    la, ++level);
  // first insert head to the first position of the sub result
  for (List<Integer< tmpList : subPermutations) {
   List<Integer< tmp = new LinkedList<Integer<(
     tmpList);
   tmp.add(0, head);
   permutations.add(tmp);
  }
  for (List<Integer< tmpList : subPermutations) {
   // add head to other possible n positions
   for (int i = 1; i <= tmpList.size(); i++) {
    List<Integer< tmp = new LinkedList<Integer<(
      tmpList);
    tmp.add(i, head);
    permutations.add(tmp);
   }
  }
  return permutations;
 }
}

Thursday, August 4, 2011

Find all Concatenate Numbers - Unsorted



Question:
Given a list of positive numbers, you can concatenate them into one number in any order, how to print all unique possible numbers? In this question, the order of the result is not important.
For example, for input 1, 2, 3, the output would be a list of 6 integers: 123, 132, 213, 231, 312, 321.
Answer:
This is a classical dynamic programming problems, we can divide the integer list to two parts, a0, and [a, .., an-1], so if we know the result of the sub list[a, .., an-1], we can compute result of the whole integer list.
Take example, for 1, 23, 45. First, we compute the sub-result of 23, 45, the result would be [[23, 45], [45, 23]], then for each member of the sub-result, we add 1 to all possible positions.
First we add 1 to all possible positions of [23, 45], we will get three integer list, [[1, 23, 45], [23, 1, 45], [23, 45, 1]], then we add 1 to add 1 to all possible positions of [45, 23], the result would be [1, 45, 23], [45, 1, 23], [45, 23, 1]. So the all possible concatenate numbers of 1, 23, 45 would be 12345, 23145, 23451, 14523, 45123, 45231.
Code:
The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/programmer-plus.
package org.codeexample.concatNumber;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import org.codeexample.common.OverflowException;
import org.codeexample.common.Utils;
public class AllConcatNumberUnsorted {
 /**
  * This method would concatenate each integer value of the list in any
  * order.
  * 
  * @param la,
  *            a list of positive integer numbers
  * @return all unique concatenate integer numbers from the list
  * @throws IllegalArgumentException,
  *             if the parameter list contains negative value.
  * @throws OverflowException,
  *             it one possible concatenate integer number is greater than
  *             Integer.MAX_VALUE
  */
 public static List<Integer> concatNumbersUnsored(
   List<Integer> la)
   throws IllegalArgumentException,
   OverflowException {
  HashSet<List<Integer>> permutations = concatNumbersUnSortedImpl(
    la, 0);
  List<Integer> results = new ArrayList<Integer>();
  for (List<Integer> intList : permutations) {
   int result = 0;
   for (int tmpInt : intList) {
    result = Utils.concat(result, tmpInt);
   }
   results.add(result);
  }
  return results;
 }
 private static HashSet<List<Integer>> concatNumbersUnSortedImpl(
   List<Integer> la, int level) {
  HashSet<List<Integer>> permutations = new LinkedHashSet<List<Integer>>();
  // base case
  if (level == la.size() - 1) {
   if (la.get(level) < 0)
    throw new IllegalArgumentException(
      "Invalid number: " + la.get(level));
   List<Integer> result = new LinkedList<Integer>();
   result.add(la.get(level));
   permutations
     .add(new LinkedList<Integer>(result));
   return permutations;
  }
  int head = la.get(level);
  if (head < 0)
   throw new IllegalArgumentException(
     "Invalid number: " + head);
  HashSet<List<Integer>> subPermutations = concatNumbersUnSortedImpl(
    la, ++level);
  for (List<Integer> tmpList : subPermutations) {
   // add head to all possible n+1 positions
   for (int i = 0; i <= tmpList.size(); i++) {
    List<Integer> tmp = new LinkedList<Integer>(
      tmpList);
    tmp.add(i, head);
    permutations.add(tmp);
   }
  }
  return permutations;
 }
}

Tuesday, August 2, 2011

Auto Completion - Find Strings starting with Prefix



We are all familiar with the auto completion function provided by IDE, for example, in eclipse, if we type Collections.un, then eclipse would list all methods that start with "un" such as unmodifiableCollection, unmodifiableList etc.

So we have the following question:
You have a list of string, you need find all strings that starts with prefix provided repeatedly, how to do this efficiently?

Answer:
We need to preprocess the list of string, so later we can quickly search it.

One way is to sort the string list by alphabetical order, then when search with the prefix (say app), we binary search this list and get a lower index whose string is larger than “app”, and get a higher index whose string is less than “apr”, then all strings between the lower index and higher index[lower index, higher index) are the strings that starts with the prefix.
Each query would take O(longn), n is the length of the string list.

Another better way is to create a tree from the string list, for example, for string "append", it would look like this:
  [root node(flag)]
         /
        a
       / \
     [ST] p
          \
          p -- return all strings from this sub tree
         /
         e
         \
         n
        / \
        d [Sub Tree]
       /
[leaf node(flag)]
So when we search all strings that starts with "app", it can search this tree, and get all strings of the p node, the time complexity depends on the length of the prefix, having nothing to do with the length of the string list. This is much better.

Code:
The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/programmer-plus.
package org.codeexample.autocomplete;

public class WordTree {
 private WordNode root;
 public WordTree() {
  root = new WordNode(null);
 }
 /**
  * Add a string into this word tree, if word is null or an empty string, do
  * nothing
  */
 public void addWord(String word) {
  if (word == null)
   return;
  word = word.trim();
  if ("".equals(word)) {
   return;
  }
  WordNode parentNode = root, curretNode;
  for (int i = 0; i < word.length(); i++) {
   char character = word.charAt(i);
   Map<Character, WordNode> children = parentNode.getChildrenMap();
   if (children.containsKey(character)) {
    curretNode = children.get(character);
   } else {
    curretNode = new WordNode(character);
    parentNode.addChild(curretNode);
   }
   parentNode = curretNode;
  }
  // at last, add a leaf node - whose character value is null to indicate
  // the end of the word
  curretNode = new WordNode(null);
  parentNode.addChild(curretNode);
 }
 /**
  * @param prefix
  * @return all words in this tree that starts with the prefix, <br>
  *         if prefix is null, return an empty list, if prefix is empty
  *         string, return all words in this word tree.
  */
 public List<String> wordsPrefixWith(String prefix) {
  List<String> words = new ArrayList<String>();
  if (prefix == null)
   return words;
  prefix = prefix.trim();
  WordNode currentNode = root;
  for (int i = 0; i < prefix.length(); i++) {
   char character = prefix.charAt(i);
   Map<Character, WordNode> children = currentNode.getChildrenMap();
   if (!children.containsKey(character)) {
    return words;
   }
   currentNode = children.get(character);
  }
  return currentNode.subWords();
 }
 /**
  * @param word
  * @return whether this tree contains this word, <br>
  *         if the word is null return false, if word is empty string, return
  *         true.
  */
 public boolean hasWord(String word) {
  if (word == null)
   return false;
  word = word.trim();
  if ("".equals(word))
   return true;
  WordNode currentNode = root;
  for (int i = 0; i < word.length(); i++) {
   char character = word.charAt(i);
   Map<Character, WordNode> children = currentNode.getChildrenMap();
   if (!children.containsKey(character)) {
    return false;
   }
   currentNode = children.get(character);
  }
  // at last, check whether the parent node contains one null key - the
  // leaf node, if so return true, else return false.
  return currentNode.getChildrenMap().containsKey(null);
 }
}
class WordNode {
 private Character character;
 private WordNode parent;
 private Map<Character, WordNode> childrenMap = new HashMap<Character, WordNode>();
 public WordNode(Character character) {
  this.character = character;
 }
 /**
  * @return all strings of this sub tree
  */
 public List<String> subWords() {
  List<String> subWords = new ArrayList<String>();
  String prefix = getPrefix();
  List<String> noPrefixSubWords = subWordsImpl();
  for (String noPrefixSubWord : noPrefixSubWords) {
   subWords.add(prefix + noPrefixSubWord);
  }
  return subWords;
 }
 private List<String> subWordsImpl() {
  List<String> words = new ArrayList<String>();
  Iterator<Character> keyIterator = childrenMap.keySet().iterator();
  while (keyIterator.hasNext()) {
   Character key = keyIterator.next();
   if (key == null) {
    words.add(convertToString(this.character));
   } else {
    WordNode node = childrenMap.get(key);
    List<String> childWords = node.subWordsImpl();
    for (String childWord : childWords) {
     words.add(convertToString(this.character) + childWord);
    }
   }
  }
  return words;
 }
 public void addChild(WordNode child) {
  child.parent = this;
  childrenMap.put(child.getCharacter(), child);
 }
 public Character getCharacter() {
  return character;
 }
 public WordNode getParent() {
  return parent;
 }
 public Map<Character, WordNode> getChildrenMap() {
  return childrenMap;
 }
 private String convertToString(Character character) {
  return (character == null) ? "" : String.valueOf(character);
 }
 private String getPrefix() {
  StringBuilder sb = new StringBuilder();
  WordNode parentNode = this.parent;
  while (parentNode != null) {
   if (parentNode.getCharacter() != null) {
    sb.append(parentNode.getCharacter());
   }
   parentNode = parentNode.parent;
  }
  return sb.reverse().toString();
 }
}

Generate Max Number from an Integer Array



Question:
You are given a list of positive int numbers, find out the max number that can be comprised of these input int numbers.

Example:
For input 1, 2, 3, the max number would be 321.
For 8, 87, 896, the max number would be 896887.

Answer:
For example, if the numbers are 24, 243, 2435? The max number should be [2435][243][24].
Is there a way we can sort this array, and get a new array: [2435, 243, 24]?

When we sort this array, we can define a comparator. When it compares two numbers (say a and b), if the two numbers has same digit numbers, we directly compare it, if they have different digit numbers (say a has less digit numbers than b), for the number (a in this case) has less digit numbers, we would get a new int number (get a new int a0 from b) by right padding it with the original digit numbers, and get a new number a0, then compare a0 and b.

So when compare 24 and 2435, we would think we are actually comparing 2[424] and 2435, so in the descending sorted array, 2535 would come before 24.

So the descending sorted array would be [2435, 243, 24], as 2435 > 243[2] > 24[24]; the generated max number would be [2435][243][24], this would be exactly what we expect.

Code:
The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/programmer-plus.
package org.codeexample.maxNumber;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import org.codeexample.common.OverflowException;
import org.codeexample.common.Utils;
class MyComparator implements Comparator<Integer> {
	/**
	 * For input 87 and 8, it would return -1, for 89 and 8, return 1, for 88
	 * and 8, return 0.
	 */
	public int compare(Integer int1, Integer int2) {
		if (int1 == null)
			return -1;
		if (int2 == null)
			return 1;
		// if eqauls, return directly to improve efficiency.
		if (int1.equals(int2))
			return 0;
		int int1DigitNumber = Utils.getNumberOfDigits(int1), int2DigitNumber = Utils
				.getNumberOfDigits(int2);
		if (int1DigitNumber > int2DigitNumber) {
			int2 = rightPadNumber(int2, int1DigitNumber);
		} else if (int1DigitNumber < int2DigitNumber) {
			int1 = rightPadNumber(int1, int2DigitNumber);
		}
		return int1.compareTo(int2);
	}
	/**
	 * @param ia
	 * @param newDigitalNumber
	 * @return pad the number by the original digital numbers in order. <br>
	 *         For example, for input 98, 5, it would return 98989 - five
	 *         numbers.
	 * @throws IllegalArgumentException,
	 *             if the new digital number is less than the digital number of
	 *             the old integer.
	 * @throws OverflowException,
	 *             if the generated number would be larger than
	 *             Integer.MAX_VALUE
	 */
	public static int rightPadNumber(int ia,
			int newDigitalNumber)
			throws IllegalArgumentException,
			OverflowException {
		int oldNumbers = Utils.getNumberOfDigits(ia);
		if (oldNumbers > newDigitalNumber) {
			throw new IllegalArgumentException(
					"Invalid parameters: "
							+ ia
							+ " has "
							+ oldNumbers
							+ " digits, its larger than the specified new digit number: "
							+ newDigitalNumber);
		} else if (oldNumbers == newDigitalNumber) {
			return ia; // Improve efficiency.
		}
		// example: to pad 98 to five numbers: 98988.
		boolean negative = ia < 0;
		if (negative) {
			ia = -ia;
		}
		String orginalString = String.valueOf(ia);
		StringBuffer resultString = new StringBuffer(
				orginalString);
		int diff = newDigitalNumber - oldNumbers;
		while (diff >= oldNumbers) {
			resultString.append(orginalString);
			diff -= oldNumbers;
		}
		// now, result = 9898, diff = 1;
		if (diff > 0) {
			resultString.append(orginalString.substring(0,
					diff));
		}
		if (negative) {
			resultString.insert(0, "-");
		}
		try {
			return Integer.valueOf(resultString.toString());
		} catch (NumberFormatException e) {
			throw new OverflowException(e);
		}
	}
}
public class MaxNumber {
	/**
	 * @see org.codeexample.maxNumber#maxNumber(java.util.List)
	 */
	public static int maxNumber(int[] ia)
			throws IllegalArgumentException,
			OverflowException {
		return maxNumber(Utils.toList(ia));
	}
	/**
	 * @param la,
	 *            a list of positive Integer numbers
	 * @return the max value that is generated by concatting each Integer value<br>
	 *         For example, for input 8, 87, 89, it would return 89887
	 * @throws IllegalArgumentException,
	 *             if the parameters include negative number
	 * @throws OverflowException,
	 *             if the generated number would be larger than
	 *             Integer.MAX_VALUE
	 */
	public static int maxNumber(List<Integer> la)
			throws IllegalArgumentException,
			OverflowException {
		Collections.sort(la, new MyComparator());
		Collections.reverse(la);
		Iterator<Integer> iterator = la.iterator();
		int result = 0;
		while (iterator.hasNext()) {
			int tmpi = iterator.next();
			if (tmpi < 0) {
				throw new IllegalArgumentException(
						"The list contains negative number: "
								+ tmpi);
			}
			int digitNumber = Utils.getNumberOfDigits(tmpi);
			// result = (10^digitNumber)*result + tmpi;
			result = Utils.safeMultiply(new Double(Math
					.pow(10, digitNumber)).intValue(),
					result);
			result = Utils.safeAdd(result, tmpi);
		}
		return result;
	}
}

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts