Monthly Archives: February 2015

Detect circle in directed graph — DFS

To detect circle in directed graph, it is important to mark the node with 3 types:
1. Node hasn’t been visited yet.
2. Node is being visiting which means node is processing, but it hasn’t finished DFS of all outgoing edges.
3. Node is visited, which means not only node itself, but also outgoing edges have been finished DFS.

  1. package feb;
  2. import java.util.HashMap;
  3. import java.util.HashSet;
  4. import java.util.Set;
  5. public class DetectCircleInGraph_DFS {
  6.     public static boolean hasCircle(HashMap graph) {
  7.         HashMap visited = new HashMap();
  8.         for (Node node : graph.values()) {
  9.             if (hasCircleUtil(graph, visited, node)) {
  10.                 return true;
  11.             }
  12.         }
  13.         return false;
  14.     }
  15.     public static boolean hasCircleUtil(HashMap graph,
  16.             HashMap visited, Node node) {
  17.         if (visited.get(node.ch) == NodeStatus.VISITED) {
  18.             return false;
  19.         }
  20.         if (visited.get(node.ch) == NodeStatus.ON_VISITING) {
  21.             return true;
  22.         }
  23.         visited.put(node.ch, NodeStatus.ON_VISITING);
  24.         for (Node nextNode : node.outgoing) {
  25.             if (hasCircleUtil(graph, visited, nextNode)) {
  26.                 return true;
  27.             }
  28.         }
  29.         visited.put(node.ch, NodeStatus.VISITED);
  30.         return false;
  31.     }
  32.     enum NodeStatus {
  33.         ON_VISITING, VISITED
  34.     }
  35.     public static class Node {
  36.         char ch;
  37.         Set outgoing = new HashSet();
  38.         int seq;
  39.         char ancestry; // indicate ancestry of the node, led by back edge.
  40.         Node(char ch) {
  41.             this.ch = ch;
  42.         }
  43.     }
  44.     public static void main(String[] args) {
  45.         Node a = new Node(‘a’);
  46.         Node b = new Node(‘b’);
  47.         Node c = new Node(‘c’);
  48.         Node d = new Node(‘d’);
  49.         Node e = new Node(‘e’);
  50.         a.outgoing.add(b);
  51.         b.outgoing.add(c);
  52.         b.outgoing.add(e);
  53.         b.outgoing.add(d);
  54.         c.outgoing.add(e);
  55.         e.outgoing.add(d);
  56.         d.outgoing.add(a);
  57.         HashMap graph = new HashMap();
  58.         graph.put(a.ch, a);
  59.         graph.put(b.ch, b);
  60.         graph.put(c.ch, c);
  61.         graph.put(d.ch, d);
  62.         graph.put(e.ch, e);
  63.         boolean hasCircle = hasCircle(graph);
  64.         System.out.println(hasCircle);
  65.     }
  66. }

Find the median in an array, by using heap

This is a practice for heap. The problem is from this blog: link

check my recent code on github by PriorityQueue: link

  1. package feb;
  2. public class FindMedian {
  3.     /*
  4.      * Return the median of arr[]. It uses a max heap, min heap. Keep the number
  5.      * of elements in 2 heaps differ less than 1.
  6.      */
  7.     public static int findMedian(int[] arr) {
  8.         if (arr == null) {
  9.             return -1;
  10.         }
  11.         if (arr.length == 1) {
  12.             return arr[0];
  13.         }
  14.         if (arr.length == 2) {
  15.             return arr[0] < arr[1] ? arr[0] : arr[1];
  16.         }
  17.         int[] maxHeap = new int[arr.length / 2 + 2];
  18.         int[] minHeap = new int[arr.length / 2 + 2];
  19.         maxHeap[0] = arr[0] < arr[1] ? arr[0] : arr[1];
  20.         minHeap[0] = arr[0] > arr[1] ? arr[0] : arr[1];
  21.         for (int i = 1; i < maxHeap.length; i++) {
  22.             maxHeap[i] = Integer.MIN_VALUE;
  23.             minHeap[i] = Integer.MAX_VALUE;
  24.         }
  25.         int[] maxHeapNum = new int[1];
  26.         maxHeapNum[0] = 1;
  27.         int[] minHeapNum = new int[1];
  28.         minHeapNum[0] = 1;
  29.         for (int i = 2; i < arr.length; i++) {
  30.             if (arr[i] < maxHeap[0]) {
  31.                 insertMaxHeap(maxHeap, arr[i], maxHeapNum);
  32.             } else {
  33.                 insertMinHeap(minHeap, arr[i], minHeapNum);
  34.             }
  35.             if (minHeapNum[0] – maxHeapNum[0] > 1) {
  36.                 int moveEle = removeMinHeapTop(minHeap, minHeapNum);
  37.                 insertMaxHeap(maxHeap, moveEle, maxHeapNum);
  38.                 continue;
  39.             }
  40.             if (maxHeapNum[0] – minHeapNum[0] > 1) {
  41.                 int moveEle = removeMaxHeapTop(maxHeap, maxHeapNum);
  42.                 insertMinHeap(maxHeap, moveEle, minHeapNum);
  43.                 continue;
  44.             }
  45.         }
  46.         return minHeapNum[0] > maxHeapNum[0] ? minHeap[0] : maxHeap[0];
  47.     }
  48.     /*
  49.      * Insert value to max heap arr[]. maxHeapNum[] records the element number
  50.      * of heap.
  51.      */
  52.     public static void insertMaxHeap(int[] arr, int value, int[] maxHeapNum) {
  53.         arr[maxHeapNum[0]] = value;
  54.         for (int i = maxHeapNum[0]; i > 0; i = (i – 1) >> 1) {
  55.             if (arr[i] > arr[(i – 1) >> 1]) {
  56.                 int tmp = arr[i];
  57.                 arr[i] = arr[(i – 1) >> 1];
  58.                 arr[(i – 1) >> 1] = tmp;
  59.                 continue;
  60.             }
  61.             break;
  62.         }
  63.         maxHeapNum[0]++;
  64.     }
  65.     /*
  66.      * Return the top of max heap of arr[]. maxHeapNum[] records the element
  67.      * number of heap.
  68.      */
  69.     public static int removeMaxHeapTop(int[] arr, int[] maxHeapNum) {
  70.         maxHeapNum[0]–;
  71.         int result = arr[0];
  72.         arr[0] = arr[maxHeapNum[0]];
  73.         arr[maxHeapNum[0]] = Integer.MIN_VALUE;
  74.         for (int i = 0; i <= (maxHeapNum[0] – 1) >> 1;) {
  75.             int maxPos = arr[i * 2 + 1] > arr[i * 2 + 2] ? i * 2 + 1
  76.                     : i * 2 + 2;
  77.             if (arr[maxPos] > arr[i]) {
  78.                 int tmp = arr[maxPos];
  79.                 arr[maxPos] = arr[i];
  80.                 arr[i] = tmp;
  81.                 i = maxPos;
  82.                 continue;
  83.             }
  84.             return result;
  85.         }
  86.         return result;
  87.     }
  88.     /*
  89.      * Return the top of min heap of arr[]. minHeapNum[] records the element
  90.      * number of heap.
  91.      */
  92.     public static int removeMinHeapTop(int[] arr, int[] minHeapNum) {
  93.         minHeapNum[0]–;
  94.         int result = arr[0];
  95.         arr[0] = arr[minHeapNum[0]];
  96.         arr[minHeapNum[0]] = Integer.MAX_VALUE;
  97.         for (int i = 0; i <= (minHeapNum[0] – 1) >> 1;) {
  98.             int minPos = arr[i * 2 + 1] < arr[i * 2 + 2] ? i * 2 + 1
  99.                     : i * 2 + 2;
  100.             if (arr[minPos] < arr[i]) {
  101.                 int tmp = arr[minPos];
  102.                 arr[minPos] = arr[i];
  103.                 arr[i] = tmp;
  104.                 i = minPos;
  105.                 continue;
  106.             }
  107.             return result;
  108.         }
  109.         return result;
  110.     }
  111.     /*
  112.      * Insert value to min heap arr[]. minHeapNum[] records the element number
  113.      * of heap.
  114.      */
  115.     public static void insertMinHeap(int[] arr, int value, int[] minHeapNum) {
  116.         arr[minHeapNum[0]] = value;
  117.         for (int i = minHeapNum[0]; i > 0; i = (i – 1) >> 1) {
  118.             if (arr[i] < arr[(i – 1) >> 1]) {
  119.                 int tmp = arr[i];
  120.                 arr[i] = arr[(i – 1) >> 1];
  121.                 arr[(i – 1) >> 1] = tmp;
  122.                 continue;
  123.             }
  124.             break;
  125.         }
  126.         minHeapNum[0]++;
  127.     }
  128.     public static void main(String[] args) {
  129.         int[] arr = { 1, 2, 3, 6, 7, 8, 9, 5 };
  130.         int median = findMedian(arr);
  131.         System.out.println(median);
  132.     }
  133. }