0

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)?

Community
  • 1
  • 1
Hodrobond
  • 1,665
  • 17
  • 18
  • If you're concerned that a get function with side-effects is misleading, then consider renaming your function to be clearer about what it actually does -- e.g. `getCurrentVal` to something like `popNextVal` (or just `pop`) – tavnab May 08 '17 at 19:45
  • This is why I hate most interview questions – aaaaaa May 08 '17 at 19:45
  • @tavnab I'm more concerned about whether or not I should care about these functions altering the string. On one hand, the string doesn't NEED to be read twice (in favor of speed/complexity), on the other hand testing is more difficult (idempotency is easier to test). – Hodrobond May 08 '17 at 19:48
  • 1
    If the function alters the string because that's part of its contract, then that's ok. You just need to be clear on what the pre & post-conditions of your function are, so you can test them predictably. Idempotence doesn't make it easier or harder to test (and in this case, it's more about being reentrant than idempotent, since idempotent functions _can_ change state; idempotence just means that calling it multiple times in a row is the same as calling it once). However, not being precise about a function's purpose & all side-effects indeed makes testing more difficult. – tavnab May 08 '17 at 19:51
  • @tavnab Fantastic, much appreciated. I believe you've given me the food for thought I need. It looks like I was overly concerned with a minor point (caused by getting lost in panic) which could be easily discussed next time. Thank you! – Hodrobond May 08 '17 at 19:56
  • 1
    @Hodrobond glad to help! One quick correction: when I said "reentrant" I meant to say ["Pure"](https://en.wikipedia.org/wiki/Pure_function). Reentrant functions are also Pure, and pure functions are indeed easier to test. – tavnab May 08 '17 at 20:05
  • If your only task is to sum elements of a certain tier, don't build a tree at all. Just count opening and closing braces. – Bergi May 08 '17 at 20:19
  • 1
    For fun, I wrote a [PEG grammar](https://pegjs.org) to parse & take the sums at each level. This problem seemed like a good fit for PEG: [here's the gist](https://gist.github.com/atavakoli/92ab42d523cc113ab4d8f99cfa85e12f), which you can play with in the online editor – tavnab May 08 '17 at 20:31
  • @tavnab Thank you very much! Now I've got some more to study, very much appreciated! =) – Hodrobond May 08 '17 at 20:47

0 Answers0