Monthly Archives: December 2014

Find weighted median in an array — meeting problem

Problem description:
Assume in x-coodinate, there are  cities. The city i locates at xi position, and has pi people. Now people in those cities want to find a place to have a meeting. We should find the location l, where it spend least cost for all people(make the following formula smallest).

We know how to find the median. Just get the middle number. For example, 1 2 3 5 6, the median is 3.
What if each number has a weight?
For example numbers: 1 2 3 5 6
weights:1 3 2 2 5
In this case, we just discrete the numbers by its weight. So, the number sequence will become:
1 2 2 2 3 3 5 5 6 6 6 6 6
Find the median of the new sequence, which is 5.
Accordingly, we solved the meeting problem above.

Burning candle problem

Problem description:
You are given n candles with size of each candle present as an element in an integer array i.e a[i] represent length of ith candle. There is a tradition according to which you celebrate by lighting a candle every night. The candles are lit such that there are k candles lit on the kth day. For ex. 1 candle on day 1 , 2 candles on day 2 and so on. Each night a candle burns 1 inch.
you need to write a program to find out maximum number of days you can celebrate the tradition with the n candles and their lengths?

In my opinon, it is a greedy algorithms. The trick of this quesiton, is that you burn those longest candle for each day. Until one day, you can’t find enough candles to burn. Use a descend linked-list to store the candle. Each time, select the candles from the beginning of the array.

Arrange the integers 1 to N such the position of the average of two numbers (if present) falls outside the two numbers

Problem: Given a positive integer N, arrange the integers 1 to N such the position of the average of two numbers (if present) falls outside the two numbers. For example, for a[i] and a[j], if b = (a[i] + a[j])/2, then if a[k] = b, k < i or k > j. Hint :- If the average of two numbers is not

The right solution is follow:
Let’s say you started with 1 2 3 4 5 6 7 8 9 10 11 12.
1 2 3 4 5 6 7 8 9 10 11 12 ->
2 4 6 8 10 12 (0 mod 2) | 1 3 5 7 9 11 (1 mod 2) ->
4 8 12 (0 mod 4) | 2 6 10 (2 mod 4) || 1 5 9 (1 mod 4) | 3 7 11 (3 mod 4) ->
8 (0 mod 8) | 4 12 (4 mod 8) || 2 10 (2 mod 8) | 6 (6 mod 8) ||| 1 9 (1 mod 8) | 5 (5 mod 8) || 3 11 (3 mod 8) | 7 (7 mod 8).
Now all the partitions are size 2 or smaller, so we’re done. The final result is 8 4 12 2 10 6 1 9 5 3 11 7. I invite you to verify that all constraints are satisfied.

Here, I want to write why it use the modulo.
Let’s consider about some numbers which the modulo is 8( x, which x mod 8 = 7): 7, 15, 23, 31, 39, 47, 55
Because all modulo of each number is 7, there is probability that average of 2 numbers are still in this group. (7+7)/2=7
For example ( 15 + 31 ) / 2=23, 23
in another way, it is  ( 8+7 + 3*8+7) /2 = (2*8+7), (2*8+7) mod 8 = 7, so there is still chance that average of 2 numers is still in this group.

So, we need to break this group into new 2 groups. Let’s those numbers modula 16, then the modulas are:
7    15    23    31    39    47    55
7    15    7      15    7      15     7

Divide them into 2 groups according to new modula: 7    23    39    55,    15    31    47
In this way, any x in [7, 23, 39, 55], and any y in [15, 31, 47], (x+y)/2 mod 16 won’t be 7, nor 15.

For example, (55+47)/2 mod 16 = (16*3+7 + 16*2+15)/2 mod 16.
The idealism is that 16 can be removed, it will be like (7+15)/2 mod 16 = 11( the 2 groups are value of mod 7 or 15)
So, we say average of 2 numbers in different group, won’t exist in either group.

Catalan numbers

These numbers are catalan numbers:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452
F(0) = 1
F(1) = 1
F(2) = 2
F(3) = 5
F(4) = 14
….

The formula of catalan could be:

Some cases of catalan numbers are below:
:


Actually, the dyck word and parentheses groups are the same of stack in-out sequence.


Focus on a certain point, try to draw a chord from a that point, which can divide rest of the points into 2 even parts.

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

Find the largest BST in a Binary Tree

http://www.geeksforgeeks.org/find-the-largest-subtree-in-a-tree-that-is-also-a-bst/

Given a Binary Tree, write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST). If the complete Binary Tree is BST, then return the size of whole tree.

  1. public class FindLargestBST {
  3.     public static Tree getTree(){
  4.         Tree t50 = new Tree(50);
  5.         Tree t30 = new Tree(30);
  6.         Tree t60 = new Tree(60);
  7.         Tree t5 = new Tree(5);
  8.         Tree t20 = new Tree(20);
  9.         Tree t45 = new Tree(45);
  10.         Tree t70 = new Tree(70);
  11.         Tree t65 = new Tree(65);
  12.         Tree t80 = new Tree(80);
  13.         t50.left = t30;
  14.         t50.right = t60;
  15.         t30.left = t5;
  16.         t30.right = t20;
  17.         t60.left = t45;
  18.         t60.right = t70;
  19.         t70.left = t65;
  20.         t70.right = t80;
  21.         return t50;
  22.     }
  24.     public static Tree getTree2(){
  25.         Tree t1 = new Tree(1);
  26.         Tree t2 = new Tree(2);
  27.         Tree t3 = new Tree(3);
  28.         Tree t4 = new Tree(4);
  29.         Tree t5 = new Tree(5);
  30.         t5.left = t2;
  31.         t5.right = t4;
  32.         t2.left = t1;
  33.         t2.right = t3;
  34.         return t5;
  35.     }
  36.     public static void findLargestBST(Tree tree, LargestBSTData data){
  37.         if(tree==null){
  38.             data.size = 0;
  39.             data.isBST = true;
  40.             data.tree = null;
  41.             return;
  42.         }
  43.         LargestBSTData ldata = new LargestBSTData();
  44.         LargestBSTData rdata = new LargestBSTData();
  45.         findLargestBST(tree.left, ldata);
  46.         findLargestBST(tree.right, rdata);
  47.         //when left-subtree and right-subtree are both BST, check if tree is a BST.
  48.         if(ldata.isBST&&rdata.isBST){
  49.             boolean lBST = false;    //if left-subtree and tree can be treated as BST.
  50.             boolean rBST = false;    //if right-subtree and tree can be treated as BST.
  51.             if(tree.left==null||tree.left.value<tree.value){
  52.                 lBST  = true;
  53.             }
  54.             if(tree.right==null||tree.right.value>tree.value){
  55.                 rBST  = true;
  56.             }
  57.             if(lBST&&rBST){    //tree is a BST
  58.                 data.size = ldata.size + rdata.size + 1;
  59.                 data.tree = tree;
  60.                 data.isBST = true;
  61.                 return;
  62.             }
  63.         }
  64.         //tree is not a BST
  65.         data.size = ldata.size>rdata.size?ldata.size:rdata.size;
  66.         data.tree = ldata.size>rdata.size?ldata.tree:rdata.tree;
  67.         data.isBST = false;
  68.     }
  70.     public static void main(String[] args) {
  71.         Tree tree = getTree();
  72.         LargestBSTData data = new LargestBSTData();
  73.         findLargestBST(tree, data);
  74.         System.out.println(data.size);
  75.     }
  77. }
  79. class LargestBSTData{
  80.     public Tree tree;   //to indicate the largest BST of current tree
  81.     public boolean isBST;    //to indicate if current tree is a BST
  82.     public int size;   //to indicate the size of the largest BST of current tree
  83. }