HN Explorer

My Experience With a Programmer Coding Test (Survey) (spreadsheets.google.com)

12 points by jcromartie ↗ HN
Prompted by RiderOfGiraffes, I decided to put my programmer interview question in a Google Form and gather responses that way. I am concerned that no applicants have aced these questions thus far, although my peers seem to do OK.

25 comments

[ 2.9 ms ] story [ 66.3 ms ] thread
macemoneta
You're not looking for a programmer, you're looking for a JavaScript web developer. The requirement should be more specific.
blacksmythe
Why restrict the language to Javascript? That is not really a programmer coding test.
Dysiode
It may be that Scheme isn't used at their company (or that he doesn't read Scheme). This particular problem is simple enough it's not hard to write in Javascript anyway.

Besides, it's not an application, I'm sure you could write it in your favorite language of you wanted :)

jcromartie
I'd accept C# using delegates, or C using structs and function pointers. Anything, really.
justinlilly
My results:

  Array.prototype.contains = function(obj) {
    // copied from http://stackoverflow.com/questions/237104/javascript-array-containsobj
    var i = this.length;
    while (i--) {
      if (this[i] === obj) {
        return true;
      }
    }
    return false;
  }
  
  function doTree (node, func) {
    var seen = [];
    var to_see = [node];
    while to_see.length {
      var next_node = to_see.pop();
      func(next_node.value);
      seen.push(next_node);
      for (var i; i < next_node.children.length; i++) {
        var child = next_node.children[i];
        if (! seen.contains(child) && ! to_see.contains(child)) {
          to_see.push(child);
        }
      }
    }  
  }
  
  // --
  
  var num_arr = [];
  var sum = 0;
  doTree(numTree, function (val) { num_arr.push(val); })
  // googled for a sum function. didn't know if javascript had map or reduce in stdlib.
  
  for (var i; num_arr.length; i++) {
    sum += num_arr[i];
  }
  
  // sum is sum.
// --

5-10 min.

// --

its kind of a pain to do in a text box. variable width fonts make it harder to read. Would have also been nice to have an actual javascript repl. Was a bit shaky on tree traversal, but I think that's correct. Also not intimately familiar with javascript stdlib.

orangecat
Would have also been nice to have an actual javascript repl.

Chrome has it built in and Firefox has Firebug.

Was a bit shaky on tree traversal, but I think that's correct.

It's much simpler with recursion. Your contains method is "correct" but doesn't work in this case because objects with the same keys and values still aren't necessarily equal.

ydant
Recursion is also what the "exam" asked for, so I imagine you'd be dinged a bit for not using it.
jiaaro
wow... mine were much shorter than that. Maybe I did it wrong?

    var doTree = function doTree(node, fn) {
        for (var i = 0; i < node.children.length; i++) {
            doTree(node.children[i]);
        }
        fn(node.value);
    }

    var treeSum = 0;    
    doTree(numTree, function(nodeValue) {
        treeSum += nodeValue;
    });
edit: fixed a dumb bug edit2: nicer coding style
justinlilly
Nope. That's correct as well. Recursion is a much more elegant way of doing it. :-/
kqr2
Should the last line be:

  doTree(numTree, addNodeToSum)
gcr
Wow... you got... erm. something very different than I did.

  function mapTree(tree, fun) {
    // apply function to tree.value, then recurse (needs javascript.map)
    if (typeof tree == 'undefined') {
      return null;
    }
    return {
      value: fun(tree.value),
      children: tree.children.map(
        function(tree) {
          return mapTree(tree, fun);
        })
    };
  }

  //////////////////
  var numTree={value: 42,
       children: [
         {value: 43, children: []},
         {value: 44,
          children: [{value: 95, children: []},
                     {value: 1, children: []}]}
       ]
     };
  var count=0;
  
  mapTree(numTree, function(c) {
    count+=c;
  });

  alert(count); // => 225
aidenn0
it is unclear if the tree is restricted to being a binary tree or not. Also, it is unclear what a leaf node will look like (will children be null or an empty array, or an array of nulls?)
jiaaro
I believe each node may have an arbitrary number of children.

The problem definitely says that a leaf node will have an empty array as it's children property

jcromartie
I edited the problem to clarify leaf nodes.
droz
handy wavy requirements lead to handy wavy code.
tetha
I wonder how I would have done in that interview given that I don't know JS. My overall answers would have been:

- Well, I dont know JS, but in order to process a node, I have to apply the function to the value and recurse for each value in the array. This also handles leafes properly, because they have no children and thus no recursion occurs. Thus, I'd have to grab some web browser now and find some forach-loop and some functio-definition-syntax in JS now.

- In order to sum values up, I'd need some function which adds the value to an accumulator in place and destructively (such that the new value replaces the old value). Should be easy using closures or, in the worst case, a simple small object.

Overall, this took about 3 minutes. If I would search for javascript syntax now, I'd probably need around 10 - 20 additional minutes to get everything working.

RiderOfGiraffes
I provided my solution in Python, typed directly into the box. Sub 5 minutes, but I didn't keep a copy, and now there's no way I can get it back.

Did it pass? Can you email it back to me ...

bhiggins 

  function doTree(node, fn) {
       fn(node.value);
       for (var i = 0; i < node.children.length; ++i) {
           doTree(node.children[i], fn);
       }
   }

  var sum = 0;
  doTree(numTree, function(value) { sum += value; });
RiderOfGiraffes
I don't know JS at all, so I'm interested in this example. Can you really pass in a function like this and have the referencing to the variable "sum" work as you would want?

Can someone explain (or point to an explanation of) the scoping rules for me?

Thanks.

drewolson
In javascript, functions are closures. This means that the function "closes" over the environment in which it was defined. In the above example, the function has access to the sum variable because it was available at the time the function was defined. It is then free to add to that variable when the function is called at a later time.
rpdillon
It would have been nice to get a better specification for the behavior you wanted. The fact that you called it "doTree" rather than "mapTree" implies that it is a destructive operation, but it still would have been helpful for you to say so. I tend to think functionally, and my first reaction writing doTree was "Wait, what does this return?"
kennu
How about:

  do_tree([Value | Children], Fun) ->
    [Fun(Value) | [do_tree(Child, Fun) || Child <- Children]];
  do_tree([], _Fun) -> [].

  sum_tree(NumTree) ->
    lists:foldl(fun(Elem, AccIn) -> Elem+AccIn end, 0,
      lists:flatten(do_tree(NumTree, fun(Value) -> Value end))).