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.
  • Some people will be able to plow through it in 5 minutes. Some will take 20.

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.

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"