Skip to content

Instantly share code, notes, and snippets.

View jinwolf's full-sized avatar

Jin jinwolf

  • Chime
  • San Francisco
View GitHub Profile
@jinwolf
jinwolf / postorder_binary_traversal.js
Created January 14, 2018 01:32
Postorder binary tree traversal with a single stack
class Node {
constructor(val) {
this.value = val;
this.left = null;
this.right = null;
}
}
let nodes = [
new Node('a'), //0
@jinwolf
jinwolf / find_repeat_big.js
Created March 26, 2016 21:05
Find the first duplicate number in the list where the range is 1:n+1 and the size of the array is n that implies there should be at least one duplicate in the list
'use strict'
var num_list_1 = [3, 4, 2, 3, 1, 5];
var num_list_2 = [3, 1, 2, 2];
var num_list_3 = [4, 3, 1, 1, 4];
function find_duplicate(num_list) {
// initializing
var slowIndex = num_list.length - 1;
var fastIndex = num_list.length - 1;
@jinwolf
jinwolf / find_repeat.js
Created February 29, 2016 05:21
Finding a repeated number using pigeon hole principle
'use strict'
// pigeon hole theory
// number range 1 - n
// array length n + 1
const num_list = [10, 2, 4, 3, 2, 5, 6, 9, 8, 7, 1];
const num_list2 = [10, 2, 4, 3, 5, 6, 9, 8, 7, 1, 8];
function findDuplicate(num_list) {
@jinwolf
jinwolf / breadth_first_search.js
Created January 30, 2016 15:49
breadth first search binary tree in JavaScript
function TreeNode(value) {
this.value = value;
this.left = null;
this.right = null;
}
var root = new TreeNode(15);
root.left = new TreeNode(7);
root.right = new TreeNode(26);
root.left.left = new TreeNode(1);
@jinwolf
jinwolf / HashMap.js
Created January 5, 2016 21:52
(JavaScript) Hash map implementation
function Pair(key, value) {
this.key = key;
this.value = value;
this.next = null;
}
function HashMap(size) {
size = size || 35;
var storage = new Array(35);
@jinwolf
jinwolf / unbounded_knapsack_recursive.js
Created January 5, 2016 19:54
(JavaScript) Knapsack problem in a recursive way
function CakeType(weight, value) {
this.weight = weight;
this.value = value;
}
var cakeTypes = [
new CakeType(7, 160),
new CakeType(3, 90),
new CakeType(2, 15),
];
@jinwolf
jinwolf / unbounded_knapsack.js
Created January 5, 2016 01:48
(JavaScript) Knapsack problem
function CakeType(weight, value) {
this.weight = weight;
this.value = value;
}
var cakeTypes = [
new CakeType(7, 160),
new CakeType(3, 90),
new CakeType(2, 15),
];
@jinwolf
jinwolf / queue_with_stacks.js
Created December 31, 2015 06:58
Queue implementation using two stacks (JavaScript)
function Queue() {
var inStack = [];
var outStack = [];
this.enqueue = function(num) {
inStack.push(num);
}
this.dequeue = function() {
if (outStack.length > 0) {
@jinwolf
jinwolf / merge_sorted_arrays.js
Last active December 31, 2015 06:34
Merge sorted arrays into one (JavaScript)
var sorted_lists = [
[3, 4, 6, 10, 11, 15],
[1, 5, 8, 12, 14, 19],
[2, 7, 9, 13, 16, 17, 18],
[20, 22, 23, 25]
];
function mergeSortedArrays(sortedLists) {
var pointers = new Array(sortedLists.length);
@jinwolf
jinwolf / binary_search.js
Created December 19, 2015 23:34
Builds a binary tree from a sorted array and searches a value using the binary tree (JavaScript)
function Node(val) {
this.value = val;
this.left = null;
this.right = null;
}
var numList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function buildTree(list, start, end) {
if (start > end) {