justinm
BAN USERSimilar to Gils idea but each item on the stack records the max value at time it was added.
Push, Pop, Peek all O(1)
Space complexity is 2n
function StackEx() {
this.items = [];
}
StackEx.prototype.push = function (val) {
if (this.items.length === 0) {
this.items.push(new StackExItem(val, val))
} else {
var maxVal = Math.max(this.items[this.count() - 1].maxValue, val);
this.items.push(new StackExItem(val, maxVal));
}
}
StackEx.prototype.pop = function () {
return this.items.pop().value;
}
StackEx.prototype.peekHighest = function () {
return this.items[this.items.length - 1].maxValue;
}
StackEx.prototype.count = function () {
return this.items.length;
}
function StackExItem(val, maxValue) {
this.value = val;
this.maxValue = maxValue;
}
This algorithm assumes they wanted us to use the most basic functions.
First normalize both strings so they both have same number of digits before and after the decimal. This is not necessary but makes the code simpler later.
Then do simple addition on the char values, carrying any values to the next char sum.
function sumOfStrings(a, b) {
var aIdx = a.indexOf('.');
var bIdx = b.indexOf('.');
if (aIdx > -1 || bIdx > -1) {
// if one string has a decimal make sure they both do
if (aIdx === -1) {
a += '.';
aIdx = a.length - 1;
}
if (bIdx === -1) {
b += '.';
bIdx = b.length - 1;
}
var aDecimalCount = a.length - aIdx - 1;
var bDecimalCount = b.length - bIdx - 1;
var maxDecimalCount = Math.max(aDecimalCount, bDecimalCount);
// pad decimal values for one of the strings if necessary
while (aDecimalCount < maxDecimalCount) {
a += '0';
aDecimalCount++;
}
while (bDecimalCount < maxDecimalCount) {
b += '0';
bDecimalCount++;
}
}
// pad digits to left of decimal if necessary
while (a.length > b.length) {
b = '0' + b;
}
while (b.length > a.length) {
a = '0' + a;
}
var total = '';
var carry = 0;
var hasDecimal = false;
var zeroPoint = '0'.charCodeAt(0);
for (var i = a.length - 1; i >= 0; i--) {
var aVal = a.charCodeAt(i) - zeroPoint;
var bVal = b.charCodeAt(i) - zeroPoint;
// handle decimal if exists
if (a.charAt(i) === '.') {
if (hasDecimal) {
throw new Error('String cannot have multiple decimal points');
}
hasDecimal = true;
total = '.' + total;
carry = 0;
continue;
}
if (aVal < 0 || aVal > 9 || bVal < 0 || bVal > 9) {
throw new Error('String values can only be numbers or decimal point');
}
var tmp = aVal + bVal + carry;
carry = 0;
if (tmp > 9) {
carry = 1;
tmp = tmp - 10;
}
total = tmp + total;
}
if (carry > 0) {
total = carry + total;
}
return total;
}
Non-recursive method in javascript.
Add pairs of nodes to compare to the queue.
Pop the left/right pairs off and compare if their structure is the same (null/not null).
Then repeat for left.left + right.right and left.right, right.left.
function isFoldable(node) {
var queue = [node.left, node.right];
while (queue.length > 0) {
var left = queue.shift();
var right = queue.shift();
if (left == null && right == null) {
continue
}
if (left == null || right == null) {
return false;
}
queue.push(left.left);
queue.push(right.right);
queue.push(left.right);
queue.push(right.left);
}
return true;
}
Almost identical to the most voted solution, but since I did the work I wanted to post it anyways.
Do breadth first search with 2 stacks and a variable for specifying the direction we are moving (left or right) so we can add the child nodes to the stacks in correct order.
/*
Tree:
20
/\
10 30
/\ /\
5 15 25 35
Output:
20
10 30
35 25 15 5
*/
function doZigZagOrderTest() {
var tree = new Tree();
[20, 10, 30, 5, 15, 25, 35].forEach(function (val) {
tree.add(val);
});
zigZagOrder(tree);
}
function zigZagOrder(tree) {
var currentStack = [tree.node];
var nextStack = [];
var printString = '';
var left = true;
while (currentStack.length > 0) {
var n = currentStack.pop();
if (n != null) {
printString += n.value + ' ';
if (left) {
nextStack.push(n.right);
nextStack.push(n.left);
} else {
nextStack.push(n.left);
nextStack.push(n.right);
}
}
if (currentStack.length === 0) {
currentStack = nextStack;
nextStack = [];
console.log(printString);
printString = '';
left = !left;
}
}
}
function Tree() {
this.node;
}
Tree.prototype.add = function (val) {
if (!this.node) {
this.node = new TreeNode(val);
} else {
this.node.add(val);
}
}
function TreeNode(val) {
this.value = val;
this.left;
this.right;
}
TreeNode.prototype.add = function (val) {
if (val === this.value) {
return;
} else if (val < this.value) {
if (!this.left) {
this.left = new TreeNode(val);
} else {
this.left.add(val);
}
} else {
if (!this.right) {
this.right = new TreeNode(val);
} else {
this.right.add(val);
}
}
}
1. for each word create dictionary entries for possiblePalindrome=>[word]
We do this by:
a) adding an entry for the word reversed if it is not a palindrome.
b) taking any palindrome suffixes of the word and reversing the prefix.
Don't include the first char in this check because there has to be some prefix chars remaining after we find the suffix palindrome so we can know what chars can be added to the suffix palindrome to make it symmetrical.
i.e. For the word 'cata' the palindrome suffixes are 'ata', 'a'.
The dictionary entries for would be: 'c'=>['cata'], 'tac'=>['cata'], 'atac'=>['cata'].
The entry is an array because multiple words might have the same possible palindrome.
2. Now for each word in the list you can look up the words that are palindrome pairs.
findPalindromePairs(['cata', 'c', 'atac', 'tac', 'cat', 'a']);
returns
atac, cata
cata, c
cata, atac
cata, tac
cat, tac
tac, cat
function findPalindromePairs(list, hash) {
// for each word, add entries for each possible palindrome pair
// build dictionary of possiblePalindromePair=>[word] // several words might have same palindrome pairs
list.forEach(function (word) {
findPossiblePalindromePairs(word, hash);
});
// look up each word in the list from the dictionary
var pairs = [];
list.forEach(function (word) {
if (hash[word]) {
hash[word].forEach(function (match) {
pairs.push([match, word]);
});
}
});
return pairs;
}
function findPossiblePalindromePairs(word, hash) {
// don't add reverse self if word is a palindrome
// otherwise it will match to itself
if (!isPalindrome(word)) {
var wordReversed = reverseWord(word);
if (!hash[wordReversed]) {
hash[wordReversed] = [word];
} else {
hash[wordReversed].push(word)
}
}
var start = 1; // skip first char
while (start < word.length) {
// search for char that matches end char
if (word[start] === word[word.length - 1]) {
var palindromeSuffix = word.substring(start, word.length);
if (isPalindrome(palindromeSuffix)) {
var prefixReversed = reverseWord(word.substring(0, start))
if (!hash[prefixReversed]) {
hash[prefixReversed] = [word];
} else {
hash[prefixReversed].push(word)
}
}
}
start++;
}
}
function isPalindrome(word) {
var start = 0;
var end = word.length - 1;
while (start < end) {
if (word.charAt(start) !== word.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
function reverseWord(word) {
var ret = '';
for (var i = 0; i < word.length; i++) {
ret = word.charAt(i) + ret;
}
return ret;
}
Iterate over array finding start/end indexes for each group then swap elements in group to reverse.
- justinm May 18, 2015