jack-wong-build’s gists

jack-wong-build / airteaching-local-gateway-setting.txt

Last active July 31, 2021 15:26

local airteaching gateway setting

	#user nobody;
	worker_processes 1;

	#error_log logs/error.log;
	#error_log logs/error.log notice;
	#error_log logs/error.log info;

	#pid logs/nginx.pid;

jack-wong-build / findLocalMin

Created February 19, 2014 00:35

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 ﬁve local minima in the following array: 9 7 7 2 1 3 7 5 4 7 3 3…

	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 {

jack-wong-build / breadthFirstSearch

Created February 18, 2014 14:42

Breadth first search.

	function breadthFirstSearch(node){

	// build a queue
	var q = [];

	// initialize q
	q.push(node);

	var currentNode = null;

jack-wong-build / depthFirstSearch

Created February 18, 2014 14:32

Depth First Search

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

jack-wong-build / quickSort

Last active August 29, 2015 13:56

Quick sort.

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

jack-wong-build / commonAncestor

Created February 18, 2014 05:16

Find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure.

	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;

jack-wong-build / createMinimalBST

Created February 17, 2014 20:04

Given a sorted array, write an algorithm to create a binary search tree with minimal height.

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

jack-wong-build / containTrees

Created February 17, 2014 19:05

Create an algorithm to decide if T2 is a subtree of T1.


	function containTrees(tree1, tree2){
	if (tree2 === null){
	return true;
	}

	return subTree(tree1, tree2);
	}

	function subTree(tree1, tree2){

jack-wong-build / checkBST

Created February 17, 2014 18:21

Implement a function to check if a binary tree is a binary search tree.

	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;

jack-wong-build / findSortedArrayOcurrence

Created February 13, 2014 11:04

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

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

Jack Wong jack-wong-build