Skip to content

Instantly share code, notes, and snippets.

@woonketwong
woonketwong / 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;
@woonketwong
woonketwong / 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 five 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 {
@woonketwong
woonketwong / 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;
@woonketwong
woonketwong / 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]);
@woonketwong
woonketwong / 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);
@woonketwong
woonketwong / 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;
@woonketwong
woonketwong / 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);
@woonketwong
woonketwong / 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){
@woonketwong
woonketwong / 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;
@woonketwong
woonketwong / 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);