jack-wong-build’s gists

jack-wong-build / mergeSort

Last active August 29, 2015 13:56

Merge sort

	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);

jack-wong-build / inOrderSucc

Created January 13, 2014 05:23

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

	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){

jack-wong-build / findLevelLinkedList

Created January 13, 2014 03:09

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){

jack-wong-build / createMinimalBST

Created January 12, 2014 20:13

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height

	var createMinimalBST = function(array){
	var makeNode = function(value){
	var obj = {
	value:value,
	left:null,
	right:null
	};
	return obj;
	};

jack-wong-build / searchNodeUsingDFS

Created January 12, 2014 19:09

Given a directed graph, design an algorithm to find out whether there is a route between two nodes using DFS.


	var search = function(startNode, endNode){

	//visit startNode
	console.log("Visting:", startNode.key);
	if (startNode.key === endNode.key){
	return true;
	}
	startNode.visit = true;

jack-wong-build / isBalanced

Last active January 3, 2016 01:19

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.

	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){

jack-wong-build / breathFirstSearch

Created January 12, 2014 18:01

Breath first search implementation with a queue.

	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();

jack-wong-build / insertionSort

Created January 12, 2014 06:12

Insertion sort in javascript

	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--){

jack-wong-build / quickSort

Created January 10, 2014 19:40

Quick sort implementation in JavaScript.

	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);

jack-wong-build / findLocInInterspersedSortedArr

Created December 31, 2013 20:07

A binary search function on a sorted array of strings which is interspersed with empty strings.

	var findLocInInterspersedSortedArr = function(strArr, target, first, last){
	var mid = Math.floor( last - first / 2);

	if (strArr[mid] === ''){
	var left = mid - 1;
	var right = mid + 1;

	while (true){
	if (left < first && right > last){
	return -1;

Jack Wong jack-wong-build