My Experience With a Programmer Coding Test (Survey)

http://spreadsheets.google.com/viewform?formkey=dElOMWhBa2t1cjFhVFFkcXVUelE0Tnc6MQ

by jcromartie • 16 years ago

12 25 16 years ago

spreadsheets.google.com

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.

RiderOfGiraffes3• 16 years ago

OK - I've done it.

macemoneta• 16 years ago

You're not looking for a programmer, you're looking for a JavaScript web developer. The requirement should be more specific.

blacksmythe• 16 years ago

Why restrict the language to Javascript? That is not really a programmer coding test.

Dysiode• 16 years ago

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

jcromartie3• 16 years ago

I'd accept C# using delegates, or C using structs and function pointers. Anything, really.

justinlilly2• 16 years ago

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• 16 years ago

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• 16 years ago

Recursion is also what the "exam" asked for, so I imagine you'd be dinged a bit for not using it.

jiaaro3• 16 years ago

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

justinlilly2• 16 years ago

Nope. That's correct as well. Recursion is a much more elegant way of doing it. :-/

kqr2• 16 years ago

Should the last line be:

  doTree(numTree, addNodeToSum)

gcr• 16 years ago

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

jcromartie3• 16 years ago

Overachiever :D

aidenn0• 16 years ago

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

jiaaro3• 16 years ago

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

jcromartie3• 16 years ago

I edited the problem to clarify leaf nodes.

droz• 16 years ago

handy wavy requirements lead to handy wavy code.

tetha• 16 years ago

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.

RiderOfGiraffes3• 16 years ago

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• 16 years ago

  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; });

RiderOfGiraffes3• 16 years ago

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• 16 years ago

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• 16 years ago

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• 16 years ago

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

My Experience With a Programmer Coding Test (Survey)

Related Stories