Daily Archives: January 31, 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. }