My New Favorite Interview Question

I interview a fair number of geeks every year and usually spend my alotted time going over one programming challenge. Lately I’ve been looking for a new one that was simple, but still big enough to give me a glimpse into their thinking. I think I’ve found it.

Why I Like This

I really like this question because:

  • A good solution involves recursion but you could approach it in multiple ways.
  • The seemingly simple Array throws a monkey-wrench into the whole thing.
  • It tests their ability to follow written instructions.
  • It should give an idea of how willing they are to ask questions.
  • It’s small, but with 3 separate, but connected, things to handle should be enough to give insight into how they work through things.
  • In my experience you’ll spend ~40 minutes on this regardless of experience level. I’ve only had one person do it in 5. If folks finish a little early I try and find out what kind of job would make them happy.

The Question

You’re presented with the following YAML file which you need to convert to a useful data structure, but for whatever reason you don’t have a YAML library. You do however, have something that has converted it into a tree of nodes.

Each node has some useful methods you can call:

  • node.type returns Array, Hash, or String
  • returns the name of the current node or null/nil if you’re looking at a node in an array.
  • node.value returns a node, or a String
  • returns the next node in the tree at the current level or null/nil (assume there are no empty nodes)
  • node.children will return all the child nodes.

The goal

Using the following YAML as an example, create a method that will take a “node” and return a useful data structure. In the case of the example YAML, that structure would look something like this (Ruby notation)

# en-us is just the name we've assigned to the method's return value.

en-us['date']['formats']['default']   #=> contains "%Y-%m-%d"
# en-us is a hash, with a key 'date', whose value is a hash, 
# ... with the key 'formats' whose value, in turn, is a hash
# ... with the key 'default' whose value is a string.
# So, hash->hash->hash->string

en-us['date']['day_names'][1]       #=> contains "Monday"
# hash->hash->array->string


Keep in mind that Arrays items can themselves be Hashes, Strings, or other Arrays, and they can be nested, or empty.

Notes for Inerviewer

I present the interviewee with “The Question” and “The Goal” one one side, with the YAML printed on the back. I point out the YAML and tell them that I’ll go over it with them when they reach that point. You can find a PDF version of it here.

I also tell them that “If you ask questions I’ll give you helpful answers. If you don’t ask questions I won’t. Please ask questions.” and let them know that I’m not looking for perfect syntax, optomized code, or anything like that. I only want to see them work through the problem. That is 100% true.

It is very common for people to go down the wrong route before solving this. If someone is stuck on it for a while, I’ll tell them that if they can verbalize what they’re thinking, or ask me questions I can help. Every now and then you’ll get someone who absolutely refuses the help. That’s ok. You don’t want someone who refuses to work with helpful coworkers when they’re stuck.

The test is not to see if they can do it entirely themselves. The test is to see how they’ll work through a problem, and how they’ll leverage the resource of someone who knows more than them.

People who give up are an automatic fail for me. If you can’t work through a problem with a helpful questionner at such a critical time I can’t trust you in a crunch.

Help folks who ask questions. Give them honest answers and leading hints. Don’t give them the answer, obviously, but work with them like the future coworker they might. Help them to figure it out by building on the thoughts in their head.

Note that Junior / Intern level people may not have encountered the concept of recursion. That’s ok. At some point you may have to ask them if they’re familiar with it. Walk them through the idea and see if they can solve it then. Some mid-level people have it in their heads that recurion is evil for “performance reasons” and should be avoided at all costs. Assure them you don’t care about performance.

About the YAML

When they’re ready to look at the YAML I tell them that each line is a “node”. I then tell them I’m going to ask them some really “stupid” questions just to make sure you understand everything. I assure them that it’s not a trick. And then I ask them what the expected return values would be for each node type and make sure they understand that if i give them the - Tuesday node they’d give me the string "Tuesday", day_names becomes an array of seven strings, and so on. I also note that there can be nested data structures and that I don’t want a solution that would work for any tree of data structures, not just this tree.

The Yaml

      default: "%Y-%m-%d"
      short: "%b %d"
      long: "%B %d, %Y"

      - Sunday
      - Monday
      - Tuesday
      - Wednesday
      - Thursday
      - Friday
      - Saturday
      default: "%a, %d %b %Y %H:%M:%S %z"
      short: "%d %b %H:%M"
      long: "%B %d, %Y %H:%M"
    am: "am"
    pm: "pm"