Added hard/max_heap_checker

bradhanson · bradhanson · commit 6ced3539c1f3 · 2018-07-16T09:15:41.000-04:00
diff --git a/hard/max_heap_checker.js b/hard/max_heap_checker.js
@@ -0,0 +1,69 @@
+/**
+ * Using the JavaScript language, have the function maxHeapChecker(arr) take arr
+ * which represents a heap data structure and determine whether or not it is a
+ * max heap. A max heap has the property that all nodes in the heap are either
+ * greater than or equal to each of its children. For example: if arr is
+ * [100,19,36,17] then this is a max heap and your program should return the
+ * string max. If the input is not a max heap then your program should return a
+ * list of nodes in string format, in the order that they appear in the tree,
+ * that currently do not satisfy the max heap property because the child nodes
+ * are larger than their parent. For example: if arr is [10,19,52,13,16] then
+ * your program should return 19,52.
+ *
+ * Another example: if arr is [10,19,52,104,14] then your program should return
+ * 19,52,104
+ *
+ * https://www.coderbyte.com/results/bhanson:Max%20Heap%20Checker:JavaScript
+ *
+ * @param  {array} arr
+ * @return {string}
+ */
+function maxHeapChecker(arr) {
+    // https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation
+
+    // Iterative solution: breadth-first search
+
+    const invalidNodes = [];
+
+    // Initialize to root, each successive queue will have the next level depth of indexes
+    let queue = [0];
+
+    arr.forEach(_ => {
+        const nextQueue = [];
+
+        queue.forEach(nodeIndex => {
+            const leftIndex = 2 * nodeIndex + 1;
+            const rightIndex = 2 * nodeIndex + 2;
+
+            if (leftIndex < arr.length) {
+                if (arr[leftIndex] > arr[nodeIndex]) {
+                    invalidNodes.push({
+                        index: leftIndex,
+                        value: arr[leftIndex]
+                    });
+                }
+                nextQueue.push(leftIndex);
+            }
+
+            if (rightIndex < arr.length) {
+                if (arr[rightIndex] > arr[nodeIndex]) {
+                    invalidNodes.push({
+                        index: rightIndex,
+                        value: arr[rightIndex]
+                    });
+                }
+                nextQueue.push(rightIndex);
+            }
+        });
+
+        queue = nextQueue;
+    });
+
+    if (invalidNodes.length === 0) {
+        return 'max';
+    }
+
+    return invalidNodes.map(node => node.value).join(',');
+}
+
+module.exports = maxHeapChecker;
diff --git a/hard/max_heap_checker.test.js b/hard/max_heap_checker.test.js
@@ -0,0 +1,25 @@
+const maxHeapChecker = require('./max_heap_checker');
+
+describe('maxHeapChecker()', () => {
+    test('passes Coderbyte.com tests', () => {
+        expect(maxHeapChecker([100, 19, 36, 17])).toBe('max');
+
+        expect(maxHeapChecker([10, 19, 52, 13, 16])).toBe('19,52');
+
+        expect(maxHeapChecker([10, 19, 52, 104, 14])).toBe('19,52,104');
+
+        expect(maxHeapChecker([73, 74, 75, 7, 2, 107])).toBe('74,75,107');
+
+        expect(maxHeapChecker([1, 5, 10, 2, 3])).toBe('5,10');
+
+        expect(maxHeapChecker([5, 2, 1, 1, 1])).toBe('max');
+
+        expect(maxHeapChecker([86, 100, 2])).toBe('100');
+
+        expect(maxHeapChecker([73, 74, 81, 79, 90])).toBe('74,81,79,90');
+
+        expect(maxHeapChecker([73, 72, 1, 79, 90])).toBe('79,90');
+
+        expect(maxHeapChecker([100, 99, 98, 97, 96, 95, 94])).toBe('max');
+    });
+});
