Daily Archives: February 1, 2015

Qaz

This problem is from careercup, link
Problem description:
1. qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.
for example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.
the question is to find the max qaz.

A brute force solution is to iterate each element, and find how many elements after and larger than it.
A O(nlogn) solution can be achieved by mergesort:
For each array, it has a maxQaz. Let’s consider to merge {33, 48, 26} and {58, 41, 59}.
Final result of 2 arrays are:
{26(0), 33(1), 48(0)}, leftQaz = 1.
{41(1), 58(1), 59(0)}, rightQaz = 1.
-initial added_qaz = 0,
-traverse both arrays from end to the beginning,
-move the pointer which is pointing to the bigger number,
—when moving the pointer of the right sub array, increase added_qaz
—when moving the pointer of the left sub array, apply added_qaz to qaz of pointed element before moving 
Because only left sub array is updated.
Now, left sub array should be {26(3), 33(4), 48(2)}. And we know leftQaz is 4.
Before return, we use merge sort to merge 2 subarrays, and got:
{26(3), 33(4), 41(1), 48(2), 58(1), 59(0)}.
Now, we should return max(leftQaz, rightQaz). The result would be 4.

The code is kinda long. Because we use mergesort, so 2 helper arrays for auxiliary space are used.

  1. package feb;
  2. public class QAZ {
  3.     public static void main(String[] args) {
  4.         int[] arr = { 7, 8, 2, 3, 4, 5 };
  5.         int qaz = qaz(arr);
  6.         System.out.println(qaz);
  7.     }
  8.     public static int qaz(int[] arr) {
  9.         int[] eleTimes = new int[arr.length];
  10.         int[] helperQaz = new int[arr.length];
  11.         int[] helperTimes = new int[arr.length];
  12.         return qazUtil(arr, eleTimes, 0, arr.length – 1, helperQaz, helperTimes);
  13.     }
  14.     /*
  15.      * Return qaz of arr[]
  16.      * @param qazArr[], qazArr[i] stores the qaz of element arr[i] from arr[start,…,end].
  17.      * @param start, the start position of arr[]
  18.      * @param end, the end position of arr[]
  19.      * @param helperQaz, this is a helper array for mergesort. It helps for arr[]
  20.      * @param helperTimes, a helper array for merge sort. It is temporary place for eleTimes
  21.      */
  22.     private static int qazUtil(int[] arr, int[] qazArr, int start, int end,
  23.             int[] helperQaz, int[] helperTimes) {
  24.         if (start > end) {
  25.             return 0;
  26.         }
  27.         if (start == end) {
  28.             return 0;
  29.         }
  30.         int mid = start + (end – start) / 2;
  31.         int qazLeft = qazUtil(arr, qazArr, start, mid, helperQaz, helperTimes);
  32.         int qazRight = qazUtil(arr, qazArr, mid + 1, end, helperQaz, helperTimes);
  33.         // 1. Update eleTimes in left part.
  34.         int pointerL = mid, pointerR = end;
  35.         int added = 0;
  36.         while (pointerL >= start) {
  37.             while (arr[pointerL] < arr[pointerR] && pointerR >= mid + 1) {
  38.                 pointerR–;
  39.                 added++;
  40.             }
  41.             qazArr[pointerL] += added;
  42.             qazLeft = (qazArr[pointerL] > qazLeft) ? qazArr[pointerL]: qazLeft;
  43.             pointerL–;
  44.         }
  45.         // 2. Mergesort left and right part into helperQaz, helperTimes
  46.         pointerL = start;
  47.         pointerR = mid + 1;
  48.         int helpIndex = start;
  49.         while (pointerL <= mid && pointerR <= end) {
  50.             if (arr[pointerL] < arr[pointerR]) {
  51.                 helperQaz[helpIndex] = arr[pointerL];
  52.                 helperTimes[helpIndex] = qazArr[pointerL];
  53.                 pointerL++;
  54.             } else {
  55.                 helperQaz[helpIndex] = arr[pointerR];
  56.                 helperTimes[helpIndex] = qazArr[pointerR];
  57.                 pointerR++;
  58.             }
  59.             helpIndex++;
  60.         }
  61.         while (pointerL <= mid) {
  62.             helperQaz[helpIndex] = arr[pointerL];
  63.             helperTimes[helpIndex] = qazArr[pointerL];
  64.             pointerL++;
  65.             helpIndex++;
  66.         }
  67.         while (pointerR <= end) {
  68.             helperQaz[helpIndex] = arr[pointerR];
  69.             helperTimes[helpIndex] = qazArr[pointerR];
  70.             pointerR++;
  71.             helpIndex++;
  72.         }
  73.         // 2.2 Copy result from helperQaz, helperTimes back to arr, eleTimes
  74.         for (int i = start; i <= end; i++) {
  75.             arr[i] = helperQaz[i];
  76.             qazArr[i] = helperTimes[i];
  77.         }
  78.         return Math.max(qazLeft, qazRight);
  79.     }
  80. }

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