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
).
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 concern lay mainly with how the string manipulation occurs: stripFirstLastParen
will strip the first and last paren, getCurrentVal
removes the value while reading it.
This was an exercise for an interview, and I'd like to fill some gaps in my knowledge:
I do understand that reading should be a non-destructive operation (i.e. getting the current value of the node shouldn't remove it from the input string). In this example, would it be worthwhile to separate concerns (read & alter input strings separately), or would that add complexity to the overhead? Iterating through the strings additionally may be argued as non-favorable (parse once to read, second time to remove the read value).
I can't think of any solid reason for "why should your read functions be idempotent" other than general testing/usability, is idempotency important here, or can it be casually swept under the rug (assuming this is an exercise)?