Instantly share code, notes, and snippets.

# Woon Ket Wongwoonketwong

• Sort options
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);
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 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){
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)
 var findLevelLinkedList = function(root){ var queue = []; var linkedListArray = []; var level = 0; queue.push([root, level]); root.visit = true; while(queue.length !== 0){
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; };
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;
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){
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();
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--){
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.