(Fair preface: this is an interview question I would like to improve my knowledge of. I got some rest, and re-solved the problem with a fresh/unpanicked mind)
Fair preface: This is an interview question I would like to improve my knowledge of. I got some rest, and re-solved the problem with a fresh/unpanicked mind.
My task is to find the summation of values at a particular tier, like (5+14=19\5ドル+14=19\$ which is the sum for n=1\$n=1\$, or 3+12+11+17=43\3ドル+12+11+17=43\$ the sum for n=2)\$n=2\$.
My main utility functions are:stripFirstLastParen (strips the first and last paren), getCurrentVal (retrieves the value of the current node), and getChildren (retrieves the left and right nodes).
stripFirstLastParen– strips the first and last parengetCurrentVal– retrieves the value of the current nodegetChildren– retrieves the left and right nodes
String manipulation.String manipulation. How should I properly be passing the altered string throughout the recursive function? Callout for lines like
var currentValue = getCurrentVal(input); var children = getChildren(currentValue.input);
Where the getChildren function relies on getCurrentValgetCurrentVal removing the value from the string itself, that feels dirty.
- Complexity.Complexity. I'm having difficulty describing the complexity of my procedure, and would argue that it's somewhere between O(n)\$O(n)\$ and O(n^2)\$O(n^2)\$, so...O(n^2) is it \$O(n^2)\$? Considering the parens and values are removed as they are parsed, that lends itself to O(n)\$O(n)\$, but I feel it's O(n^2)\$O(n^2)\$ because of the duplicate parsing in order to create the child nodes. Is that correct? Can it be improved?
(Fair preface: this is an interview question I would like to improve my knowledge of. I got some rest, and re-solved the problem with a fresh/unpanicked mind)
My task is to find the summation of values at a particular tier (5+14=19 which is the sum for n=1, 3+12+11+17=43 the sum for n=2).
My main utility functions are:stripFirstLastParen (strips the first and last paren), getCurrentVal (retrieves the value of the current node), and getChildren (retrieves the left and right nodes).
String manipulation. How should I properly be passing the altered string throughout the recursive function? Callout for lines like
var currentValue = getCurrentVal(input); var children = getChildren(currentValue.input);
Where the getChildren function relies on getCurrentVal removing the value from the string itself, that feels dirty.
- Complexity. I'm having difficulty describing the complexity of my procedure, and would argue that it's somewhere between O(n) and O(n^2), so...O(n^2)? Considering the parens and values are removed as they are parsed, that lends itself to O(n), but I feel it's O(n^2) because of the duplicate parsing in order to create the child nodes. Is that correct? Can it be improved?
Fair preface: This is an interview question I would like to improve my knowledge of. I got some rest, and re-solved the problem with a fresh/unpanicked mind.
My task is to find the summation of values at a particular tier, like \5ドル+14=19\$ which is the sum for \$n=1\$, or \3ドル+12+11+17=43\$ the sum for \$n=2\$.
My main utility functions are:
stripFirstLastParen– strips the first and last parengetCurrentVal– retrieves the value of the current nodegetChildren– retrieves the left and right nodes
String manipulation. How should I properly be passing the altered string throughout the recursive function? Callout for lines like
var currentValue = getCurrentVal(input); var children = getChildren(currentValue.input);
Where the getChildren function relies on getCurrentVal removing the value from the string itself, that feels dirty.
- Complexity. I'm having difficulty describing the complexity of my procedure, and would argue that it's somewhere between \$O(n)\$ and \$O(n^2)\$, so is it \$O(n^2)\$? Considering the parens and values are removed as they are parsed, that lends itself to \$O(n)\$, but I feel it's \$O(n^2)\$ because of the duplicate parsing in order to create the child nodes. Is that correct? Can it be improved?
Calculate the sum at a level of a binary tree represented in a String
(Fair preface: this is an interview question I would like to improve my knowledge of. I got some rest, and re-solved the problem with a fresh/unpanicked mind)
Given input of the type (10(5(3)(12))(14(11)(17)))
which would represent the following tree
n=0 10
n=1 5 14
n=2 3 12 11 17
My task is to find the summation of values at a particular tier (5+14=19 which is the sum for n=1, 3+12+11+17=43 the sum for n=2).
Considering this is a binary tree, a recursive function seems appropriate.
My main utility functions are:
stripFirstLastParen (strips the first and last paren), getCurrentVal (retrieves the value of the current node), and getChildren (retrieves the left and right nodes).
var input =
"(10(5(3)(12))(14(11)(17)))";
function stripFirstLastParen(input){
if(input[0] !== "(" || input[input.length - 1] !== ")"){
console.error("unbalanced parens")
}
else{
input = input.substr(1);
input = input.substring(0, input.length - 1);
}
return input;
}
function getCurrentVal(input){
var val = "";
while(input[0] !== "(" && input[0] !== ")" && input.length){
val += input[0];
input = input.substr(1);
}
return {
val,
input
}
}
function getChildren(input){
var val = "";
if(input.length == 0){
return {
left: "",
right: ""
}
}
if(input[0] !== "("){
console.error("no open paren at start");
}
val += input[0];
input = input.substr(1);
var parenStack = 1;
while(parenStack > 0){
if(input[0] == ")"){
parenStack--;
}
else if(input[0] == "("){
parenStack++;
}
val += input[0];
input = input.substr(1);
}
return {
left: val,
right: input
}
}
function getValueForLevel(input, k){
var totalValue = 0;
input = stripFirstLastParen(input);
var currentValue = getCurrentVal(input);
var children = getChildren(currentValue.input);
if(k > 0){
if(children.left.length){
totalValue += getValueForLevel(children.left, k-1);
}
if(children.right.length){
totalValue += getValueForLevel(children.right, k-1);
}
}
else if(k == 0){
totalValue += JSON.parse(currentValue.val);
}
return totalValue;
}
var test = getValueForLevel(input, 2);
console.log(test);My main concerns are:
String manipulation. How should I properly be passing the altered string throughout the recursive function? Callout for lines like
var currentValue = getCurrentVal(input); var children = getChildren(currentValue.input);
Where the getChildren function relies on getCurrentVal removing the value from the string itself, that feels dirty.
- Complexity. I'm having difficulty describing the complexity of my procedure, and would argue that it's somewhere between O(n) and O(n^2), so...O(n^2)? Considering the parens and values are removed as they are parsed, that lends itself to O(n), but I feel it's O(n^2) because of the duplicate parsing in order to create the child nodes. Is that correct? Can it be improved?
I tried to keep the "spirit of the challenge" and re-completed this within the amount of time previously allotted (somewhere around 30-45 minutes). Suggestions and improvements need not consider this time restriction, but providing context is important.