Instantly share code, notes, and snippets.

# Woon Ket Wongwoonketwong

• Sort options
Last active Aug 29, 2015
Merge sort
View mergeSort
 function mergeSort(array, start, end){ if (start === end) return [array[start]]; var mid = Math.floor( (start + end) / 2 ); var arr1 = mergeSort(array, start, mid); var arr2 = mergeSort(array, mid+1, end); var result = merge(arr1, arr2);
Created Feb 13, 2014
Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn).
View findSortedArrayOcurrence
 //1,2,3,4,4,4,4,4,5,6,7 function findFrequency(array, target){ var first, last; var result = -1; first = findFirst(array, target, 0, array.length-1); if (first !== -1){ last = findLast(array, target, 0, array.length-1);
Created Feb 18, 2014
Find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure.
View commonAncestor
 function covers(root, node){ if (root === null ) return false; if (root === node ) return true; return covers(root.left, node) || covers(root.right, node); } function commonAncestorHelper(root, node1, node2){ if (root === null ) return false; if (root === node1 || root === node2 ) return root;
Created Feb 17, 2014
Implement a function to check if a binary tree is a binary search tree.
View checkBST
 function checkBST(node){ lastVisited = null; function checkBSTRecurse (node){ if (node === null) return true; if ( !checkBSTRecurse(node.left) ) return false; if (node.val < lastVisited) return false;
Created Feb 17, 2014
Create an algorithm to decide if T2 is a subtree of T1.
View containTrees
 function containTrees(tree1, tree2){ if (tree2 === null){ return true; } return subTree(tree1, tree2); } function subTree(tree1, tree2){
Created Feb 17, 2014
Given a sorted array, write an algorithm to create a binary search tree with minimal height.
View createMinimalBST
 function createMinimalBST(array, start, end){ if (end < start){ return null; } var mid = Math.floor( (start + end) / 2 ); var node = {val: array[mid], left: null, right: null}; node.left = createMinimalBST(array, start, mid-1); node.right = createMinimalBST(array, mid+1, end);
Last active Aug 29, 2015
Quick sort.
View quickSort
 function quickSort(array, start, end){ var leftIndex = partition(array, start, end); if (start < leftIndex-1){ quickSort(array, start, leftIndex-1); } if (start > leftIndex){ quickSort(array, leftIndex, end);
Created Feb 18, 2014