Monthly Archives: November 2014

Check if a tree is a sum tree

This is the solution to here: link

  1. public class BuildSumTree {
  3.     public static void main(String[] args) {
  4.         Tree tree = Tree.getSumTree3();
  5.         System.out.println(ifSumTree(tree, new MyInteger(0)));
  6.     }
  8.     /*
  9.      * http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/
  10.      */
  11.     public static boolean ifSumTree(Tree tree, MyInteger sum){
  12.         if(tree==null||(tree.left==null&&tree.right==null)){    //return true if tree is null or leaf
  13.             sum.i = 0;
  14.             return true;
  15.         }
  16.         int lvalue = (tree.left==null)?0:tree.left.value;
  17.         int rvalue = (tree.right==null)?0:tree.right.value;
  18.         MyInteger lsum = new MyInteger(0);
  19.         MyInteger rsum = new MyInteger(0);
  20.         if(ifSumTree(tree.left, lsum)&&ifSumTree(tree.right, rsum)){
  21.             sum.i = lsum.i + rsum.i + lvalue+rvalue;
  22.             boolean result = sum.i==tree.value;
  23.             return result;
  24.         }
  25.         return false;
  26.     }
  28.     /*
  29.      * This is a sum tree. This tree will be checked if it is a sum tree
  30.      */
  31.     public static Tree getSumTree3(){
  32.         Tree t1 = new Tree(34);
  33.         Tree t2 = new Tree(12);
  34.         Tree t3 = new Tree(5);
  35.         Tree t4 = new Tree(3);
  36.         Tree t5 = new Tree(3);
  37.         Tree t6 = new Tree(2);
  38.         Tree t7 = new Tree(3);
  39.         Tree t8 = new Tree(1);
  40.         Tree t9 = new Tree(2);
  41.         Tree t10 = new Tree(1);
  42.         Tree t11 = new Tree(1);
  43.         Tree t12 = new Tree(1);
  44.         t1.left = t2;
  45.         t1.right = t3;
  46.         t2.left = t4;
  47.         t2.right = t5;
  48.         t4.left = t8;
  49.         t4.right = t9;
  50.         t5.left = t10;
  51.         t5.right = t11;
  52.         t11.right = t12;
  53.         t3.left = t6;
  54.         t3.right = t7;
  55.         return t1;
  56.     }
  57. }

Convert a given tree to sum tree

This is a solution to here: link

  1. public class BuildSumTree {
  3.     public static void main(String[] args) {
  4.         Tree tree = getSumTree();
  5.         tree = convertToSumTree(tree);
  6.     }
  8.     /*
  9.      * http://www.geeksforgeeks.org/convert-a-given-tree-to-sum-tree/
  10.      */
  11.     public static int convertToSumTree(Tree tree){
  12.         if(tree==null){
  13.             return 0;
  14.         }
  15.         int lvalue = (tree.left==null)?0:tree.left.value;
  16.         int rvalue = (tree.right==null)?0:tree.right.value;
  17.         tree.value = convertToSumTree(tree.left) + convertToSumTree(tree.right) + lvalue + rvalue;
  18.         return tree.value;
  19.     }
  21.     /*
  22.      * This tree will be converted to a sum tree.
  23.      */
  24.     public static Tree getSumTree(){
  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.         Tree t6 = new Tree(6);
  31.         t1.left = t2;
  32.         t1.right = t3;
  33.         t2.left = t4;
  34.         t2.right = t5;
  35.         t3.left = t6;
  36.         return t1;
  37.     }
  38. }

Page visit problem

This is for the amazon interview Round 3, Question 2. http://www.geeksforgeeks.org/amazon-interview-experience-set-149-campus-internship/
Design an efficient data structure which supports queries like the following:
Which page was visited by exactly 2 users in day?
Which page was visited by only one user exactly 2 times in a day?
Which page was visited by ‘User 3? more than 5 times in a day?

The basic idea is to use cross linkedlist to store the data. There are 3 types of class: User, Page, InfoNode.
Initial User[] user, Page[] page. user[] and page[] are the entries to find infoNode. Each element in user[], page[] will point to a infonode by the nextNodeByUser pointer or nextNodeByPage pointer.

The cross linkedlist are contructed by the following rules:
1. Elements in page[] are ordered by visitedUserNum parameter. In this way, it can use binary search to find “Which page was visited by exactly 2 users in day?”
2. For those page element with same visitedUserNum, they are sorted by visitedTimes.  In this way, it can use binary search to find “Which page was visited by only one user exactly 2 times in a day?”
3. Elements in user[] are sorted by their userId. For InfoNodes which are under same user, they are linked by nextNodeByUser. They are sorted by descended visit times. In this way, it can easily find “Which page was visited by ‘User 3? more than 5 times in a day?”

Please correct me if I’m wrong!

  1. /*
  2.  * Q2. Given a log file of page visits of a website by different users for a day.
  3.  * Entry in the log file is like this:
  4.  * User 1 visited Page 4
  5.  * User 3 visited Page 2
  6.  * User 7 visited Page 9
  7.  */
  8. class User{
  9.     int userId;
  10.     InfoNode firstUserNode;
  11. }
  12. class Page{
  13.     int pageId;
  14.     int visitedUserNum;    //indicate this page is visited by how many users;    pages are sorted by visitedUser.
  15.     int visitedTimes;    //indicate this page is visited by how many times in total;    pages with same visitedUser are internally sorted by visitTimes.
  16.     InfoNode firstPageNode;
  17. }
  18. /*
  19.  * UserNode LinkList is sorted by visiting times. From large to less. To solve question 3.
  20.  */
  21. class InfoNode{
  22.     int pageId;    //indicate the page it belongs
  23.     int userId;    //indicate the user it belongs
  24.     int times;    //indicate how many times has this user visit page_belong
  25.     InfoNode nextNodeByUser;
  26.     InfoNode nextNodeByPage;
  27. }

Find longest substring without repeating

http://www.geeksforgeeks.org/amazon-interview-experience-set-149-campus-internship/
Round3, Q1
Given a string, find the longest substring without repeating characters. For example, the longest substrings without repeating characters for “ABDEFGABEF” are “BDEFGA” and “DEFGAB”.

Instead of using a array for all 26 alphabets, I use hashmap to store the char which are already read.

/*
* http://www.geeksforgeeks.org/amazon-interview-experience-set-149-campus-internship/
* Round3, Q1
* Given a string, find the longest substring without repeating characters.
* For example, the longest substrings without repeating characters for “ABDEFGABEF” are “BDEFGA” and “DEFGAB”.
*/
import java.util.HashMap;

public class LengthOfLongestSubstringWithoutRepeating {

public static int findLongestSubstringWithoutRepeating(String s){
if(s==null){
return -1;
}
HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
int max_start = 0;        //Record the position where the max substring starts
int max_len = 1;        //Record the length of max substring
int curr_len = 1;        //Record the length of current substring
hm.put(s.charAt(0), 0);
for(int i=1;i<s.length();i++){
if((hm.get(s.charAt(i))==null)||(i-curr_len>hm.get(s.charAt(i)))){
//Current char hasn’t been read, or position of previous char c is not in the range of current substring
curr_len++;
hm.put(s.charAt(i), i);
}
else{
if(curr_len>max_len){    //Find a new max length, update the max_len
max_len = curr_len;
max_start = i – curr_len;
}
curr_len = i – hm.get(s.charAt(i));    //Calculate the new length of current substring
hm.put(s.charAt(i), i);
}
}
//        System.out.println(“max start:” + max_start);
//        System.out.println(“max len:” + max_len);
return max_len;
}

public static void main(String[] args) {
//String str = “abcdefeczqposc”;
String str = “GEEKSFORGEEKS”;
int max_len = findLongestSubstringWithoutRepeating(str);
System.out.println(max_len);
}

}

Find max difference two elements

http://www.geeksforgeeks.org/amazon-interview-experience-set-149-campus-internship/

  2. /*
  3.  * Q2. Given an array arr[] of integers, find out the maximum difference between any
  4.  * two elements such that larger element appears after the smaller number in arr[].
  5.  * Print the indices of the two elements also.
  6.  * Example: If array is [2, 3, 10, 6, 4, 8, 1] then returned value should be 8 (difference between 10 and 2).
  7.  * If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (difference between 7 and 9).
  8.  */
  9. public class MaxDifferenceTwoElement {
  11.     public static void main(String[] args) {
  12.         int[] array = {7, 9, 5, 6, 3, 2};
  13.         findMaxDifference(array);
  14.     }
  17.     public static void findMaxDifference(int[] array){
  18.         if(array==null){
  19.             return;
  20.         }
  21.         int min_pos = 0;    //position of min value
  22.         int max_pos = 0;    //position of max value
  23.         int max_gap = Integer.MIN_VALUE;
  24.         for(int i=1;i<array.length;i++){
  25.             if(array[i]-array[min_pos]>max_gap){
  26.                 max_pos = i;
  27.                 max_gap = array[i] – array[min_pos];
  28.             }
  29.             else if(array[i]<min_pos){
  30.                 min_pos = i;
  31.             }
  32.         }
  33.         System.out.println(max_gap);
  34.     }
  35. }

Find TopK value, by small heap

This is the code to get top k values from a input.

  1. /*
  2.  * Get the Top Largest K values from small heap
  3.  */
  4. public class TopK {
  6.     public static void main(String[] args) {
  7.         int[] array = {5, 13,10,12,15,11, 8,23, 40, 16, 83, 23, 31, 73, 59, 25, 75};
  8.         findTopK(array, 5);
  9.     }
  11.     public static void findTopK(int[] array, int k){
  12.         int[] heap = new int[k+1];
  13.         heap[0] = k;     //use heap[0] to record the length of heap
  14.         for(int i=0;i
  15.             heapPut(heap, array[i]);
  16.         }
  17.         printArray(heap);
  18.     }
  20.     /*
  21.      * Small heap, put value in heap
  22.      */
  23.     public static void heapPut(int[] heap, int value){
  24.         if(heap==null){
  25.             return;
  26.         }
  27.         if(value>heap[1]){
  28.             heap[1] = value;
  29.             heapAdjust(heap, 1);
  30.         }
  31.     }
  34.     /*
  35.      * Small heap, put value in heap
  36.      */
  37.     public static void heapAdjust(int[] heap, int pos){
  38.         if(heap==null||pos*2>heap[0]){    //heap is empty, or the position is not correct
  39.             return;
  40.         }
  41.         if(heap[pos]<=heap[pos*2]&&(heap[0]==pos*2||heap[pos]<=heap[pos*2+1])){
  42.         //the heap[pos] is already smallest
  43.      //heap[0]==pos*2 is to check if pos has right child. If it doesn’t has right child, then don’t compare with right child.
  44.             return;
  45.         }
  46.         int minPos = (heap[0]==pos*2)?pos*2:heap[pos*2]//heap[pos] is not the smallest, get the min pos
  48.         arrayExchange(heap, pos, minPos);
  49.         heapAdjust(heap, minPos);
  50.     }
  53.     /*
  54.      * Exchange pos1 and pos2 in array[]
  55.      */
  56.     public static void arrayExchange(int[] array, int pos1, int pos2){
  57.         if(array==null||pos1>array.length-1||pos2>array.length-1){
  58.             return;
  59.         }
  60.         int tmp = array[pos1];    array[pos1] = array[pos2]; array[pos2] = tmp;
  61.         return;
  62.     }
  64.     public static void printArray(int[] array){
  65.         if(array==null){
  66.             return;
  67.         }
  68.         for(int i=1;i
  69.             System.out.print(array[i]+” “);
  70.         }
  71.         System.out.println();
  72.     }
  73. }

find the path between nodes in binary tree

I made this code, it is because I saw there is a problem in geeksforgeeks: link
But it only gets the distance of 2 nodes. I’m thinking how to get the path of the 2 nodes. The idea is inspired by Pavel Fusu’s code. link

The process is below:
1. Find the lca node. link
2. Find the path1 and path2 from the lca to the designated nodes.
3. Merge path1 and path2

  1. public class LCA {
  3.     public static void main(String[] args) {
  4.         Tree tree = Tree.getTree();
  5.         ArrayList<Integer> path = findNodesPath(tree, 9, 18);
  6.         printPath(path);
  7.     }
  9.     /*
  10.      * Find the LCA of node1 and node2
  11.      */
  12.     public static Tree findLca(Tree tree, MyInteger lcaNum, int node1, int node2){
  13.         if(tree==null){
  14.             return null;
  15.         }
  16.         MyInteger lLca = new MyInteger(0);
  17.         Tree ltree = findLca(tree.left, lLca, node1, node2);
  18.         if(lLca.i==2){
  19.             lcaNum.i=2;
  20.             return ltree;
  21.         }
  22.         MyInteger rLca = new MyInteger(0);
  23.         Tree rtree = findLca(tree.right, rLca, node1, node2);
  24.         if(rLca.i==2){
  25.             lcaNum.i=2;
  26.             return rtree;
  27.         }
  28.         int selfLca = 0;
  29.         if(node1==tree.value||node2==tree.value){
  30.             selfLca = 1;
  31.         }
  32.         lcaNum.i = lLca.i + rLca.i + selfLca;
  33.         return tree;
  34.     }
  35.     /*
  36.      * Find the path of node under root.
  37.      */
  38.     public static boolean findPath(Tree root, int node, ArrayList<Integer> path){
  39.         if(root==null){
  40.             return false;
  41.         }
  42.         boolean lHas = findPath(root.left, node, path);
  43.         if(lHas){
  44.             path.add(root.value);
  45.             return true;
  46.         }
  47.         boolean rHas = findPath(root.right, node, path);
  48.         if(rHas){
  49.             path.add(root.value);
  50.             return true;
  51.         }
  52.         if(root.value==node){
  53.             path.add(root.value);
  54.             return true;
  55.         }
  56.         return false;
  57.     }
  59.     /*
  60.      * Find the path of node1(or node2) under root.
  61.      */
  62.     public static boolean findPath(Tree root, int node1, int node2, ArrayList<Integer> path){
  63.         if(root==null){
  64.             return false;
  65.         }
  66.         if(findPath(root.left, node1, node2, path)){
  67.             path.add(root.value);
  68.             return true;
  69.         }
  70.         if(findPath(root.right, node1, node2, path)){
  71.             path.add(root.value);
  72.             return true;
  73.         }
  74.         if(root.value==node1||root.value==node2){
  75.             path.add(root.value);
  76.             return true;
  77.         }
  78.         return false;
  79.     }
  81.     /*
  82.      * Find the path between node1 and node2
  83.      */
  84.     public static ArrayList<Integer> findNodesPath(Tree tree, int node1, int node2){
  85.         MyInteger lcaNum = new MyInteger(0);
  86.         Tree lca = findLca(tree, lcaNum, node1, node2);
  87.         if(lcaNum.i<2){
  88.             return null;
  89.         }
  90.         ArrayList<Integer> path1 = new ArrayList<Integer>();
  91.         ArrayList<Integer> path2 = new ArrayList<Integer>();
  92.         findPath(lca.left, node1, node2, path1);
  93.         findPath(lca.right, node1, node2, path2);
  94.         path1.add(lca.value);
  95.         while(!path2.isEmpty()){
  96.             path1.add(path2.remove(path2.size()-1));
  97.         }
  98.         return path1;
  99.     }
  101.     public static void printPath(ArrayList<Integer> path){
  102.         if(path==null){
  103.             return;
  104.         }
  105.         Iterator<Integer> itr = path.iterator();
  106.         while(itr.hasNext()){
  107.             System.out.print(itr.next()+” “);
  108.         }
  109.         System.out.println();
  110.     }
  111. }
  113. public class MyInteger{
  114.     public int i = 0;
  115.     public MyInteger(int i){
  116.         this.i = i;
  117.     }
  118.     public String toString(){
  119.         return String.valueOf(i);
  120.     }
  121. }

find lca(lowest common ancestry) in a binary tree 

public static Tree findLca(Tree tree, MyInteger lcaNum, int node1, int node2){
   if(tree==null){
      return null;
   }
   MyInteger lLca = new MyInteger(0);
   Tree ltree = findLca(tree.left, lLca, node1, node2);
   if(lLca.i==2){
      lcaNum.i=2;
      return ltree;
   }
   MyInteger rLca = new MyInteger(0);
   Tree rtree = findLca(tree.right, rLca, node1, node2);
   if(rLca.i==2){
      lcaNum.i=2;
      return rtree;
   }
   int selfLca = 0;
   if(node1==tree.value||node2==tree.value){
      selfLca = 1;
   }
   lcaNum.i = lLca.i + rLca.i + selfLca;
   return tree;
}

 

PostOrderTraverse

  1. public class PostOrderNonTraverse {
  3.     public static void main(String[] args){
  4.         Tree t17 = new Tree(17);
  5.         Tree t16 = new Tree(16);
  6.         Tree t15 = new Tree(15);
  7.         Tree t14 = new Tree(14);
  8.         Tree t13 = new Tree(13);
  9.         Tree t12 = new Tree(12);
  10.         Tree t11 = new Tree(11);
  11.         Tree t10 = new Tree(10);
  12.         Tree t9 = new Tree(9);
  13.         Tree t8 = new Tree(8);
  14.         Tree t7 = new Tree(7);
  15.         Tree t6 = new Tree(6);
  16.         Tree t5 = new Tree(5);
  17.         Tree t4 = new Tree(4);
  18.         Tree t3 = new Tree(3);
  19.         Tree t2 = new Tree(2);
  20.         Tree t1 = new Tree(1);
  21.         t8.left = t9;
  22.         t6.left = t8;
  23.         t5.right = t7;
  24.         t4.left = t5;
  25.         t4.right = t6;
  26.         t2.left = t4;
  27.         t1.left = t2;
  28.         t1.right = t3;
  29.         t6.right = t10;
  30.         t3.left = t11;
  31.         t3.right = t12;
  32.         t12.left = t13;
  33.         t12.right = t14;
  34.         t13.left = t15;
  35.         t13.right = t16;
  36.         PostTraverse(t1);
  37.     }
  39.     public static void PostTraverse(Tree tree){
  40.         ArrayList s = new ArrayList();
  41.         s.add(tree);
  42.         Tree prev = null;
  43.         Tree curr = null;
  44.         Tree next = null;
  45.         while(!s.isEmpty()){
  46.             curr = s.get(s.size()-1);
  47.             if(prev==null||prev.left==curr||prev.right==curr||(curr.left != prev)&&(curr.right != prev)){
  48.                 //新进来的
  49.                 if(curr.left==null&&curr.right==null){    //是叶子
  50.                     System.out.println(curr.value);
  51.                     s.remove(s.size()-1);
  52.                 }
  53.                 else{
  54.                     if(curr.right!=null){
  55.                         s.add(curr.right);
  56.                     }
  57.                     if(curr.left!=null){
  58.                         s.add(curr.left);
  59.                     }
  60.                 }
  61.             }
  62.             else if(curr.left == prev){    //从左子树返回的
  63.                 if(curr.right!=null){
  64.                     s.add(curr.right);
  65.                 }
  66.                 else{
  67.                     System.out.println(curr.value);
  68.                     s.remove(s.size()-1);
  69.                 }
  70.             }
  71.             else{    //从右子树返回
  72.                 System.out.println(curr.value);
  73.                 s.remove(s.size()-1);
  74.             }
  75.             prev = curr;
  76.         }
  77.     }
  78. }
  80. class Tree{
  81.     public Tree(int value){
  82.         this.value = value;
  83.     }
  84.     public Tree left;
  85.     public Tree right;
  86.     public int value;
  87. }

Solve the problem that hive is pending for a long time for MapReduce select

I have partition_table in Hive. It run the select command well:
Hive>select * from partition_table;

When I ran
Hive>select count(*) from partition_table;
Starting Job = job_1414213419655_0001, Tracking URL = http://centmaster:8088/proxy/application_1414213419655_0001/
Kill Command = /home/hadoop/hadoop-2.3.0/bin/hadoop job  -kill job_1414213419655_0001

After that, Hive is pending there for 40 minutes, until I pressed Ctrl+c to stop it.

I checked http://centmaster:8000/logs/yarn-root-nodemanager-centmaster.log, I found the Exception information:
mapreduce.shuffle set in yarn.nodemanager.aux-services is invalid.The valid service name should only contain a-zA-Z0-9_

and can not start with numbers

I googled it. I found out it is because the yarn.nodemanager.aux-services in yarn-site.xml is not correctly set.
I changed it from mapreduce.shuffle into mapreduce_shuffle.
mapreduce.shuffle is used in hadoop2.1, 2.2. mapreduce_shuffle shall be used in hadoop2.3.