Skip to content

Instantly share code, notes, and snippets.

@ddallala

ddallala/index.html

Created January 31, 2018 05:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ddallala/276d81c161741dbe8d462c0bd631b2ec to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ddallala/276d81c161741dbe8d462c0bd631b2ec to your computer and use it in GitHub Desktop.
Download ZIP
JS Bin Algorithms // source https://jsbin.com/domixaq
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta name="description" content="Algorithms">
<meta charset="utf-8">
<meta name="viewport" content="width=device-width">
<title>JS Bin</title>
</head>
<body>
<script id="jsbin-javascript">
// 16.1 Given a sorted array of positive integers with an empty spot at the end, insert an element in sorted order
function insertEl(a,n){
console.log(a);
var found = false;
var next_val;
for(var i=0; i<a.length;i++){
// end of the array
if(a.length==(i+1)){ // at the last spot
if(!found) a[i] = n;
else a[i] = next_val;
}
// place it at i and move all other elements
else {
if(!found) {
if(n<a[i]) {
found = true;
next_val = a[i];
a[i] = n;
}
} else {
var tmp_val = next_val;
next_val = a[i];
a[i] = tmp_val;
}
}
}
console.log(a)
}
insertEl([1, 3, 5, 10, 15, 20, 22, 24, ""],25);
// 16.2 Rever the order of elements in an array without creating a new array
function reverseArray(a){
console.log(a);
for(var i=0; i < a.length/2; i++){
var j = a.length - 1 - i;
var tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
console.log(a);
}
reverseArray([1,2,3,4,5]);
// 163. Given two lists (A and B) of unique strings, determine if A is a subset of B
function isSubset(a,b){
// transform b into a hash
var b_hash = {};
for(var i=0; i<b.length;i++){
b_hash[b[i]] = true;
}
// loop through a to see if a is in b_has
for(var j=0;j<a.length;j++){
if(!b_hash[a[j]]) return false;
}
return true;
}
console.log(isSubset([1,5],[1,2,3,4]));
console.log(isSubset([1,4],[1,2,3,4]));
// 16.4 given a two dimensional array of sales data where first column is prod ID and second column
//.. is quantity. Return a new 2 D array with Totals for each product ID
function getTotals(a){
var totals_hash = {};
for(var i=0;i<a.length;i++){
// check if does not exist, else create
if(totals_hash[a[i][0]] === undefined) totals_hash[a[i][0]] = 0;
// add to the hash
totals_hash[a[i][0]] += a[i][1];
}
// transform hash into array
console.log(totals_hash)
}
getTotals([[211,4],[211,5], [204,6], [204,10]])
// 16.5 Insert an element into a binary search tree (in order). Tree contains integers
function binarySearchTree(val){
this.value = val;
this.right = null;
this.left = null;
}
binarySearchTree.prototype.insert = function(val){
if(val == this.value) return; // do not insert
if(val > this.value){ // greater so must be insert to the right
if(this.right == null){
this.right = new binarySearchTree(val);
return;
} else {
this.right.insert(val);
return
}
}
if(val < this.value){ // greater so must be insert to the left
if(this.left == null){
this.left = new binarySearchTree(val);
return;
} else {
this.left.insert(val);
return;
}
}
}
binarySearchTree.prototype.print = function(depth){
if(!depth) depth = 0;
var spaces = "";
for(var i=0;i<depth;i++) spaces += " ";
console.log(spaces + this.value);
if(!(this.left == null)) {
console.log(spaces + "left: ");
this.left.print(depth+1);
}
if(!(this.right == null)){
console.log(spaces + "right: ");
this.right.print(depth+1);
}
}
var bst = new binarySearchTree(20);
bst.insert(20);
bst.insert(30);
bst.insert(10);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(17);
bst.print();
// 16.6 Given a binary search tree which contains integers as values, calculate the sum
binarySearchTree.prototype.sum = function(){
return this.value + (this.left==null?0:this.left.sum()) + (this.right==null?0:this.right.sum());
}
console.log(bst.sum())
// 16.7 Insert a node into a sorted linked list
function linkedList(val){
this.value = val;
this.next = null;
}
linkedList.prototype.insert = function(val){
if(this.next == null) this.next = new linkedList(val);
else this.next.insert(val);
}
linkedList.prototype.insertInOrder = function(val, prevnode){
// when greater than current node
if(val > this.value){
if(this.next == null) {
this.next = new linkedList(val);
return;
}
else this.next.insertInOrder(val,this);
}
// when smaller than current node
if(val < this.value){
if(prevnode === undefined){ // replace existing node
var tmp_next = this.next;
this.next = new linkedList(this.value);
this.next.next = tmp_next;
this.value = val;
} else { // need to add node in between
var new_node = new linkedList(val);
new_node.next = this;
prevnode.next = new_node;
}
}
return;
}
var ll = new linkedList(5);
ll.insertInOrder(8);
ll.insertInOrder(9);
ll.insertInOrder(2);
ll.insertInOrder(3);
console.log(ll);
// 16.8 "Sort" a linked list that contains just 0s and 1s
var ll2 = new linkedList(1);
ll2.insert(1);
ll2.insert(0);
ll2.insert(1);
ll2.insert(0);
ll2.insert(0);
ll2.insert(1);
console.log(ll2)
linkedNode = function(val){
this.value = val;
this.next = null;
}
linkedList2 = function(val){
if(val !== undefined) this.header = new linkedNode(val);
else this.header = null;
}
linkedList2.prototype.insert = function(val){
return this.insertNode(new linkedNode(val));
}
linkedList2.prototype.insertNode = function(newnode){
if(this.header == null) this.header = newnode;
else {
var currentnode = this.header;
while(currentnode.next){
currentnode = currentnode.next;
}
currentnode.next = newnode;
}
return this;
}
linkedList2.prototype.sortBinary = function() {
var ones = new linkedList2(); // to store linkedlist of ones
var currentnode = this.header; // for looping
var prevnode = null;
while(currentnode){
// if 1 then move to other linked list and fix the chain
if(currentnode.value == 1){
var tmpnode = currentnode;
// fix the chain
if(prevnode==null) this.header = currentnode.next; // header
else prevnode.next = currentnode.next; // skipping this node
currentnode = currentnode.next;
tmpnode.next = null;
ones.insertNode(tmpnode); // adding to 1s
} else {// 0 and do nothing
prevnode = currentnode;
currentnode = currentnode.next;
}
}
// need to merge linkedLists
this.insertNode(ones.header);
console.log(this)
}
lll = new linkedList2(3);
lll.insert(4).insert(5).insert(60)
console.log(lll);
var lll2 = new linkedList2(1);
lll2.insert(1);
lll2.insert(0);
lll2.insert(1);
lll2.insert(0);
lll2.insert(0);
lll2.insert(1);
console.log(lll2);
lll2.sortBinary();
// 16.9 Take a stack as input and return new stack which has elements reversed
function Stack(a){
if(a) this.data = a;
else this.data = [];
}
Stack.prototype.push = function(val){
this.data.push(val);
return this;
}
Stack.prototype.pop = function(){
return this.data.pop();
}
Stack.prototype.hasMore = function() {
return this.data.length > 0;
}
var s = new Stack();
s.push(5);
s.push(8);
s.push(9);
console.log(s)
function reverseStack(stack){
var new_stack = new Stack();
while(stack.hasMore()){
new_stack.push(stack.pop());
}
return new_stack;
}
console.log(reverseStack(s))
// 16.10 Removes all even numbers from a stack and return the original
Stack.prototype.removeEven = function(){
var tmp_stack = new Stack();
while(this.hasMore()){
var el = this.pop();
if(el %2 == 0) tmp_stack.push(el);
}
// move all elements back into original stack
while(tmp_stack.hasMore()){
this.push(tmp_stack.pop());
}
return this;
}
ss = new Stack([1,2,3,4,5,6,7,8,9,10]);
console.log(ss.removeEven())
// 16.11 check if two queues are identical. it's okay to destroy them
function Queue(a){
if(a) this.data = a;
else this.data = [];
}
Queue.prototype.push = function(val){
this.data.splice(0,0,val)
return this;
}
Queue.prototype.pop = function(val){
return this.data.pop();
}
Queue.prototype.length = function(){
return this.data.length;
}
Queue.prototype.empty = function(){
return this.data.length === 0;
}
function areQueuesEqual(q1,q2){
while(!q1.empty()){
if(q2.empty()) return false;
if(!(q1.pop() == q2.pop())) return false;
}
return q2.empty();
}
console.log(areQueuesEqual(new Queue([0,1,2,3]), new Queue([0,1,2])))
// 16.12 remove 13th element of queue but keep all else the same
function remove(queue,n){
// loop through initial length of queue and input it back
for(var i=1; i<=queue.length()+1;i++){
if(i!=n) queue.push(queue.pop());
else queue.pop();
}
return q;
}
var q = new Queue([1,2,3,4,5,6,7,8,9]);
console.log(q)
console.log(remove(q,2))
// 16.13 given 2 sorted arrays, write function to merge
function mergeSort(a1,a2){
var merged = [];
for(var i=0, j=0; i<a1.length || j<a2.length;){
// if a1 complete then input a2
if(i>=a1.length){
merged.push(a2[j]);
j++
// if a2 complete then input a1
} else if(j>= a2.length){
merged.push(a1[i]);
i++
// else input the smaller of both
} else {
if(a1[i] == a2[j]){
merged.push(a1[i]);
i++;j++;
}
else if(a1[i]<a2[j]) {
merged.push(a1[i]);
i++;
} else {
merged.push(a2[j]);
j++
}
}
}
return merged;
}
console.log(mergeSort([1,3,5,7,8,11],[2,4,6,10,11,12]));
// 16.14 Insertion sort
function insertionSort(a){
for(var sorthead=0;sorthead<a.length;sorthead++){
// if at the beginning then skip
if(sorthead==0) continue;
// if next value is bigger then skip
else if(a[sorthead] > a[sorthead-1] ) continue;
// else we need to find place and shift
else {
var current_val = a[sorthead];
var cont = true;
for(var j=sorthead;j>=0 && cont;j--){
// prev is greater or zero so insert here
if(j-1 < 0 || current_val>a[j-1]){
a[j] = current_val;
cont=false;
} else { // need to keep flipping
a[j]=a[j-1];
}
}
}
}
return a;
}
console.log(insertionSort([2,5,3,7,4,6,1,9,8]));
// 16.15 Implement binary search. ie: given a sorted array and vale , find location
function binarySearch(a,val,loc){
var mid = Math.floor(a.length/2);
console.log("---")
console.log(a);
console.log("mid = "+mid);
console.log("val = "+val);
console.log("loc = "+loc);
loc = loc || 0;
if(a.length === 0) return -1;
if(a.length ===1) return (a[0] === val?loc+0:-1);
// if value at mid = value, then found
if(a[mid]===val) return loc+mid;
// else split the array in 2 and search in either one
if(val < a[mid]){
return binarySearch(a.splice(0,mid),val,loc);
} else { // bigger
return binarySearch(a.splice(mid+1,a.length-mid),val,loc+mid+1);
}
}
console.log(binarySearch([5,6,7,8,9,10],10));
// 16.16 Find min in a sorted array that was rotated
function findMinBrute(a){
var min_val = null;
var min_val_count = 0;
for(var i=0;i<a.length;i++){
if(min_val == null || a[i]<min_val){
min_val=a[i];
min_val_count++;
}
if(min_val_count==2) return min_val;
}
return min_val;
}
console.log(findMinBrute([2,3,4,5,1]));
function findMinRecursive(a){
console.log(a)
if(a.length===0) return false;
if(a.length===1) return a[0];
if(a.length===2) return (a[0]<a[1]?a[0]:a[1]);
var mid = Math.floor(a.length/2);
if(a[0]<a[mid] && a[mid]<a[a.length-1]) return findMinRecursive(a.splice(0,mid));
if(a[0]>a[mid] && a[mid]<a[a.length-1]) return findMinRecursive(a.splice(0,mid+1));
if(a[0]<a[mid] && a[mid]>a[a.length-1]) return findMinRecursive(a.splice(mid,a.length-mid));
return false;
}
console.log(findMinRecursive([20,22,30,1,5,10,15,16,17,18,19]))
// 16.17 using depth first search, check if tree contains value
function Tree(val){
this.value = val;
this.children = [];
}
Tree.prototype.add = function(val){
return this.addChildNode(new Tree(val));
}
Tree.prototype.addChildNode = function(n){
this.children.push(n);
return this;
}
Tree.prototype.numChildren = function(){
return this.children.length;
}
function depthSearchTree(tree,val){
console.log("depth searching tree for: " + val);
console.log(tree);
if(tree.value === val) return true;
for(var i=0;i<tree.numChildren();i++){
var child = tree.children[i];
if(depthSearchTree(child,val)) return true;
}
return false;
}
var t = new Tree(17);
var t1 = new Tree(18);
t1.add(5).add(6);
var t2 = new Tree(16);
t2.add(22).add(29);
var t3 = new Tree(15);
t3.add(21).add(23);
console.log(t.addChildNode(t1).addChildNode(t2).addChildNode(t3));
console.log(depthSearchTree(t,7));
// 16.18 breadth first search on binary tree
function breadthSearchTree(tree,val){
console.log("breadth searching tree for: " + val);
console.log(tree);
if(tree.value === val) return true;
// search first level
for(var i=0;i<tree.numChildren();i++){
var child = tree.children[i];
if(child.value === val) return true;
}
// send search to next level
for(var j=0;j<tree.numChildren();j++){
var c = tree.children[j];
if(breadthSearchTree(c,val)) return true;
}
return false;
}
console.log(breadthSearchTree(t,5));
// 16.9 find all solutions to a^3+b^3 = c^3+d^3
function findSolutions(){
var solutions = [];
var limit = 100;
var a,b,c,d;
var acubed,bcubed,ccubed,dcubed;
var dcubed_dictionary = {};
var sol_map = {};
var pairs = {};
for(var i=0;i<limit;i++) dcubed_dictionary[i*i*i] = i;
for(a=0;a<limit;a++){
acubed = a*a*a;
for(b=a+1;b<limit;b++){
bcubed = b*b*b;
if(pairs[acubed+bcubed] === undefined) pairs[acubed+bcubed] = [{a:a,b:b}];
else pairs[acubed+bcubed].push({a:a,b:b});
if(pairs[acubed+bcubed].length >= 2) solutions.push(pairs[acubed+bcubed])
/*
for(c=a+1;c<b;c++){
if(c!=a && c!=b) {
ccubed = c*c*c;
dcubed = (acubed + bcubed - ccubed);
if(a==1 && b==12 && c==9) console.log(acubed + bcubed - ccubed)
// if d is integer then it is a solution
if(dcubed_dictionary[dcubed] && dcubed_dictionary[dcubed]>c && !(sol_map[a+b]) && !(sol_map[c+dcubed_dictionary[dcubed]])){
sol_map[a+b] = true;
sol_map[c+dcubed_dictionary[dcubed]] = true;
solutions.push(a+"^3+"+b+"^3="+c+"^3+"+dcubed_dictionary[dcubed]+"^3");
}
}
}*/
}
}
console.log(pairs); // all pairs where length > 2 are solutions ==> O(n^2)
console.log(dcubed_dictionary);
console.log(solutions)
}
findSolutions();
// noprotect
// 16.20 given string print all permutations (no duplicate characters)
function printPermuations(string){
// O(2^n)
if(string.length==1) return [string];
var list = [];
for(var i=0;i<string.length;i++){
var pivot = string[i];
console.log("pivot: "+ pivot)
var str = string.slice(0, i) + string.slice(i+1);
console.log("string: " + str)
// keep one character and permutate the remaining
var perms = printPermuations(str);
for(var j=0;j<perms.length;j++){
list.push(pivot + perms[j]);
}
}
return list;
}
console.log(printPermuations("abcd"));
// 16.21 given knows(a,b) returns if a and b know each other
// celebrity, everyone knows them but they know no one else
// findCelebrity()
function knows(a,b){
var hash = {
"ab": true,
"cb": true,
"db": true,
"ac": true,
"ca": true
}
return !(!hash[a+b]);
}
function findCelebrity(population){
var knowledge_hash = {};
knowledge_hash.knows = {};
knowledge_hash.isknown = {};
// build knowledge hash
for(var i=0;i<population.length;i++){
var a = population[i];
for(var j=0;j<population.length;j++){
if(i!=j){
var b = population[j];
if(knows(a,b)){
if(!knowledge_hash.knows[a])knowledge_hash.knows[a]=1;
else knowledge_hash.knows[a] += 1;
if(!knowledge_hash.isknown[b])knowledge_hash.isknown[b]=1;
else knowledge_hash.isknown[b] += 1;
}
}
}
}
// search knowledge has
for(var k=0;k<population.length;k++){
if(knowledge_hash.isknown[population[k]] == population.length-1
&& !(knowledge_hash.knows[population[k]])) return population[k];
}
console.log(knowledge_hash);
return false;
}
// 16.22 given NxN matrix of characters and list of valid words
// Print all valid words found by traversing the matrix, cannot re-use letters in same word
function findValidWords(matrix, valid_words) {
var valid_words_in_matrix = [];
var matrix_size = matrix.length; // assuming N*N
var hashes = (function() {
var hashes = {
words: {},
characters: {}
}
// create hashes for word and character
for (var ii = 0; ii < valid_words.length; ii++) {
var word = valid_words[ii];
hashes.words[word] = true;
for (var jj = 0; jj < word.length; jj++) {
var character = word[jj];
hashes.characters[jj] = hashes.characters[jj] || {};
hashes.characters[jj][character] = true;
}
}
return hashes;
})();
// creating helper functions
function canBeinPosition(letter, position) {
hashes.characters[position] = hashes.characters[position] || {};
return hashes.characters[position][letter] || false;
}
function isValidWord(word) {
return hashes.words[word]
}
function findWords(prefix, visited, row, col,dir) {
console.log("----FIND WORDS----")
console.log(dir)
console.log("prefx: " + prefix);
console.log(copyObj(visited));
console.log("matrix("+row+","+col+")="+matrix[row][col]);
var current_letter = matrix[row][col];
var new_word = prefix + current_letter;
console.log("new word: " + new_word)
if (visited[row + "" + col]) {
console.log("VISITED - STOP")
return false;
}
else visited[row + "" + col] = true;
// check if current letter can be the nth position in a valid word
if (!canBeinPosition(current_letter, new_word.length - 1)) {
console.log("NO POSSIBLE WORDS - STOP")
return false;
}
// check if prefix is a word
if (isValidWord(new_word)) {
console.log("WORD FOUND:" + new_word)
valid_words_in_matrix.push(new_word);
}
// do a check on all other directions recursively
// right
if (col + 1 < matrix_size) findWords(new_word, copyObj(visited), row, col + 1,"right");
else console.log(new_word + ": CANT GO RIGHT");
// down
if (row + 1 < matrix_size) findWords(new_word, copyObj(visited), row + 1, col,"down");
else console.log(new_word + ": CANT GO DOWN");
// left
if (col - 1 >= 0) findWords(new_word, copyObj(visited), row, col - 1,"left");
else console.log(new_word + ": CANT GO LEFT");
// up
if (row - 1 >= 0) findWords(new_word, copyObj(visited), row - 1, col,"up");
else console.log(new_word + ": CANT GO UP");
}
// loop through the matrix
for (var i = 0; i < matrix_size; i++) {
for (var j = 0; j < matrix_size; j++) {
findWords("", {}, i, j,"start"); // base case
}
}
return valid_words_in_matrix;
}
function copyObj(obj) {
return JSON.parse(JSON.stringify(obj));
}
console.log(findValidWords([
["B", "I", "N"],
["A", "O", "G"],
["T", "A", "R"]
], ["BINGO", "BAT", "GOAT", "RAT","LAX"]))
// noprotect
// 16.23. given array of +/- integers find the contiguous sequence with laargest sum.
function findMaxContiguous(a){
var max;
for(var i=0;i<a.length;i++){
var m = findMaxSum(a.slice(i));
if(i===0 || m > max) max = m
}
return max;
}
function findMaxSum(a){
var running_count = 0;
var max = 0;
for(var i=0;i<a.length;i++){
running_count += a[i];
if(running_count > max) max = running_count;
}
return max;
}
console.log(findMaxContiguous([2,-8,3,-2,4,-10]))
</script>
<script id="jsbin-source-javascript" type="text/javascript">
// 16.1 Given a sorted array of positive integers with an empty spot at the end, insert an element in sorted order
function insertEl(a,n){
console.log(a);
var found = false;
var next_val;
for(var i=0; i<a.length;i++){
// end of the array
if(a.length==(i+1)){ // at the last spot
if(!found) a[i] = n;
else a[i] = next_val;
}
// place it at i and move all other elements
else {
if(!found) {
if(n<a[i]) {
found = true;
next_val = a[i];
a[i] = n;
}
} else {
var tmp_val = next_val;
next_val = a[i];
a[i] = tmp_val;
}
}
}
console.log(a)
}
insertEl([1, 3, 5, 10, 15, 20, 22, 24, ""],25);
// 16.2 Rever the order of elements in an array without creating a new array
function reverseArray(a){
console.log(a);
for(var i=0; i < a.length/2; i++){
var j = a.length - 1 - i;
var tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
console.log(a);
}
reverseArray([1,2,3,4,5]);
// 163. Given two lists (A and B) of unique strings, determine if A is a subset of B
function isSubset(a,b){
// transform b into a hash
var b_hash = {};
for(var i=0; i<b.length;i++){
b_hash[b[i]] = true;
}
// loop through a to see if a is in b_has
for(var j=0;j<a.length;j++){
if(!b_hash[a[j]]) return false;
}
return true;
}
console.log(isSubset([1,5],[1,2,3,4]));
console.log(isSubset([1,4],[1,2,3,4]));
// 16.4 given a two dimensional array of sales data where first column is prod ID and second column
//.. is quantity. Return a new 2 D array with Totals for each product ID
function getTotals(a){
var totals_hash = {};
for(var i=0;i<a.length;i++){
// check if does not exist, else create
if(totals_hash[a[i][0]] === undefined) totals_hash[a[i][0]] = 0;
// add to the hash
totals_hash[a[i][0]] += a[i][1];
}
// transform hash into array
console.log(totals_hash)
}
getTotals([[211,4],[211,5], [204,6], [204,10]])
// 16.5 Insert an element into a binary search tree (in order). Tree contains integers
function binarySearchTree(val){
this.value = val;
this.right = null;
this.left = null;
}
binarySearchTree.prototype.insert = function(val){
if(val == this.value) return; // do not insert
if(val > this.value){ // greater so must be insert to the right
if(this.right == null){
this.right = new binarySearchTree(val);
return;
} else {
this.right.insert(val);
return
}
}
if(val < this.value){ // greater so must be insert to the left
if(this.left == null){
this.left = new binarySearchTree(val);
return;
} else {
this.left.insert(val);
return;
}
}
}
binarySearchTree.prototype.print = function(depth){
if(!depth) depth = 0;
var spaces = "";
for(var i=0;i<depth;i++) spaces += " ";
console.log(spaces + this.value);
if(!(this.left == null)) {
console.log(spaces + "left: ");
this.left.print(depth+1);
}
if(!(this.right == null)){
console.log(spaces + "right: ");
this.right.print(depth+1);
}
}
var bst = new binarySearchTree(20);
bst.insert(20);
bst.insert(30);
bst.insert(10);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(17);
bst.print();
// 16.6 Given a binary search tree which contains integers as values, calculate the sum
binarySearchTree.prototype.sum = function(){
return this.value + (this.left==null?0:this.left.sum()) + (this.right==null?0:this.right.sum());
}
console.log(bst.sum())
// 16.7 Insert a node into a sorted linked list
function linkedList(val){
this.value = val;
this.next = null;
}
linkedList.prototype.insert = function(val){
if(this.next == null) this.next = new linkedList(val);
else this.next.insert(val);
}
linkedList.prototype.insertInOrder = function(val, prevnode){
// when greater than current node
if(val > this.value){
if(this.next == null) {
this.next = new linkedList(val);
return;
}
else this.next.insertInOrder(val,this);
}
// when smaller than current node
if(val < this.value){
if(prevnode === undefined){ // replace existing node
var tmp_next = this.next;
this.next = new linkedList(this.value);
this.next.next = tmp_next;
this.value = val;
} else { // need to add node in between
var new_node = new linkedList(val);
new_node.next = this;
prevnode.next = new_node;
}
}
return;
}
var ll = new linkedList(5);
ll.insertInOrder(8);
ll.insertInOrder(9);
ll.insertInOrder(2);
ll.insertInOrder(3);
console.log(ll);
// 16.8 "Sort" a linked list that contains just 0s and 1s
var ll2 = new linkedList(1);
ll2.insert(1);
ll2.insert(0);
ll2.insert(1);
ll2.insert(0);
ll2.insert(0);
ll2.insert(1);
console.log(ll2)
linkedNode = function(val){
this.value = val;
this.next = null;
}
linkedList2 = function(val){
if(val !== undefined) this.header = new linkedNode(val);
else this.header = null;
}
linkedList2.prototype.insert = function(val){
return this.insertNode(new linkedNode(val));
}
linkedList2.prototype.insertNode = function(newnode){
if(this.header == null) this.header = newnode;
else {
var currentnode = this.header;
while(currentnode.next){
currentnode = currentnode.next;
}
currentnode.next = newnode;
}
return this;
}
linkedList2.prototype.sortBinary = function() {
var ones = new linkedList2(); // to store linkedlist of ones
var currentnode = this.header; // for looping
var prevnode = null;
while(currentnode){
// if 1 then move to other linked list and fix the chain
if(currentnode.value == 1){
var tmpnode = currentnode;
// fix the chain
if(prevnode==null) this.header = currentnode.next; // header
else prevnode.next = currentnode.next; // skipping this node
currentnode = currentnode.next;
tmpnode.next = null;
ones.insertNode(tmpnode); // adding to 1s
} else {// 0 and do nothing
prevnode = currentnode;
currentnode = currentnode.next;
}
}
// need to merge linkedLists
this.insertNode(ones.header);
console.log(this)
}
lll = new linkedList2(3);
lll.insert(4).insert(5).insert(60)
console.log(lll);
var lll2 = new linkedList2(1);
lll2.insert(1);
lll2.insert(0);
lll2.insert(1);
lll2.insert(0);
lll2.insert(0);
lll2.insert(1);
console.log(lll2);
lll2.sortBinary();
// 16.9 Take a stack as input and return new stack which has elements reversed
function Stack(a){
if(a) this.data = a;
else this.data = [];
}
Stack.prototype.push = function(val){
this.data.push(val);
return this;
}
Stack.prototype.pop = function(){
return this.data.pop();
}
Stack.prototype.hasMore = function() {
return this.data.length > 0;
}
var s = new Stack();
s.push(5);
s.push(8);
s.push(9);
console.log(s)
function reverseStack(stack){
var new_stack = new Stack();
while(stack.hasMore()){
new_stack.push(stack.pop());
}
return new_stack;
}
console.log(reverseStack(s))
// 16.10 Removes all even numbers from a stack and return the original
Stack.prototype.removeEven = function(){
var tmp_stack = new Stack();
while(this.hasMore()){
var el = this.pop();
if(el %2 == 0) tmp_stack.push(el);
}
// move all elements back into original stack
while(tmp_stack.hasMore()){
this.push(tmp_stack.pop());
}
return this;
}
ss = new Stack([1,2,3,4,5,6,7,8,9,10]);
console.log(ss.removeEven())
// 16.11 check if two queues are identical. it's okay to destroy them
function Queue(a){
if(a) this.data = a;
else this.data = [];
}
Queue.prototype.push = function(val){
this.data.splice(0,0,val)
return this;
}
Queue.prototype.pop = function(val){
return this.data.pop();
}
Queue.prototype.length = function(){
return this.data.length;
}
Queue.prototype.empty = function(){
return this.data.length === 0;
}
function areQueuesEqual(q1,q2){
while(!q1.empty()){
if(q2.empty()) return false;
if(!(q1.pop() == q2.pop())) return false;
}
return q2.empty();
}
console.log(areQueuesEqual(new Queue([0,1,2,3]), new Queue([0,1,2])))
// 16.12 remove 13th element of queue but keep all else the same
function remove(queue,n){
// loop through initial length of queue and input it back
for(var i=1; i<=queue.length()+1;i++){
if(i!=n) queue.push(queue.pop());
else queue.pop();
}
return q;
}
var q = new Queue([1,2,3,4,5,6,7,8,9]);
console.log(q)
console.log(remove(q,2))
// 16.13 given 2 sorted arrays, write function to merge
function mergeSort(a1,a2){
var merged = [];
for(var i=0, j=0; i<a1.length || j<a2.length;){
// if a1 complete then input a2
if(i>=a1.length){
merged.push(a2[j]);
j++
// if a2 complete then input a1
} else if(j>= a2.length){
merged.push(a1[i]);
i++
// else input the smaller of both
} else {
if(a1[i] == a2[j]){
merged.push(a1[i]);
i++;j++;
}
else if(a1[i]<a2[j]) {
merged.push(a1[i]);
i++;
} else {
merged.push(a2[j]);
j++
}
}
}
return merged;
}
console.log(mergeSort([1,3,5,7,8,11],[2,4,6,10,11,12]));
// 16.14 Insertion sort
function insertionSort(a){
for(var sorthead=0;sorthead<a.length;sorthead++){
// if at the beginning then skip
if(sorthead==0) continue;
// if next value is bigger then skip
else if(a[sorthead] > a[sorthead-1] ) continue;
// else we need to find place and shift
else {
var current_val = a[sorthead];
var cont = true;
for(var j=sorthead;j>=0 && cont;j--){
// prev is greater or zero so insert here
if(j-1 < 0 || current_val>a[j-1]){
a[j] = current_val;
cont=false;
} else { // need to keep flipping
a[j]=a[j-1];
}
}
}
}
return a;
}
console.log(insertionSort([2,5,3,7,4,6,1,9,8]));
// 16.15 Implement binary search. ie: given a sorted array and vale , find location
function binarySearch(a,val,loc){
var mid = Math.floor(a.length/2);
console.log("---")
console.log(a);
console.log("mid = "+mid);
console.log("val = "+val);
console.log("loc = "+loc);
loc = loc || 0;
if(a.length === 0) return -1;
if(a.length ===1) return (a[0] === val?loc+0:-1);
// if value at mid = value, then found
if(a[mid]===val) return loc+mid;
// else split the array in 2 and search in either one
if(val < a[mid]){
return binarySearch(a.splice(0,mid),val,loc);
} else { // bigger
return binarySearch(a.splice(mid+1,a.length-mid),val,loc+mid+1);
}
}
console.log(binarySearch([5,6,7,8,9,10],10));
// 16.16 Find min in a sorted array that was rotated
function findMinBrute(a){
var min_val = null;
var min_val_count = 0;
for(var i=0;i<a.length;i++){
if(min_val == null || a[i]<min_val){
min_val=a[i];
min_val_count++;
}
if(min_val_count==2) return min_val;
}
return min_val;
}
console.log(findMinBrute([2,3,4,5,1]));
function findMinRecursive(a){
console.log(a)
if(a.length===0) return false;
if(a.length===1) return a[0];
if(a.length===2) return (a[0]<a[1]?a[0]:a[1]);
var mid = Math.floor(a.length/2);
if(a[0]<a[mid] && a[mid]<a[a.length-1]) return findMinRecursive(a.splice(0,mid));
if(a[0]>a[mid] && a[mid]<a[a.length-1]) return findMinRecursive(a.splice(0,mid+1));
if(a[0]<a[mid] && a[mid]>a[a.length-1]) return findMinRecursive(a.splice(mid,a.length-mid));
return false;
}
console.log(findMinRecursive([20,22,30,1,5,10,15,16,17,18,19]))
// 16.17 using depth first search, check if tree contains value
function Tree(val){
this.value = val;
this.children = [];
}
Tree.prototype.add = function(val){
return this.addChildNode(new Tree(val));
}
Tree.prototype.addChildNode = function(n){
this.children.push(n);
return this;
}
Tree.prototype.numChildren = function(){
return this.children.length;
}
function depthSearchTree(tree,val){
console.log("depth searching tree for: " + val);
console.log(tree);
if(tree.value === val) return true;
for(var i=0;i<tree.numChildren();i++){
var child = tree.children[i];
if(depthSearchTree(child,val)) return true;
}
return false;
}
var t = new Tree(17);
var t1 = new Tree(18);
t1.add(5).add(6);
var t2 = new Tree(16);
t2.add(22).add(29);
var t3 = new Tree(15);
t3.add(21).add(23);
console.log(t.addChildNode(t1).addChildNode(t2).addChildNode(t3));
console.log(depthSearchTree(t,7));
// 16.18 breadth first search on binary tree
function breadthSearchTree(tree,val){
console.log("breadth searching tree for: " + val);
console.log(tree);
if(tree.value === val) return true;
// search first level
for(var i=0;i<tree.numChildren();i++){
var child = tree.children[i];
if(child.value === val) return true;
}
// send search to next level
for(var j=0;j<tree.numChildren();j++){
var c = tree.children[j];
if(breadthSearchTree(c,val)) return true;
}
return false;
}
console.log(breadthSearchTree(t,5));
// 16.9 find all solutions to a^3+b^3 = c^3+d^3
function findSolutions(){
var solutions = [];
var limit = 100;
var a,b,c,d;
var acubed,bcubed,ccubed,dcubed;
var dcubed_dictionary = {};
var sol_map = {};
var pairs = {};
for(var i=0;i<limit;i++) dcubed_dictionary[i*i*i] = i;
for(a=0;a<limit;a++){
acubed = a*a*a;
for(b=a+1;b<limit;b++){
bcubed = b*b*b;
if(pairs[acubed+bcubed] === undefined) pairs[acubed+bcubed] = [{a:a,b:b}];
else pairs[acubed+bcubed].push({a:a,b:b});
if(pairs[acubed+bcubed].length >= 2) solutions.push(pairs[acubed+bcubed])
/*
for(c=a+1;c<b;c++){
if(c!=a && c!=b) {
ccubed = c*c*c;
dcubed = (acubed + bcubed - ccubed);
if(a==1 && b==12 && c==9) console.log(acubed + bcubed - ccubed)
// if d is integer then it is a solution
if(dcubed_dictionary[dcubed] && dcubed_dictionary[dcubed]>c && !(sol_map[a+b]) && !(sol_map[c+dcubed_dictionary[dcubed]])){
sol_map[a+b] = true;
sol_map[c+dcubed_dictionary[dcubed]] = true;
solutions.push(a+"^3+"+b+"^3="+c+"^3+"+dcubed_dictionary[dcubed]+"^3");
}
}
}*/
}
}
console.log(pairs); // all pairs where length > 2 are solutions ==> O(n^2)
console.log(dcubed_dictionary);
console.log(solutions)
}
findSolutions();
// noprotect
// 16.20 given string print all permutations (no duplicate characters)
function printPermuations(string){
// O(2^n)
if(string.length==1) return [string];
var list = [];
for(var i=0;i<string.length;i++){
var pivot = string[i];
console.log("pivot: "+ pivot)
var str = string.slice(0, i) + string.slice(i+1);
console.log("string: " + str)
// keep one character and permutate the remaining
var perms = printPermuations(str);
for(var j=0;j<perms.length;j++){
list.push(pivot + perms[j]);
}
}
return list;
}
console.log(printPermuations("abcd"));
// 16.21 given knows(a,b) returns if a and b know each other
// celebrity, everyone knows them but they know no one else
// findCelebrity()
function knows(a,b){
var hash = {
"ab": true,
"cb": true,
"db": true,
"ac": true,
"ca": true
}
return !(!hash[a+b]);
}
function findCelebrity(population){
var knowledge_hash = {};
knowledge_hash.knows = {};
knowledge_hash.isknown = {};
// build knowledge hash
for(var i=0;i<population.length;i++){
var a = population[i];
for(var j=0;j<population.length;j++){
if(i!=j){
var b = population[j];
if(knows(a,b)){
if(!knowledge_hash.knows[a])knowledge_hash.knows[a]=1;
else knowledge_hash.knows[a] += 1;
if(!knowledge_hash.isknown[b])knowledge_hash.isknown[b]=1;
else knowledge_hash.isknown[b] += 1;
}
}
}
}
// search knowledge has
for(var k=0;k<population.length;k++){
if(knowledge_hash.isknown[population[k]] == population.length-1
&& !(knowledge_hash.knows[population[k]])) return population[k];
}
console.log(knowledge_hash);
return false;
}
// 16.22 given NxN matrix of characters and list of valid words
// Print all valid words found by traversing the matrix, cannot re-use letters in same word
function findValidWords(matrix, valid_words) {
var valid_words_in_matrix = [];
var matrix_size = matrix.length; // assuming N*N
var hashes = (function() {
var hashes = {
words: {},
characters: {}
}
// create hashes for word and character
for (var ii = 0; ii < valid_words.length; ii++) {
var word = valid_words[ii];
hashes.words[word] = true;
for (var jj = 0; jj < word.length; jj++) {
var character = word[jj];
hashes.characters[jj] = hashes.characters[jj] || {};
hashes.characters[jj][character] = true;
}
}
return hashes;
})();
// creating helper functions
function canBeinPosition(letter, position) {
hashes.characters[position] = hashes.characters[position] || {};
return hashes.characters[position][letter] || false;
}
function isValidWord(word) {
return hashes.words[word]
}
function findWords(prefix, visited, row, col,dir) {
console.log("----FIND WORDS----")
console.log(dir)
console.log("prefx: " + prefix);
console.log(copyObj(visited));
console.log("matrix("+row+","+col+")="+matrix[row][col]);
var current_letter = matrix[row][col];
var new_word = prefix + current_letter;
console.log("new word: " + new_word)
if (visited[row + "" + col]) {
console.log("VISITED - STOP")
return false;
}
else visited[row + "" + col] = true;
// check if current letter can be the nth position in a valid word
if (!canBeinPosition(current_letter, new_word.length - 1)) {
console.log("NO POSSIBLE WORDS - STOP")
return false;
}
// check if prefix is a word
if (isValidWord(new_word)) {
console.log("WORD FOUND:" + new_word)
valid_words_in_matrix.push(new_word);
}
// do a check on all other directions recursively
// right
if (col + 1 < matrix_size) findWords(new_word, copyObj(visited), row, col + 1,"right");
else console.log(new_word + ": CANT GO RIGHT");
// down
if (row + 1 < matrix_size) findWords(new_word, copyObj(visited), row + 1, col,"down");
else console.log(new_word + ": CANT GO DOWN");
// left
if (col - 1 >= 0) findWords(new_word, copyObj(visited), row, col - 1,"left");
else console.log(new_word + ": CANT GO LEFT");
// up
if (row - 1 >= 0) findWords(new_word, copyObj(visited), row - 1, col,"up");
else console.log(new_word + ": CANT GO UP");
}
// loop through the matrix
for (var i = 0; i < matrix_size; i++) {
for (var j = 0; j < matrix_size; j++) {
findWords("", {}, i, j,"start"); // base case
}
}
return valid_words_in_matrix;
}
function copyObj(obj) {
return JSON.parse(JSON.stringify(obj));
}
console.log(findValidWords([
["B", "I", "N"],
["A", "O", "G"],
["T", "A", "R"]
], ["BINGO", "BAT", "GOAT", "RAT","LAX"]))
// noprotect
// 16.23. given array of +/- integers find the contiguous sequence with laargest sum.
function findMaxContiguous(a){
var max;
for(var i=0;i<a.length;i++){
var m = findMaxSum(a.slice(i));
if(i===0 || m > max) max = m
}
return max;
}
function findMaxSum(a){
var running_count = 0;
var max = 0;
for(var i=0;i<a.length;i++){
running_count += a[i];
if(running_count > max) max = running_count;
}
return max;
}
console.log(findMaxContiguous([2,-8,3,-2,4,-10]))
</script></body>
</html>
Raw
jsbin.domixaq.js
// 16.1 Given a sorted array of positive integers with an empty spot at the end, insert an element in sorted order
function insertEl(a,n){
console.log(a);
var found = false;
var next_val;
for(var i=0; i<a.length;i++){
// end of the array
if(a.length==(i+1)){ // at the last spot
if(!found) a[i] = n;
else a[i] = next_val;
}
// place it at i and move all other elements
else {
if(!found) {
if(n<a[i]) {
found = true;
next_val = a[i];
a[i] = n;
}
} else {
var tmp_val = next_val;
next_val = a[i];
a[i] = tmp_val;
}
}
}
console.log(a)
}
insertEl([1, 3, 5, 10, 15, 20, 22, 24, ""],25);
// 16.2 Rever the order of elements in an array without creating a new array
function reverseArray(a){
console.log(a);
for(var i=0; i < a.length/2; i++){
var j = a.length - 1 - i;
var tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
console.log(a);
}
reverseArray([1,2,3,4,5]);
// 163. Given two lists (A and B) of unique strings, determine if A is a subset of B
function isSubset(a,b){
// transform b into a hash
var b_hash = {};
for(var i=0; i<b.length;i++){
b_hash[b[i]] = true;
}
// loop through a to see if a is in b_has
for(var j=0;j<a.length;j++){
if(!b_hash[a[j]]) return false;
}
return true;
}
console.log(isSubset([1,5],[1,2,3,4]));
console.log(isSubset([1,4],[1,2,3,4]));
// 16.4 given a two dimensional array of sales data where first column is prod ID and second column
//.. is quantity. Return a new 2 D array with Totals for each product ID
function getTotals(a){
var totals_hash = {};
for(var i=0;i<a.length;i++){
// check if does not exist, else create
if(totals_hash[a[i][0]] === undefined) totals_hash[a[i][0]] = 0;
// add to the hash
totals_hash[a[i][0]] += a[i][1];
}
// transform hash into array
console.log(totals_hash)
}
getTotals([[211,4],[211,5], [204,6], [204,10]])
// 16.5 Insert an element into a binary search tree (in order). Tree contains integers
function binarySearchTree(val){
this.value = val;
this.right = null;
this.left = null;
}
binarySearchTree.prototype.insert = function(val){
if(val == this.value) return; // do not insert
if(val > this.value){ // greater so must be insert to the right
if(this.right == null){
this.right = new binarySearchTree(val);
return;
} else {
this.right.insert(val);
return
}
}
if(val < this.value){ // greater so must be insert to the left
if(this.left == null){
this.left = new binarySearchTree(val);
return;
} else {
this.left.insert(val);
return;
}
}
}
binarySearchTree.prototype.print = function(depth){
if(!depth) depth = 0;
var spaces = "";
for(var i=0;i<depth;i++) spaces += " ";
console.log(spaces + this.value);
if(!(this.left == null)) {
console.log(spaces + "left: ");
this.left.print(depth+1);
}
if(!(this.right == null)){
console.log(spaces + "right: ");
this.right.print(depth+1);
}
}
var bst = new binarySearchTree(20);
bst.insert(20);
bst.insert(30);
bst.insert(10);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(17);
bst.print();
// 16.6 Given a binary search tree which contains integers as values, calculate the sum
binarySearchTree.prototype.sum = function(){
return this.value + (this.left==null?0:this.left.sum()) + (this.right==null?0:this.right.sum());
}
console.log(bst.sum())
// 16.7 Insert a node into a sorted linked list
function linkedList(val){
this.value = val;
this.next = null;
}
linkedList.prototype.insert = function(val){
if(this.next == null) this.next = new linkedList(val);
else this.next.insert(val);
}
linkedList.prototype.insertInOrder = function(val, prevnode){
// when greater than current node
if(val > this.value){
if(this.next == null) {
this.next = new linkedList(val);
return;
}
else this.next.insertInOrder(val,this);
}
// when smaller than current node
if(val < this.value){
if(prevnode === undefined){ // replace existing node
var tmp_next = this.next;
this.next = new linkedList(this.value);
this.next.next = tmp_next;
this.value = val;
} else { // need to add node in between
var new_node = new linkedList(val);
new_node.next = this;
prevnode.next = new_node;
}
}
return;
}
var ll = new linkedList(5);
ll.insertInOrder(8);
ll.insertInOrder(9);
ll.insertInOrder(2);
ll.insertInOrder(3);
console.log(ll);
// 16.8 "Sort" a linked list that contains just 0s and 1s
var ll2 = new linkedList(1);
ll2.insert(1);
ll2.insert(0);
ll2.insert(1);
ll2.insert(0);
ll2.insert(0);
ll2.insert(1);
console.log(ll2)
linkedNode = function(val){
this.value = val;
this.next = null;
}
linkedList2 = function(val){
if(val !== undefined) this.header = new linkedNode(val);
else this.header = null;
}
linkedList2.prototype.insert = function(val){
return this.insertNode(new linkedNode(val));
}
linkedList2.prototype.insertNode = function(newnode){
if(this.header == null) this.header = newnode;
else {
var currentnode = this.header;
while(currentnode.next){
currentnode = currentnode.next;
}
currentnode.next = newnode;
}
return this;
}
linkedList2.prototype.sortBinary = function() {
var ones = new linkedList2(); // to store linkedlist of ones
var currentnode = this.header; // for looping
var prevnode = null;
while(currentnode){
// if 1 then move to other linked list and fix the chain
if(currentnode.value == 1){
var tmpnode = currentnode;
// fix the chain
if(prevnode==null) this.header = currentnode.next; // header
else prevnode.next = currentnode.next; // skipping this node
currentnode = currentnode.next;
tmpnode.next = null;
ones.insertNode(tmpnode); // adding to 1s
} else {// 0 and do nothing
prevnode = currentnode;
currentnode = currentnode.next;
}
}
// need to merge linkedLists
this.insertNode(ones.header);
console.log(this)
}
lll = new linkedList2(3);
lll.insert(4).insert(5).insert(60)
console.log(lll);
var lll2 = new linkedList2(1);
lll2.insert(1);
lll2.insert(0);
lll2.insert(1);
lll2.insert(0);
lll2.insert(0);
lll2.insert(1);
console.log(lll2);
lll2.sortBinary();
// 16.9 Take a stack as input and return new stack which has elements reversed
function Stack(a){
if(a) this.data = a;
else this.data = [];
}
Stack.prototype.push = function(val){
this.data.push(val);
return this;
}
Stack.prototype.pop = function(){
return this.data.pop();
}
Stack.prototype.hasMore = function() {
return this.data.length > 0;
}
var s = new Stack();
s.push(5);
s.push(8);
s.push(9);
console.log(s)
function reverseStack(stack){
var new_stack = new Stack();
while(stack.hasMore()){
new_stack.push(stack.pop());
}
return new_stack;
}
console.log(reverseStack(s))
// 16.10 Removes all even numbers from a stack and return the original
Stack.prototype.removeEven = function(){
var tmp_stack = new Stack();
while(this.hasMore()){
var el = this.pop();
if(el %2 == 0) tmp_stack.push(el);
}
// move all elements back into original stack
while(tmp_stack.hasMore()){
this.push(tmp_stack.pop());
}
return this;
}
ss = new Stack([1,2,3,4,5,6,7,8,9,10]);
console.log(ss.removeEven())
// 16.11 check if two queues are identical. it's okay to destroy them
function Queue(a){
if(a) this.data = a;
else this.data = [];
}
Queue.prototype.push = function(val){
this.data.splice(0,0,val)
return this;
}
Queue.prototype.pop = function(val){
return this.data.pop();
}
Queue.prototype.length = function(){
return this.data.length;
}
Queue.prototype.empty = function(){
return this.data.length === 0;
}
function areQueuesEqual(q1,q2){
while(!q1.empty()){
if(q2.empty()) return false;
if(!(q1.pop() == q2.pop())) return false;
}
return q2.empty();
}
console.log(areQueuesEqual(new Queue([0,1,2,3]), new Queue([0,1,2])))
// 16.12 remove 13th element of queue but keep all else the same
function remove(queue,n){
// loop through initial length of queue and input it back
for(var i=1; i<=queue.length()+1;i++){
if(i!=n) queue.push(queue.pop());
else queue.pop();
}
return q;
}
var q = new Queue([1,2,3,4,5,6,7,8,9]);
console.log(q)
console.log(remove(q,2))
// 16.13 given 2 sorted arrays, write function to merge
function mergeSort(a1,a2){
var merged = [];
for(var i=0, j=0; i<a1.length || j<a2.length;){
// if a1 complete then input a2
if(i>=a1.length){
merged.push(a2[j]);
j++
// if a2 complete then input a1
} else if(j>= a2.length){
merged.push(a1[i]);
i++
// else input the smaller of both
} else {
if(a1[i] == a2[j]){
merged.push(a1[i]);
i++;j++;
}
else if(a1[i]<a2[j]) {
merged.push(a1[i]);
i++;
} else {
merged.push(a2[j]);
j++
}
}
}
return merged;
}
console.log(mergeSort([1,3,5,7,8,11],[2,4,6,10,11,12]));
// 16.14 Insertion sort
function insertionSort(a){
for(var sorthead=0;sorthead<a.length;sorthead++){
// if at the beginning then skip
if(sorthead==0) continue;
// if next value is bigger then skip
else if(a[sorthead] > a[sorthead-1] ) continue;
// else we need to find place and shift
else {
var current_val = a[sorthead];
var cont = true;
for(var j=sorthead;j>=0 && cont;j--){
// prev is greater or zero so insert here
if(j-1 < 0 || current_val>a[j-1]){
a[j] = current_val;
cont=false;
} else { // need to keep flipping
a[j]=a[j-1];
}
}
}
}
return a;
}
console.log(insertionSort([2,5,3,7,4,6,1,9,8]));
// 16.15 Implement binary search. ie: given a sorted array and vale , find location
function binarySearch(a,val,loc){
var mid = Math.floor(a.length/2);
console.log("---")
console.log(a);
console.log("mid = "+mid);
console.log("val = "+val);
console.log("loc = "+loc);
loc = loc || 0;
if(a.length === 0) return -1;
if(a.length ===1) return (a[0] === val?loc+0:-1);
// if value at mid = value, then found
if(a[mid]===val) return loc+mid;
// else split the array in 2 and search in either one
if(val < a[mid]){
return binarySearch(a.splice(0,mid),val,loc);
} else { // bigger
return binarySearch(a.splice(mid+1,a.length-mid),val,loc+mid+1);
}
}
console.log(binarySearch([5,6,7,8,9,10],10));
// 16.16 Find min in a sorted array that was rotated
function findMinBrute(a){
var min_val = null;
var min_val_count = 0;
for(var i=0;i<a.length;i++){
if(min_val == null || a[i]<min_val){
min_val=a[i];
min_val_count++;
}
if(min_val_count==2) return min_val;
}
return min_val;
}
console.log(findMinBrute([2,3,4,5,1]));
function findMinRecursive(a){
console.log(a)
if(a.length===0) return false;
if(a.length===1) return a[0];
if(a.length===2) return (a[0]<a[1]?a[0]:a[1]);
var mid = Math.floor(a.length/2);
if(a[0]<a[mid] && a[mid]<a[a.length-1]) return findMinRecursive(a.splice(0,mid));
if(a[0]>a[mid] && a[mid]<a[a.length-1]) return findMinRecursive(a.splice(0,mid+1));
if(a[0]<a[mid] && a[mid]>a[a.length-1]) return findMinRecursive(a.splice(mid,a.length-mid));
return false;
}
console.log(findMinRecursive([20,22,30,1,5,10,15,16,17,18,19]))
// 16.17 using depth first search, check if tree contains value
function Tree(val){
this.value = val;
this.children = [];
}
Tree.prototype.add = function(val){
return this.addChildNode(new Tree(val));
}
Tree.prototype.addChildNode = function(n){
this.children.push(n);
return this;
}
Tree.prototype.numChildren = function(){
return this.children.length;
}
function depthSearchTree(tree,val){
console.log("depth searching tree for: " + val);
console.log(tree);
if(tree.value === val) return true;
for(var i=0;i<tree.numChildren();i++){
var child = tree.children[i];
if(depthSearchTree(child,val)) return true;
}
return false;
}
var t = new Tree(17);
var t1 = new Tree(18);
t1.add(5).add(6);
var t2 = new Tree(16);
t2.add(22).add(29);
var t3 = new Tree(15);
t3.add(21).add(23);
console.log(t.addChildNode(t1).addChildNode(t2).addChildNode(t3));
console.log(depthSearchTree(t,7));
// 16.18 breadth first search on binary tree
function breadthSearchTree(tree,val){
console.log("breadth searching tree for: " + val);
console.log(tree);
if(tree.value === val) return true;
// search first level
for(var i=0;i<tree.numChildren();i++){
var child = tree.children[i];
if(child.value === val) return true;
}
// send search to next level
for(var j=0;j<tree.numChildren();j++){
var c = tree.children[j];
if(breadthSearchTree(c,val)) return true;
}
return false;
}
console.log(breadthSearchTree(t,5));
// 16.9 find all solutions to a^3+b^3 = c^3+d^3
function findSolutions(){
var solutions = [];
var limit = 100;
var a,b,c,d;
var acubed,bcubed,ccubed,dcubed;
var dcubed_dictionary = {};
var sol_map = {};
var pairs = {};
for(var i=0;i<limit;i++) dcubed_dictionary[i*i*i] = i;
for(a=0;a<limit;a++){
acubed = a*a*a;
for(b=a+1;b<limit;b++){
bcubed = b*b*b;
if(pairs[acubed+bcubed] === undefined) pairs[acubed+bcubed] = [{a:a,b:b}];
else pairs[acubed+bcubed].push({a:a,b:b});
if(pairs[acubed+bcubed].length >= 2) solutions.push(pairs[acubed+bcubed])
/*
for(c=a+1;c<b;c++){
if(c!=a && c!=b) {
ccubed = c*c*c;
dcubed = (acubed + bcubed - ccubed);
if(a==1 && b==12 && c==9) console.log(acubed + bcubed - ccubed)
// if d is integer then it is a solution
if(dcubed_dictionary[dcubed] && dcubed_dictionary[dcubed]>c && !(sol_map[a+b]) && !(sol_map[c+dcubed_dictionary[dcubed]])){
sol_map[a+b] = true;
sol_map[c+dcubed_dictionary[dcubed]] = true;
solutions.push(a+"^3+"+b+"^3="+c+"^3+"+dcubed_dictionary[dcubed]+"^3");
}
}
}*/
}
}
console.log(pairs); // all pairs where length > 2 are solutions ==> O(n^2)
console.log(dcubed_dictionary);
console.log(solutions)
}
findSolutions();
// noprotect
// 16.20 given string print all permutations (no duplicate characters)
function printPermuations(string){
// O(2^n)
if(string.length==1) return [string];
var list = [];
for(var i=0;i<string.length;i++){
var pivot = string[i];
console.log("pivot: "+ pivot)
var str = string.slice(0, i) + string.slice(i+1);
console.log("string: " + str)
// keep one character and permutate the remaining
var perms = printPermuations(str);
for(var j=0;j<perms.length;j++){
list.push(pivot + perms[j]);
}
}
return list;
}
console.log(printPermuations("abcd"));
// 16.21 given knows(a,b) returns if a and b know each other
// celebrity, everyone knows them but they know no one else
// findCelebrity()
function knows(a,b){
var hash = {
"ab": true,
"cb": true,
"db": true,
"ac": true,
"ca": true
}
return !(!hash[a+b]);
}
function findCelebrity(population){
var knowledge_hash = {};
knowledge_hash.knows = {};
knowledge_hash.isknown = {};
// build knowledge hash
for(var i=0;i<population.length;i++){
var a = population[i];
for(var j=0;j<population.length;j++){
if(i!=j){
var b = population[j];
if(knows(a,b)){
if(!knowledge_hash.knows[a])knowledge_hash.knows[a]=1;
else knowledge_hash.knows[a] += 1;
if(!knowledge_hash.isknown[b])knowledge_hash.isknown[b]=1;
else knowledge_hash.isknown[b] += 1;
}
}
}
}
// search knowledge has
for(var k=0;k<population.length;k++){
if(knowledge_hash.isknown[population[k]] == population.length-1
&& !(knowledge_hash.knows[population[k]])) return population[k];
}
console.log(knowledge_hash);
return false;
}
// 16.22 given NxN matrix of characters and list of valid words
// Print all valid words found by traversing the matrix, cannot re-use letters in same word
function findValidWords(matrix, valid_words) {
var valid_words_in_matrix = [];
var matrix_size = matrix.length; // assuming N*N
var hashes = (function() {
var hashes = {
words: {},
characters: {}
}
// create hashes for word and character
for (var ii = 0; ii < valid_words.length; ii++) {
var word = valid_words[ii];
hashes.words[word] = true;
for (var jj = 0; jj < word.length; jj++) {
var character = word[jj];
hashes.characters[jj] = hashes.characters[jj] || {};
hashes.characters[jj][character] = true;
}
}
return hashes;
})();
// creating helper functions
function canBeinPosition(letter, position) {
hashes.characters[position] = hashes.characters[position] || {};
return hashes.characters[position][letter] || false;
}
function isValidWord(word) {
return hashes.words[word]
}
function findWords(prefix, visited, row, col,dir) {
console.log("----FIND WORDS----")
console.log(dir)
console.log("prefx: " + prefix);
console.log(copyObj(visited));
console.log("matrix("+row+","+col+")="+matrix[row][col]);
var current_letter = matrix[row][col];
var new_word = prefix + current_letter;
console.log("new word: " + new_word)
if (visited[row + "" + col]) {
console.log("VISITED - STOP")
return false;
}
else visited[row + "" + col] = true;
// check if current letter can be the nth position in a valid word
if (!canBeinPosition(current_letter, new_word.length - 1)) {
console.log("NO POSSIBLE WORDS - STOP")
return false;
}
// check if prefix is a word
if (isValidWord(new_word)) {
console.log("WORD FOUND:" + new_word)
valid_words_in_matrix.push(new_word);
}
// do a check on all other directions recursively
// right
if (col + 1 < matrix_size) findWords(new_word, copyObj(visited), row, col + 1,"right");
else console.log(new_word + ": CANT GO RIGHT");
// down
if (row + 1 < matrix_size) findWords(new_word, copyObj(visited), row + 1, col,"down");
else console.log(new_word + ": CANT GO DOWN");
// left
if (col - 1 >= 0) findWords(new_word, copyObj(visited), row, col - 1,"left");
else console.log(new_word + ": CANT GO LEFT");
// up
if (row - 1 >= 0) findWords(new_word, copyObj(visited), row - 1, col,"up");
else console.log(new_word + ": CANT GO UP");
}
// loop through the matrix
for (var i = 0; i < matrix_size; i++) {
for (var j = 0; j < matrix_size; j++) {
findWords("", {}, i, j,"start"); // base case
}
}
return valid_words_in_matrix;
}
function copyObj(obj) {
return JSON.parse(JSON.stringify(obj));
}
console.log(findValidWords([
["B", "I", "N"],
["A", "O", "G"],
["T", "A", "R"]
], ["BINGO", "BAT", "GOAT", "RAT","LAX"]))
// noprotect
// 16.23. given array of +/- integers find the contiguous sequence with laargest sum.
function findMaxContiguous(a){
var max;
for(var i=0;i<a.length;i++){
var m = findMaxSum(a.slice(i));
if(i===0 || m > max) max = m
}
return max;
}
function findMaxSum(a){
var running_count = 0;
var max = 0;
for(var i=0;i<a.length;i++){
running_count += a[i];
if(running_count > max) max = running_count;
}
return max;
}
console.log(findMaxContiguous([2,-8,3,-2,4,-10]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment