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
@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);
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 / inOrderSucc
Created Jan 13, 2014
Write an algorithm to find the ‘next’ node (e g , in-order successor) of a given node in a binary search tree where each node has a link to its parent
View inOrderSucc
var inOrderSucc = function(node){
var p = null;
if (node !== null){
if (node.parent === null || node.right !== null){
p = leftMostChild(node.right);
console.log("result=", p);
} else {
while ((p = node.parent) !== null){
if (p.left === node){
@woonketwong
woonketwong / findLevelLinkedList
Created Jan 13, 2014
Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists)
View findLevelLinkedList
var findLevelLinkedList = function(root){
var queue = [];
var linkedListArray = [];
var level = 0;
queue.push([root, level]);
root.visit = true;
while(queue.length !== 0){
@woonketwong
woonketwong / createMinimalBST
Created Jan 12, 2014
Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height
View createMinimalBST
var createMinimalBST = function(array){
var makeNode = function(value){
var obj = {
value:value,
left:null,
right:null
};
return obj;
};
@woonketwong
woonketwong / searchNodeUsingDFS
Created Jan 12, 2014
Given a directed graph, design an algorithm to find out whether there is a route between two nodes using DFS.
View searchNodeUsingDFS
var search = function(startNode, endNode){
//visit startNode
console.log("Visting:", startNode.key);
if (startNode.key === endNode.key){
return true;
}
startNode.visit = true;
@woonketwong
woonketwong / isBalanced
Last active Jan 3, 2016
Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.
View isBalanced
var isBalanced = function(node){
var maxDepth = function(node){
if (node === undefined){
return 0;
}
return 1 + Math.max(maxDepth(node.next[0]), maxDepth(node.next[1]));
}
var minDepth = function(node){
@woonketwong
woonketwong / breathFirstSearch
Created Jan 12, 2014
Breath first search implementation with a queue.
View breathFirstSearch
var breathFirstSearch = function(node){
var queue = [];
// visit root
console.log("Node key, value", node.key, node.value);
root.visit=true;
queue.push(root);
while(queue.length !== 0){
currentNode = queue.pop();
@woonketwong
woonketwong / insertionSort
Created Jan 12, 2014
Insertion sort in javascript
View insertionSort
var insertionSort = function(array){
var target;
var sortedIndex = 0;
var targetIndex;
for(var i = 0; i < array.length; i++){
target = array[i];
targetIndex = i;
for(var j = i; j >= sortedIndex; j--){
@woonketwong
woonketwong / quickSort
Created Jan 10, 2014
Quick sort implementation in JavaScript.
View quickSort
var quickSort = function(array, left, right){
var leftIndex = partition(array, left, right);
if (left < leftIndex - 1){
quickSort(array, left, leftIndex-1);
}
if (right > leftIndex){
quickSort(array, leftIndex, right);
You can’t perform that action at this time.