srterpe
BAN USERfunction F (startDate, expirationDate, quantity) {
this.startDate = startDate
this.expirationDate = expirationDate
this.quantity = quantity
}
var Demand = F
var Supply = F
function fulfill(demand, supply) {
// First let's normalize all supply and demand objects
// to be of quantity 1
var tmp = demand
demand = []
for (var m = 0; m < tmp.length; ++m) {
var d = tmp[m]
for (var i = 0; i < d.quantity; ++i) {
demand.push(new Demand(d.startDate,
d.expirationDate, 1))
}
}
tmp = supply
supply = []
for (var n = 0; n < tmp.length; ++n) {
var s = tmp[n]
for (i = 0; i < s.quantity; ++i) {
supply.push(new Supply(s.startDate,
s.expirationDate, 1))
}
}
// Now each supply must have at least 3 days remaining
// lets assume that expirationDate and startDate are in
// milliseconds (ms)
for (n = 0; n < supply.length; ++n) {
supply[n].expirationDate -= 259200000
}
// I'm not entirely sure about `a demand is said to be
// fulfilled 24 hours after all demands have been mapped
// to correspondingly available supplies`
// I think it means that Demand.startDate => Demand.startDate
// + 24 hours.
for (m = 0; m < demand.length; ++m) {
demand[m].startDate += 86400000
}
// Now we should sort both supply and demand by expirationDate,
// ties are broken by a secondary key of `startDate`
function f (a, b) {
if (a.expirationDate < b.expirationDate) {
return -1
}
if (a.expirationDate > b.expirationDate) {
return 1
}
if (a.startDate < b.startDate) {
return -1
}
if (a.startDate > b.startDate) {
return 1
}
return 0
}
supply.sort(f)
demand.sort(f)
// Now all supply and demand is sorted so that
// it is in order of expirationDate and secondarily by
// startDate so that if a precedes b that means either:
// a.expirationDate < b.expirationDate ||
// a.expirationDate === b.expirationDate &&
// a.startDate < b.startDate
//
// Now for each demand we need to find the first supply that
// fulfills the demand conditions because at this point it
// is assured that if supply X fulfills demand Y then supply X-1
// to supply 0 do not.
// It is also guaranteed for either supply X or demand X that
// supply/demand X+1 either has a later startDate, a later
// expirationDate or both
var mapping = []
for (m = 0; m < demand.length; ++m) {
for (n = 0; n < supply.length; ++n) {
d = demand[m]
s = supply[n]
if (s.expirationDate >= d.expirationDate) {
if (s.startDate <= d.startDate) {
mapping.push([d, s])
break
}
}
}
}
return mapping
}
var solution
function extractNextWord(s, A) {
if (s === "") {
return [s, A]
}
for (var i = 1; i <= s.length; ++i) {
var w = s.substring(0, i)
if (d(w)) {
A.push(w)
var retVal = extractNextWord(s.substring(i),
A.slice(0))
if (retVal && retVal[0] === "") {
solution = retVal[1]
break
}
}
}
if (solution) {
return solution.join(' ')
}
}
function d(s) {
var dictionary = ["this", "is", "a", "valid", "sentence"]
return dictionary.indexOf(s) !== -1
}
console.log(extractNextWord('thisisavalidsentence', []))
// You have some money in you bank account, the only function to
// withdraw money is `uint_16t withdraw(uint_16t value)`. If `value`
// is greater than they money you have it returns 0, otherwise it
// withdraws the requested amount and returns the "value".
// Write a function that withdraws all your money.
"use strict";
const withdraw = require('./uint_16t-bank-account-withdraw');
module.exports = function () {
let money = 0;
let value = 65535;
let withdrawal;
while (value > 0) {
while (withdrawal = withdraw(value)) {
money += withdrawal;
}
value = Math.floor(value / 2);
}
return money;
};
// Given two words, design an algorithm/flowchart and write
// a function to print the letter(s) common to both words in
// sorted order. Make the function to perform a case
// insensitive operation.
"use strict";
module.exports = function (word1, word2) {
const hashMap = {};
let S = "";
let i;
for (i = 0; i < word1.length; i++) {
let c = word1.charAt(i);
hashMap[c.toLowerCase()] = 1;
}
word2 = word2.split("").sort();
for (i = 0; i < word2.length; ++i) {
if (hashMap[word2[i].toLowerCase()]) {
S += word2[i].toLowerCase();
}
}
return S;
};
// Given a cube made of N x N x N sub-cubes, how many sub-cubes are
// on the outside of the cube?
// Consider the trivial case N = 1, the answer is 1.
// Consider the next trivial case N = 2
// The answer is 8 because the 2x2x2 cube is comprised of only
// 8 subcubes, 1 @ each corner.
// Consider N = 3, we have 8 corner cubes, plus 1 cube in the
// center of each of the composite cube's 6 faces, plus 1 cube
// extra along the length of each of the main cube's 12 edges.
// Consider N = 4: 8 corner cubes, plus 4 cubes in the center
// of each face, plus the cubes between the corners on each of
// the 12 sides is 2.
// It turns out that this can be described by the following
// equation:
// ƒ(N) = 8 corner cubes + (6 faces * (N - 2)^2) + 12 sides * (N - 2)
"use strict";
module.exports = function (N) {
let sides = 0;
if (N === 1) {
sides = 1;
} else if (N > 1) {
sides = 8 + (6 * Math.pow(N-2, 2)) + (12 * (N - 2));
}
return sides;
};
// Return the count of unique words in an input
// string without using the String.prototype.split()
// method.
// Input: "Swan swam over the sea swim Swan swim Swan"
// Output: 4
module.exports = function (s) {
"use strict";
let count = 0;
let word;
while (word = /^\s*(\S\S*)/.exec(s)) {
word = word[1];
let re = new RegExp('\\b' + word + '\\b', 'i');
s = s.replace(re, '');
if (re.exec(s) === null) {
count++;
}
s = s.replace(new RegExp('\\b' + word + '\\b', 'ig'), '');
}
return count;
};
function swap(A, B) {
var hashTable = {};
var i;
for (i = A.length - 1; i >-1; i--) {
hashTable[A[i]] = i;
}
console.log(A, B);
for (i = 0; i < B.length; ++i) {
if (A[i] === B[i]) continue;
if (i !== hashTable[0])
swp(A, hashTable[0], i, hashTable);
swp(A, i, hashTable[B[i]], hashTable);
}
console.log(A, B);
}
function swp(A, i, j, table) {
console.log('swap A[' + i + '] = ' + A[i] + ' for A[' + j + '] = ' + A[j]);
var tmp = A[i];
A[i] = A[j]
A[j] = tmp;
table[A[j]] = j;
table[A[i]] = i;
}
swap([1, 0, 2,3,4], [2,1,3, 0, 4]);
swap([5,4,3,2,1,0], [0,1,2,3,4,5]);
//Output
[ 1, 0, 2, 3, 4 ] [ 2, 1, 3, 0, 4 ]
swap A[1] = 0 for A[0] = 1
swap A[0] = 0 for A[2] = 2
swap A[2] = 0 for A[3] = 3
[ 2, 1, 3, 0, 4 ] [ 2, 1, 3, 0, 4 ]
[ 5, 4, 3, 2, 1, 0 ] [ 0, 1, 2, 3, 4, 5 ]
swap A[5] = 0 for A[0] = 5
swap A[0] = 0 for A[0] = 0
swap A[0] = 0 for A[1] = 4
swap A[1] = 0 for A[4] = 1
swap A[4] = 0 for A[2] = 3
swap A[2] = 0 for A[3] = 2
swap A[3] = 0 for A[4] = 3
swap A[4] = 0 for A[0] = 4
[ 0, 1, 2, 3, 4, 5 ] [ 0, 1, 2, 3, 4, 5 ]
This implementation is poor but it does seem to work.
module.exports = function (s) {
var freqMap = {};
var array = [];
var tmp = [];
var i;
var key;
var total = 0;
var most = 0;
var type = null;
for (i = 0; i < s.length; i++) {
char = s.charAt(i);
freqMap[char] = freqMap[char] || [];
freqMap[char].push(char);
}
for (key in freqMap) {
if (freqMap.hasOwnProperty(key)) {
total += freqMap[key].length;
if (freqMap[key].length > most) {
type = key;
most = freqMap[key].length;
}
array.push(freqMap[key]);
}
}
// console.log('"' + type + '"', most, total);
if ( total - most < most - 1 ) {
return false;
}
array.sort(function (a, b) {
if (a.length > b.length) {
return -1;
} else if (a.length < b.length) {
return 1;
}
return 0;
});
// console.log(array);
tmp.push(array.shift());
while (tmp.length) {
var target = tmp.pop();
var src = array.shift();
if (!src) {
array.push(target);
continue;
}
if (array.length && target.length > src.length + 1) {
tmp.push(target);
tmp.push(src);
continue;
}
var res = [];
var q = Math.max(target.length, src.length);
for (i = 0; i < q; ++i) {
target[i] && res.push(target[i]);
src[i] && res.push(src[i]);
}
tmp.push(res);
}
return array[0].join("");
};
console.log(module.exports('aaaaabbbbcccceeeeeeeeeeddddffghijkl'))
//output
'eaedecefeaebeceheaedclabckadfbjdgbi'
var permutate = function (A, B, s) {
if (!A.length) {
B.push(s);
return;
}
var word = A[0];
var i;
for (i = 0; i < word.length; i++) {
permutate(A.slice(1), B, s + word.charAt(i));
}
};
var permutateList = function (A) {
var B = [];
permutate(A, B, "");
return B;
};
console.log(permutateList(["red", "fox", "super"]));
var iterator = function () {
var iters = arguments[0];
console.log(iters);
var index = 0;
return {
next: function () {
//assume iters return 'null' when there are no more values
var value = null;
while (iters.length && value === null) {
if (index === iters.length) {
index = 0;
}
value = iters[index++].next();
if (value === null) {
index--;
iters = iters.slice(0, index).concat(iters.slice(index+1, iters.length));
}
}
return value;
}
};
};
var A = {
_: ['a1', 'a2'],
i: 0,
next: function () {
return this._[this.i++] || null;
}
};
var B = {
_: ['b1'],
i: 0,
next: function () {
return this._[this.i++] || null;
}
};
var C = {
_: ['c1','c2', 'c3'],
i: 0,
next: function () {
return this._[this.i++] || null;
}
};
var iter = iterator([A,B,C]);
var next = iter.next();
while (next) {
console.log(next);
next = iter.next();
}
var decompose = function (A, B, s) {
if (!A.length) {
B.push(s);
return;
}
if (!s.length) {
s += '(' + A[0] + ')';
return decompose(A.slice(1), B, s);
}
for (var i = 0; i < A.length; i++) {
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' + ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' * ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' - ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' - ' + s + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' / ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' / ' + s + ')');
}
}
var solveFourIntegers = function (A, target) {
var B = [];
decompose(A.slice(), B, "");
return B.filter(function (exp) {
return eval(exp) === target;
});
};
console.log(solveFourIntegers([2,3,4,6], 24));
//output
[ '(((3 - (2)) * 4) * 6)',
'(6 / ((3 - (2)) / 4))',
'((4 / (3 - (2))) * 6)',
'(((3 - (2)) * 6) * 4)',
'(4 / ((3 - (2)) / 6))',
'((6 / (3 - (2))) * 4)',
'((((2) + 4) * 3) + 6)',
'((6 - ((2) - 4)) * 3)',
'(((4 - (2)) + 6) * 3)',
'(((4 / (2)) + 6) * 3)',
'((((2) * 6) - 4) * 3)',
'((4 - ((2) - 6)) * 3)',
'(((6 - (2)) + 4) * 3)',
'(((6 / (2)) + 3) * 4)' ]
var decompose = function (A, B, s) {
if (!A.length) {
B.push(s);
return;
}
if (!s.length) {
s += '(' + A[0] + ')';
return decompose(A.slice(1), B, s);
}
for (var i = 0; i < A.length; i++) {
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' + ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' * ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' - ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' - ' + s + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' / ' + A[i] + ')');
decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' / ' + s + ')');
}
}
var solveFourIntegers = function (A, target) {
var B = [];
decompose(A.slice(), B, "");
return B.filter(function (exp) {
return eval(exp) === target;
});
};
console.log(solveFourIntegers([2,3,4,6], 24));
//output
[ '(((3 - (2)) * 4) * 6)',
'(6 / ((3 - (2)) / 4))',
'((4 / (3 - (2))) * 6)',
'(((3 - (2)) * 6) * 4)',
'(4 / ((3 - (2)) / 6))',
'((6 / (3 - (2))) * 4)',
'((((2) + 4) * 3) + 6)',
'((6 - ((2) - 4)) * 3)',
'(((4 - (2)) + 6) * 3)',
'(((4 / (2)) + 6) * 3)',
'((((2) * 6) - 4) * 3)',
'((4 - ((2) - 6)) * 3)',
'(((6 - (2)) + 4) * 3)',
'(((6 / (2)) + 3) * 4)' ]
function bfs(G, v, x, y) {
var Q = [];
var S = [];
var count = 0;
Q.enqueue = Q.unshift
Q.dequeue = Q.pop;
Q.enqueue(v);
v.visited = true;
while (Q.length) {
v = Q.dequeue();
if (v.left && !v.left.visited) {
if (v.value > x) {
Q.enqueue(v.left);
}
v.left.visited = true;
}
if (v.right && !v.right.visited) {
if (v.value < y) {
Q.enqueue(v.right);
}
v.right.visited = true;
}
S.push(v);
}
while (S.length) {
v = S.pop();
var left = !v.left;
if (v.left) {
left = v.left.value > x && v.left.itCounts;
}
var right = !v.right;
if (v.right) {
right = v.right.value < y && v.right.itCounts;
}
v.itCounts = left && right;
if (!v.left && !v.right) {
if (v.value <= x || v.value >= y) {
v.itCounts = false;
}
}
if (v.itCounts) {
count++;
}
}
return count;
}
var Node = function (value) {
this.value = value;
};
var four = new Node(4);
var two = new Node(2);
var seven = new Node(7);
var one = new Node(1);
var three = new Node(3);
var five = new Node(5);
var six = new Node(6);
four.left = three;
two.right = four
two.left = one;
five.left = two;
seven.left = six;
five.right = seven;
console.log(bfs(null, five, 0, 5));
var Node = function (value) {
this.value = value;
};
function StepTree(v) {
var S = [];
S.push(v);
return {
next: function () {
while (S.length && S[S.length - 1].visited !== true) {
v = S.pop();
if (!v.visited) {
v.visited = true;
v.right && S.push(v.right);
S.push(v);
v.left && S.push(v.left);
}
}
return S.pop() || null;
}
};
}
function isSame(node1, node2) {
return node1.value === node2.value;
}
function compareInorder(tree1, tree2) {
tree1 = StepTree(tree1);
tree2 = StepTree(tree2);
var bool = true;
var node1 = tree1.next();
var node2 = tree2.next();
while (bool && (node1 || node2)) {
bool = isSame(node1, node2);
node1 = tree1.next();
node2 = tree2.next();
}
return bool;
}
var aA = new Node('A');
var aB = new Node('B');
var aC = new Node('C');
var bA = new Node('A');
var bB = new Node('B');
var bC = new Node('C');
aB.right = aA;
aB.left = aC;
bA.right = bB;
bB.right = bC;
compareInorder(aB, bA);
Maybe a custom type of quad-nary tree of either A or B maybe such that each node has four leaves instead of two:
X > A[i], y > i -- node A[i], i -- X < A[i] , y > i
X > A[i], i < y / \ X < A[i], i < y
And so on, but we would also need some internal balancing scheme similar to red black tree to fully ensure logarithmic run time, which would probably be non-trivial to implement.
- srterpe December 28, 2014#!/bin/sh
sed '1,$ {
s/'"$1"'/SED_FOO_1/g
s/'"$2"'/SED_FOO_2/g
s/'"$3"'/SED_FOO_3/g
s/'"$4"'/SED_FOO_4/g
s/'"$5"'/SED_FOO_5/g
s/SED_FOO_1/'"$6"'/g
s/SED_FOO_2/'"$7"'/g
s/SED_FOO_3/'"$8"'/g
s/SED_FOO_4/'"$9"'/g
s/SED_FOO_5/'"${10}"'/g
}'
./amazon.sh black night white day hose white day black night sprinkler < test.txt
I suppose one could just attempt an in-order traversal as well, memoizing the previous node's key (k-1). If we encounter the situation that k-1 > k, then this cannot be a bst.
edit: Something like this, do the throw to terminate the test when the tree is not conforming
function traverse(node, cb) {
if (!node) {
return
}
traverse(node.left, cb)
cb(node)
traverse(node.right, cb)
}
function callback(node) {
if (k_minus_one && node.key <= k_minus_one) {
throw new Error("Not a BST")
}
k_minus_one = node.key
}
var k_minus_one
function isBinarySearchTree(root) {
try {
traverse(root, callback)
return true
} catch (e) {
return false
}
}
edit...reverse my comparator
- srterpe September 04, 2014Updated answer a sort of brute force-ish O(n*m) solution. Use bit masks to "remove" the column (zero it out) if their is no bit mask that can generate n unique values then the answer is no.
Note that bit operations are pretty inefficient in Javascript since the language supports no integers, but whatever.
function manhattan_ii() {
"use strict"
args = Array.prototype.slice.call(arguments)
args = args.reverse()
tests = args.pop()
while (tests) {
rows = args.pop()
cols = args.pop()
bits = ""
for (i = 0; i < cols; ++i) {
bits += "1"
}
masks = []
for (i = 0; i < bits.length; ++i) {
masks[i] = bits.split("")
masks[i][i] = "0"
masks[i] = masks[i].join("")
masks[i] = parseInt(masks[i], 2)
}
console.log(masks)
samples = []
for (i = 0; i < rows; ++i) {
samples.push(parseInt(args.pop(), 2))
}
bool = false
for (i = 0; i < masks.length; ++i) {
hash = {}
for (j = 0; j < samples.length; ++j) {
n = masks[i] & samples[j]
if (hash[n]) {
break
} else {
hash[n] = true
}
}
if (j === samples.length) {
bool = true
break;
}
}
console.log("Test #" + tests + " : " + (bool ? "YES" : "NO"))
tests--
}
var args
, tests
, rows
, cols
, bits
, masks
, i
, samples
, j
, bool
, hash
,n
}
manhattan_ii(2,3,3,"101", "000", "100", 2, 2, "11", "11")
manhattan_ii(1, 4, 3, "011", "101", "111", "100")
manhattan_ii(1, 4, 3, "110", "101", "111", "100")
manhattan_ii(1, 5, 3, "110", "110", "101", "111", "100")
manhattan_ii(1, 2, 2, "11", "10")
/* output...
! node manhattan-ii.js
[ 3, 5, 6 ]
Test #2 : YES
[ 1, 2 ]
Test #1 : NO
[ 3, 5, 6 ]
Test #1 : NO
[ 3, 5, 6 ]
Test #1 : YES
[ 3, 5, 6 ]
Test #1 : NO
[ 1, 2 ]
Test #1 : YES
!
*/
Yes, you are right. I graphed it and it does break back toward O(n^3).
Here was the #s
! node time-complexity
1 0 0
2 0 0
4 4 0.0625
8 56 0.109375
16 560 0.13671875
32 4960 0.1513671875
64 41664 0.158935546875
128 341376 0.16278076171875
256 2763520 0.1647186279296875
512 22238720 0.16569137573242188
1024 178433024 0.16617870330810547
2048 1429559296 0.16642260551452637
It's not O(n^3) because the # of ops doesn't scale anywhere near n^3 as n increases,
consider `n = 16`, 16^2 = 256, 16^3 = 4096, at n= 16 this algorithm executes only 560 operations (this is more than 256, but is still an order of magnitude lower than O(n^3) so the lower order is O(n^2))
As to why this is the case: the reason is because as `i` iterates the number of `j` loops decreases and as `j` iterates the number of times `k` loops decreases.
If `i`, `j`, `k` were static loops of fixed iteration n then this would be O(n^3)
n = 16
sum = 0
for (i = 0; i < n - 2; i++)
for (j = i + 1; j < n - 1; j++)
for (k = j + 1; k < n; k++)
sum += 1
console.log(sum)
var sum
, i
, j
, k
, n
! node time-complexity.js
560
!
function _getMaxMarks() {
"use strict"
return this.maxMarks
}
function _isPass() {
"use strict"
return ((this.marks1 + this.marks2 + this.marks3) / 3) >= 40
}
function Marks(marks1, marks2, marks3) {
"use strict"
this.marks1 = marks1
this.marks2 = marks2
this.marks3 = marks3
this.maxMarks = Math.max.apply(Math, arguments)
}
function _totalStudents() {
"use strict"
return this.allMarks.length
}
function _passCount() {
"use strict"
return this.allMarks.filter(function (marks, i, allMarks) {
return marks.isPass()
}).length
}
function StudentList(allMarks) {
"use strict"
this.allMarks = allMarks
}
Marks.prototype.getMaxMarks = _getMaxMarks
Marks.prototype.isPass = _isPass
StudentList.prototype.totalStudents = _totalStudents
StudentList.prototype.passCount = _passCount
There are a couple of key points here:
1. Two equivalent binary strings are still equivalent no matter which column you remove.
2. There is no way to choose a column from n binary strings of m bits such that two or more members of N become equivalent unless m > n or unless N already has duplicates in it (see point #1).
Coded solution below...
function dups(array) {
"use strict"
hashmap = {}
for (i = 0; i < array.length; i++)
if (!hashmap[array[i]])
hashmap[array[i]] = true
else
return true
var hashmap
, array
, i
return false
}
function manhattan() {
"use strict"
args = Array.prototype.slice.call(arguments)
tests = args.shift()
no = 0
while (tests--) {
no++
rows = args.shift()
cols = args.shift()
if (rows > cols) {
console.log('test ' + no + ': NO')
continue
}
array = []
for (i = 0; i < rows; i++) {
array.push(args.shift())
}
if (dups(array)) {
console.log('test ' + no + ': NO')
continue
}
console.log('test ' + no + ': YES')
}
var args
, tests
, rows
, cols
, array
, no
, i
}
//ex
manhattan(4
// test1
, 3, 3
, 5, 0, 4 /* 0b101, 0b000, 0b100 */
// test2
, 2, 2
, 3, 3 /* 0b11, 0b11 */
// test3
, 4, 3
, 5, 0, 4, 7 /* 0b101, 0b000, 0b100, 0b111 */
// test4
, 3, 3
, 5, 5, 4 /* 0b101, 0b101, 0b100 */
)
/*
! node manhattan.js
test 1: YES
test 2: NO
test 3: NO
test 4: NO
!
*/
function pos(row, col, sum) {
var val = this[row][col]
return {
row: row,
col: col,
val: val,
sum: sum + val
}
}
function dfs(array) {
var S = []
, max = 0
, p
array.pos = pos
S.push(array.pos(0, 0, 0))
while (S.length) {
p = S.pop()
down = p.row + 1
right = p.col + 1
if (array[down])
S.push(array.pos(down, p.col, p.sum))
if (array[right])
S.push(array.pos(p.row, right, p.sum))
if (undefined === array[down] && undefined === array[right])
max = p.sum > max ? p.sum : max
}
return max
}
//e.g....
var maze = [
[0, 9, 2]
, [7, 50, 100]
, [10, 6, 6]
]
console.log(dfs(maze))
- srterpe December 04, 2016