Daily Archives: December 16, 2014

Find the median in an array

Problem: If a random array is [2, 20, 40, 60, 50, 65, 25, 10, 30, 35,  52, 63, 67, 3], find the median of the array.

1. For each new Element in array, if it is less than the root of max heap, put it in the max heap; or put it in the min heap.
2. Adjust 2 heaps, in order that number of element in 2 heaps differ less than 1.
If element numbers in 2 heaps differ more than 1, put the root of the heap which has more element in the heap which has less element. Adjust 2 heaps.

Put all elements into 2 heaps.
If number of elements are the same, the median is (root_of_max_heap + root_of_min_heap) / 2.
If number of elements are not the same, the median is the root of heap which has more element.

Division with cycle remainder

Divide number and return result in form of a string. e.g 100/3 result should be 33.(3) Here 3 is in brackets because it gets repeated continuously and 5/10 should be 0.5.

The essence is to use hashmap to restore the remainder. Once a certain remainder was obtained for 2nd time, we found the recycles.

  1. public class DivisionWithCycleRemainder {
  4.     public static void main(String[] args){
  5.         String result = divisionToString(45,17);
  6.         System.out.println(result);
  7.     }
  9.     public static String divisionToString(int num1, int num2) {
  10.         int beforeD = num1 / num2;    //the result before dot
  11.         int afterD = num1 % num2;    //the result after dot
  12.         if(afterD==0){
  13.             return String.valueOf(beforeD);
  14.         }
  15.         HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
  16.         StringBuffer result = new StringBuffer(beforeD + “.”);
  17.         int remainder = afterD * 10;
  18.         while(!hm.containsKey(remainder)){
  19.             hm.put(remainder, result.length());    //remainder never exist, insert into hm
  20.             int curr_value = remainder / num2;    //result of current position
  21.             result.append(curr_value);
  22.             remainder = (remainder % num2) * 10;
  23.         }
  24.         result.insert(hm.get(remainder).intValue(), ‘(‘);
  25.         result.append(‘)’);
  26.         return result.toString();
  27.     }
  28. }

Construct BST by in-order traversal

Given a sequence of an in-order traversal 4,3,1,2,7,5,8, construct the BST.

The basic idea:
The idea is that a sub-tree can be buildt only if the next value is within the  min and max value of its current node..

On thing which needs to be mentioned, is that there is not unique BST for a in-order traversal sequence.

public class ConstructBSTPreOrder {

public static void main(String[] args) {
int[] array = {4,3,1,2,7,5,8};
MyInteger pos = new MyInteger(0);
Tree tree = constructBSTByPreOrder(array, pos, Integer.MIN_VALUE, Integer.MAX_VALUE);
System.out.println(tree);
}

public static Tree constructBSTByPreOrder(int[] array, MyInteger pos, int min, int max){
if(array==null||pos.i>=array.length){
return null;
}
if(array[pos.i]<min||array[pos.i]>max){
return null;
}
Tree tree = new Tree(array[pos.i]);
pos.i++;
tree.left = constructBSTByPreOrder(array, pos, min, tree.value);
tree.right = constructBSTByPreOrder(array, pos, tree.value, max);
return tree;
}
}