Skip to content

Instantly share code, notes, and snippets.

Woon Ket Wong woonketwong

Block or report user

Report or block woonketwong

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
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);
@woonketwong
woonketwong / findSortedArrayOcurrence
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);
@woonketwong
woonketwong / commonAncestor
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;
@woonketwong
woonketwong / checkBST
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;
@woonketwong
woonketwong / containTrees
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){
@woonketwong
woonketwong / createMinimalBST
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);
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);
View breadthFirstSearch
function breadthFirstSearch(node){
// build a queue
var q = [];
// initialize q
q.push(node);
var currentNode = null;
View depthFirstSearch
function depthFirstSearch(node){
if (node === null) return;
// visit node
console.log(node.value);
node.visited = true;
for (var i = 0; i < node.children.length; i++){
if (node.children[i].visited === false){
depthFirstSearch(node.children[i]);
@woonketwong
woonketwong / findLocalMin
Created Feb 19, 2014
Suppose we are given an array A[1 .. n] with the special property that A[1] ≥ A[2] and A[n − 1] ≤ A[n]. We say that an element A[x] is a local minimum if it is less than or equal to both its neighbors, or more formally, if A[x − 1] ≥ A[x] and A[x] ≤ A[x + 1]. For example, there are five local minima in the following array: 9 7 7 2 1 3 7 5 4 7 3 3…
View findLocalMin
function findLocalMin(array, start, end){
var mid = Math.floor( (start + end)/2 );
if (((mid - 1) < 0) || ((mid + 1) >= array.length)) return null;
if (array[mid - 2] > array[mid - 1] && array[mid - 1] < array[mid]){
return array[mid-1];
} else if ( (array[mid-1] >= array[mid-2])){
return findLocalMin(array, start, mid);
} else {
You can’t perform that action at this time.