Monthly Archives: January 2015

Detect circle in graph

1. Delete edge. Delete the node which in-degree is 0, and the edges starting from it. In the end, there is no circle if all nodes are deleted.

2. Use DFS. It is similar to detecting cut point in a graph. Store the DFS visited sequence for each node. And find the back edge of each node. If a node back edge points to an earlier node, then there is a circle.

Next greater element

This one is from g4g. link
Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.
This is actually a pratice for stack.

  1. package feb;
  2. import java.util.Stack;
  3. public class NextGreaterElement {
  4.     public static void main(String[] args) {
  5.         int[] arr = { 11, 13, 3, 21, 7, 6, 4, 9, 12, 15 };
  6.         Element[] arrEle = getNGE(arr);
  7.         for (int i = 0; i < arrEle.length; i++) {
  8.             System.out.println(arrEle[i]);
  9.         }
  10.     }
  11.     /*
  12.      * http://www.geeksforgeeks.org/next-greater-element/ Using stack pratice.
  13.      * Given an array, print the Next Greater Element (NGE) for every element.
  14.      * The Next greater Element for an element x is the first greater element on
  15.      * the right side of x in array. Elements for which no greater element
  16.      * exist, consider next greater element as -1. Examples: a) For any array,
  17.      * rightmost element always has next greater element as -1. b) For an array
  18.      * which is sorted in decreasing order, all elements have next greater
  19.      * element as -1. c) For the input array [4, 5, 2, 25}, the next greater
  20.      * elements for each element are as follows.
  21.      *
  22.      * Element NGE
  23.      * 4 –> 5
  24.      * 5 –> 25
  25.      * 2 –> 25
  26.      * 25 –> -1
  27.      *
  28.      * d) For the input array
  29.      * [13, 7, 6, 12}, the next greater elements for each element are as
  30.      * follows.     *
  31.      * Element NGE
  32.      * 13 –> -1
  33.      * 7 –> 12
  34.      * 6 –> 12
  35.      * 12 –> -1
  36.      */
  37.     public static Element[] getNGE(int[] arr) {
  38.         if (arr == null) {
  39.             return null;
  40.         }
  41.         Element[] arrEle = new Element[arr.length];
  42.         for (int i = 0; i < arr.length; i++) {
  43.             arrEle[i] = new Element(arr[i], i);
  44.         }
  45.         Stack<Element> s = new Stack<Element>();
  46.         s.push(arrEle[0]);
  47.         for (int i = 1; i < arrEle.length; i++) {
  48.             while (!s.empty() && arrEle[i].value > s.peek().value) {
  49.                 Element ele = s.pop();
  50.                 arrEle[ele.pos].nge = arrEle[i].value;
  51.             }
  52.             s.push(arrEle[i]);
  53.         }
  54.         // rest elements in stack has no next larger element.
  55.         while (!s.empty()) {
  56.             Element ele = s.pop();
  57.             arrEle[ele.pos].nge = -1;
  58.         }
  59.         return arrEle;
  60.     }
  61.     static class Element {
  62.         int value;
  63.         int nge;
  64.         int pos;
  65.         Element(int value, int pos) {
  66.             this.value = value;
  67.             this.pos = pos;
  68.         }
  69.         @Override
  70.         public String toString() {
  71.             return value + “\t” + nge;
  72.         }
  73.     }
  74. }

Sort array to bst

The problem is from g4g. link
Problem: Given a sorted array. Write a function that creates a Balanced Binary Search Tree using array elements.
Basic idea is to create the tree by the middle position. Then recursively create the left sub tree and right sub tree by left part array and right part array.

  1. package feb;
  2. public class SortArrayToBST {
  3.     public static void main(String[] args) {
  4.         int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  5.         Tree t = getBSTBySortedArray(arr);
  6.     }
  7.     public static Tree getBSTBySortedArray(int[] arr) {
  8.         if (arr == null) {
  9.             return null;
  10.         }
  11.         return getBSTBySortedArrayUtil(arr, 0, arr.length – 1);
  12.     }
  13.     public static Tree getBSTBySortedArrayUtil(int[] arr, int start, int end) {
  14.         if (start > end) {
  15.             return null;
  16.         }
  17.         if (start == end) {
  18.             return new Tree(arr[start]);
  19.         }
  20.         int mid = (start + end) >> 1;
  21.         Tree tree = new Tree(arr[mid]);
  22.         tree.left = getBSTBySortedArrayUtil(arr, start, mid – 1);
  23.         tree.right = getBSTBySortedArrayUtil(arr, mid + 1, end);
  24.         return tree;
  25.     }
  26.     static class Tree {
  27.         int value;
  28.         Tree left;
  29.         Tree right;
  30.         Tree(int value) {
  31.             this.value = value;
  32.         }
  33.     }
  34. }

Cycle queue

This is a practice for cycle queue. Cycle queue uses array to store elements. Main character of cycle queue is that it allocate space for one time. When deQueue and enQueue, it saves time for space allocation compared to normal queue. Disadvantage is that the lenght is constant once it initializes.

  1. package jan;
  2. public class CycleQueue {
  3.     private int[] queue;
  4.     private final int len;
  5.     private int rear;
  6.     private int front;
  7.     CycleQueue(int len) {
  8.         this.len = len + 1;
  9.         queue = new int[this.len];
  10.         rear = front = 0;
  11.     }
  12.     int deQueue() {
  13.         if (front == rear) {
  14.             throw new RuntimeException(“queue is empyt now.”);
  15.         }
  16.         int result = queue[front];
  17.         front = (front + 1) % len;
  18.         return result;
  19.     }
  20.     void enQueue(int value) {
  21.         if ((rear + 1) % len == front) {
  22.             throw new RuntimeException(“queue is full now.”);
  23.         }
  24.         queue[rear] = value;
  25.         rear = (rear + 1) % len;
  26.     }
  27.     void print() {
  28.         for (int i = front; i != rear; i = (i + 1) % len) {
  29.             System.out.print(queue[i] + “\t”);
  30.         }
  31.         System.out.println();
  32.     }
  33.     public static void main(String[] args) {
  34.         CycleQueue queue = new CycleQueue(3);
  35.         queue.enQueue(1);
  36.         queue.enQueue(2);
  37.         queue.enQueue(3);
  38.         System.out.println(queue.deQueue());
  39.         queue.enQueue(4);
  40.         System.out.println(queue.deQueue());
  41.         queue.enQueue(5);
  42.         queue.print();
  43.         System.out.println();
  44.     }
  45. }

Find the first value smaller than target value in sorted array

This is a practice for binary search. The aim is to find the first element in an sorted array, which is smaller than a target value.
For example:
arr = {1, 3, 4, 6, 7}, value = 5. Returns 2.
arr = {1, 2, 5, 5, 5, 5, 6}, value = 5. Returns 1.
arr = {2, 3, 4}, value = 5. Return 2.
arr = {2, 3, 4}, value = 1. Return -1.

  1. public class FindFirstSmallerInSortedArray {
  2.     public static void main(String[] args) {
  3.         // System.out.println((4>>1));
  4.         int[] arr = { 3, 4, 5, 6, 6, 6, 6, 6, 6, 6, 7, 8 };
  5.         int index = findIndexBS(arr, 3);
  6.         if (index == -1) {
  7.             System.out.println(“no exist”);
  8.         } else {
  9.             System.out.println(arr[index]);
  10.         }
  11.     }
  12.     /*
  13.      * Return the index in sorted array, which value in index is the first one smaller than value.
  14.      * Return -1 if the result is not found.
  15.      * It uses binary search.
  16.      * For example, arr = {1, 3, 4, 6, 7}, value = 5. It returns 2.
  17.      * arr = {1, 2, 5, 5, 5, 5, 6}, value = 5. It returns 1.
  18.      * arr = {2, 3, 4}, value = 5. Return 2.
  19.      * arr = {2, 3, 4}, value = 1. Return -1.
  20.      *
  21.      * @param, arr[]. arr is a sorted input array
  22.      * @param, value. The value which is firstly larger than result.
  23.      */
  24.     public static int findIndexBS(int[] arr, int value) {
  25.         if (arr == null || value <= arr[0]) {
  26.             return -1;
  27.         }
  28.         if(value > arr[arr.length – 1]){
  29.             return arr.length – 1;
  30.         }
  31.         return findIndexBSUtil(arr, 0, arr.length – 1, value);
  32.     }
  33.     public static int findIndexBSUtil(int[] arr, int start, int end, int value) {
  34.         if (start > end) {
  35.             return -1;
  36.         }
  37.         int mid = start + ((end – start) >> 1);
  38.         if (value > arr[mid] && value <= arr[mid + 1]) {
  39.             return mid;
  40.         }
  41.         if (arr[mid] >= value) {
  42.             return findIndexBSUtil(arr, start, mid – 1, value);
  43.         }
  44.         return findIndexBSUtil(arr, mid + 1, end, value);
  45.     }
  46. }

Weighted Job Scheduling

This problem is from G4G link. It is a pratice for DP.

Problem Description:
Given N jobs where every job is represented by following three elements of it.
1) Start Time
2) Finish Time.
3) Profit or Value Associated.
Find the maximum profit subset of jobs such that no two jobs in the subset overlap.

Example:
Input: Number of Jobs n = 4
Job Details {Start Time, Finish Time, Profit}
Job 1:  {1, 2, 50}
Job 2:  {3, 5, 20}
Job 3:  {6, 19, 100}
Job 4:  {2, 100, 200}
Output: The maximum profit is 250.
We can get the maximum profit by scheduling jobs 1 and 4.
Note that there is longer schedules possible Jobs 1, 2 and 3
but the profit with this schedule is 20+50+100 which is less than 250.

Analysis:
This problem is quite similar to “Buy Sell stock to get maximum profit at most k times” and “0-1 knapsack” problem. First, all jobs should be ascending sorted by end time. I define 2 array: local[] and global[].
local[i] is the max profit when ith job is assigned by the time of job[i].end_time.
global[i] is the max profit by the time of job[i].end_time.

local[i] = job[i].profit + global[j]
the jth job is the first job before ith job, where job[j].end_time <= job[i].start_time. This process can be shorted to O(logn) time by binary search.
global[i] = max{ local[i], global[i – 1] }
At the job[i].end_time, the max is either the max profit when ith job is assigned, or global[i – 1]

The following is my code:

  1. package dp;
  2. import java.util.ArrayList;
  3. import java.util.Collections;
  4. import java.util.Comparator;
  5. import java.util.List;
  6. public class MaxWorkProfit {
  7.     public static void main(String[] args) {
  8.         Job j1 = new Job(1, 2, 50);
  9.         Job j2 = new Job(3, 5, 20);
  10.         Job j3 = new Job(6, 19, 100);
  11.         Job j4 = new Job(2, 100, 200);
  12.         Job j5 = new Job(19, 20, 60);
  13.         Job j6 = new Job(20, 21, 60);
  14.         List jobs = new ArrayList();
  15.         jobs.add(j1);
  16.         jobs.add(j2);
  17.         jobs.add(j3);
  18.         jobs.add(j4);
  19.         jobs.add(j5);
  20.         jobs.add(j6);
  21.         int max_profit = getMaxProfit(jobs);
  22.         System.out.println(max_profit);
  23.     }
  24.     public static int getMaxProfit(List job) {
  25.         Collections.sort(job, new JobComparator());
  26.         // local[i] is the max profit when jobi is assigned.
  27.         int[] local = new int[job.size()];
  28.         // global[i] is by the end time of jobi, the max profit.
  29.         int[] global = new int[job.size()];
  30.         local[0] = job.get(0).profit;
  31.         global[0] = job.get(0).profit;
  32.         for (int i = 1; i < job.size(); i++) {
  33.             Job curr_job = job.get(i);
  34.             // find the i, where endi<=startn. This find can be optimized to
  35.             // binary search
  36.             for (int j = i – 1; j >= 0; j–) {
  37.                 if (job.get(j).end <= curr_job.start) {
  38.                     local[i] = global[j];
  39.                     break;
  40.                 }
  41.             }
  42.             local[i] += curr_job.profit;
  43.             global[i] = Math.max(local[i], global[i – 1]);
  44.         }
  45.         return global[job.size() – 1];
  46.     }
  47.     static class Job {
  48.         int start;
  49.         int end;
  50.         int profit;
  51.         Job(int start, int end, int profit) {
  52.             this.start = start;
  53.             this.end = end;
  54.             this.profit = profit;
  55.         }
  56.     }
  57.     static class JobComparator implements Comparator {
  58.         public int compare(Job j1, Job j2) {
  59.             return j1.end – j2.end;
  60.         }
  61.     }
  62. }

Order statistic tree

According to wikipedia link, order statistic tree mainly offers 2 following functions:
Select(i) — find the i’th smallest element stored in the tree
Rank(x) – find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree

In order to find the rank/index, it is important to find the left subtree rank, and right subtree rank. After researching on character of order statistic tree, I conducted the following formula.
Let t_rank be rank of current tree, lr_num be number of left right subtree, r_num be number of right subtree, rr_num be right right subtree.
rank of left sub tree = t_rank – 1 – lr_num
rank of right sub tree = t_rank + r_num – rr_num

This following code is a try for order statistic binary tree. I didn’t write the construction for it, only wrote select and rank function.

  1. import util.Tree;
  2. public class OrderedStatisticTree {
  3.     public static void main(String[] args) {
  4.         Tree tree = Tree.getOrderStatisticBinaryTree();
  5.         int rank = rank(tree, 17);
  6.         System.out.println(rank);
  7.         Tree index_tree = index(tree, 10);
  8.         System.out.println(index_tree);
  9.     }
  10.     /*
  11.      * Return the rank of value in tree
  12.      */
  13.     public static int rank(Tree tree, int value) {
  14.         if (tree == null) {
  15.             return -1;
  16.         }
  17.         int rank = tree.num;
  18.         while(tree!=null){
  19.             rank = rank – (tree.right == null ? 0 : tree.right.num);
  20.             if (value == tree.value) {
  21.                 return rank;
  22.             }
  23.             if (value < tree.value) {
  24.                 rank = rank – 1;
  25.                 tree = tree.left;
  26.             } else {
  27.                 rank = (tree.right == null) ? -1 : rank + tree.right.num;
  28.                 tree = tree.right;
  29.             }
  30.         }
  31.         return -1;
  32.     }
  33.     /*
  34.      * Return the tree, which ranks index.
  35.      */
  36.     public static Tree index(Tree tree, int index) {
  37.         if (tree == null) {
  38.             return null;
  39.         }
  40.         int curr_index = tree.num;
  41.         while(tree!=null){
  42.             curr_index = curr_index – (tree.right == null ? 0 : tree.right.num);
  43.             if (curr_index == index) {
  44.                 return tree;
  45.             }
  46.             if (index < curr_index) {
  47.                 curr_index = curr_index – 1;
  48.                 tree = tree.left;
  49.             } else {
  50.                 curr_index = (tree.right == null) ? 0 : curr_index + tree.right.num;
  51.                 tree = tree.right;
  52.             }
  53.         }
  54.         return null;
  55.     }
  56. }

Following auxiliary Tree class helps to create a order statistic tree.

  1. package util;
  2. public class Tree{
  3.     public Tree(int value){
  4.         this.value = value;
  5.     }
  6.     public Tree(String value){
  7.         this.valueString = value;
  8.     }
  9.     public Tree(int value, int num){
  10.         this.value = value;
  11.         this.num = num;
  12.     }
  13.     public Tree left;
  14.     public Tree right;
  15.     public int value;
  16.     public String valueString;
  17.     /*
  18.      * This is used for ordered statistics binary tree
  19.      * To store the number under tree.
  20.      */
  21.     public int num;    //
  23.     public static Tree getOrderStatisticBinaryTree(){
  24.         Tree t15 = new Tree(15, 15);
  25.         Tree t10 = new Tree(10, 6);
  26.         Tree t20 = new Tree(20, 8);
  27.         Tree t8 = new Tree(8, 2);
  28.         Tree t13 = new Tree(13, 3);
  29.         Tree t17 = new Tree(17, 3);
  30.         Tree t23 = new Tree(23, 4);
  31.         Tree t7 = new Tree(7, 1);
  32.         Tree t11 = new Tree(11, 1);
  33.         Tree t14 = new Tree(14, 1);
  34.         Tree t16 = new Tree(16, 1);
  35.         Tree t18 = new Tree(18, 1);
  36.         Tree t22 = new Tree(22, 2);
  37.         Tree t24 = new Tree(24, 1);
  38.         Tree t21 = new Tree(21, 1);
  39.         t15.left = t10; t15.right = t20;
  40.         t10.left = t8; t10.right = t13;
  41.         t20.left = t17; t20.right = t23;
  42.         t8.left = t7;
  43.         t13.left = t11; t13.right = t14;
  44.         t17.left = t16; t17.right = t18;
  45.         t23.left = t22; t23.right = t24;
  46.         t22.left = t21;
  47.         return t15;
  48.     }
  50.     @Override
  51.     public String toString(){
  52.         return String.valueOf(value);
  53.     }
  54. }

Find the sequence in an array with largest sum

Problem: For any given input of numbers, find the maximum sum in a range (x, y| x<=y), the sum is defined as (A[i]+ A[i+1] + … + A[j]) where x<=i<=j<=y.
This problem can be solved by greedy algotithm:

  1. public class LargestSequence {
  2.     public static void main(String[] args) {
  3.         int[] arr = { -3, -4, 3, 2, 5, -6, 3, 5, 1, -3, -2, -90, 10 };
  4.         Interval result = findLargestSequence(arr);
  5.         System.out.println(result);
  6.     }
  7.     /*
  8.      * For any given input of numbers, find the maximum sum in a range (x, y| x<=y),
  9.      * the sum is defined as (A[i]+ A[i+1] + … + A[j]) where x<=i<=j<=y.
  10.      * @param the input array. element in array can be either posivie or negative.
  11.      */
  12.     public static Interval findLargestSequence(int[] arr) {
  13.         if (arr == null || arr.length == 0) {
  14.             return null;
  15.         }
  16.         Interval curr_interval = new Interval(0, 0);
  17.         Interval max_interval = new Interval(0, 0);
  18.         int max_sum = arr[0];
  19.         int curr_sum = arr[0];
  20.         for (int i = 1; i < arr.length; i++) {
  21.             curr_sum += arr[i];
  22.             curr_interval.y = i;
  23.             if (curr_sum > max_sum) {
  24.                 max_sum = curr_sum;
  25.                 max_interval.x = curr_interval.x;
  26.                 max_interval.y = curr_interval.y;
  27.             }
  28.             if (curr_sum < 0) {
  29.                 curr_interval.x = i + 1;
  30.                 curr_sum = 0;
  31.             }
  32.         }
  33.         return max_interval;
  34.     }
  35.     static class Interval {
  36.         int x;
  37.         int y;
  38.         int max_sum;
  39.         Interval(int x, int y) {
  40.             this.x = x;
  41.             this.y = y;
  42.         }
  43.         @Override
  44.         public String toString() {
  45.             return “(” + this.x + “, ” + this.y + “)”;
  46.         }
  47.     }
  48. }

Find range in BST

This is a practice for Tree. The idea is to find all results in a certain range in BST.

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import util.Tree;
  4. public class FindRangeInBst {
  5.     public static void main(String[] args) {
  6.         Tree bst = Tree.getBst();
  7.         List<Tree> result = new ArrayList<Tree>();
  8.         findRangeInBst(bst, 11, 16, result);
  9.         System.out.println(result.toString());
  10.     }
  11.     public static void findRangeInBst(Tree tree, int min, int max,
  12.             List<Tree> result) {
  13.         if (tree == null) {
  14.             return;
  15.         }
  16.         if (tree.value >= min && tree.value <= max) {
  17.             result.add(tree);
  18.             findRangeInBst(tree.left, min, max, result);
  19.             findRangeInBst(tree.right, min, max, result);
  20.         } else if (tree.value < min) {
  21.             findRangeInBst(tree.right, min, max, result);
  22.         } else {
  23.             findRangeInBst(tree.left, min, max, result);
  24.         }
  25.     }
  26. }

About Github

These 2 days, I did research about github. Let me write down my learning summary.
1. What is github?
It is a version control platform. It can record the changes of a project, and can help developers to collaboratively develop one project together.

2. Repository
It is actually a directory. And it is the unit where a project exists.

3. Branch
Branch is like a copy of a project. You want to modify a project based on an original one, but you don’t want to affect the original one. At this time, make a new branch of it, and modify based on the branch.

4. Clone
It is actually downloading a project. Download a project to your own laptop. After that, you can modify the project as  you want.

5. Fork
You want to contribute to someone’s project, you can click fork. In this way, this project will exist in your own github, and you can modify it as you want. After you done with that, do pull request to the project owner.

Following are some useful commands I summarized:
make current directory working repository
>git init

initialize existing directory
>git init

clone repository
>git clone https://github.com/libgit2/libgit2
or clone to a new directory
>git clone https://github.com/libgit2/libgit2 mylibgit

change file, and push it to your own remote github
>git add [file_name]
>git add .    //this is to add all changed files
>git add A    //this is to add all changed files
>git commit    -m “commit message”    //commit, save the change
>git push origin master    //origin is the remote name, master is the branch you are using.

add remote to master
>git remote add origin https://github.com/user/repo.git

In local master, do merge from branch2
>git merge branch2

check status
>git status

check current git account
>git config user.name
>git config –list

create a new branch
>git checkout -b [name_of_your_new_branch]

switch branch
>git checkout [name_of_branch]

get local repository updated
>git pull origin master

add a new branch
>git branch [new_branch_name]

change to a branch
>git checkout [branch_name]

git push origin master
This pushes to origin from local master to origin master branch

git push origin local-name:remote-name
This pushes on origin, local-branch to remote-branch.
Normally when I do a push in git I do something like git push origin master, which really means push from the local branch named master to the remote branch named master. If you want to push to a remote branch with a different name than your local branch, separate the local and remote names with a colon:

git push origin [local-commit]:remote-branch
push local commit to remote branch in origin

git push origin [local-commit]:remote-branch -f
This one will force push, regardless if there is conflict between local and remote branch

git remote –v
show all remote repos. After this command, we can see where origin is from