Excellent Interview Question (Part 2) - 18 June 2007

Just a quick follow up to my previous article on technical interview questions. It proved to be quite a popular post and I received lots of feedback and alternate solutions to the maze problem. Needless to say, many of the solutions were far superior to mine :)

Here are a couple of my favourites.

The first is from Joshua Paine. Joshua's solution is written in Javascript and wins the award for the simplest and most elegant solution.

var maze = [
      1, 0, 0, 0, 0,
      1, 0, 1, 1, 1,
      1, 0, 1, 0, 1,
      1, 0, 1, 0, 1,
      1, 1, 1, 0, 1 ];

function solvable(maze,w,h,x,y) {
  x || (x=0);
  y || (y=0);
  var i = y*w+x;
  if(x<0 || y<0 || x>=w || y>=h || !maze[i]) return false;
  if(x==(w-1) && y==(h-1)) return true;
  maze[i] = 0;
  return (solvable(maze,w,h,x,y+1) ||
          solvable(maze,w,h,x+1,y) ||
          solvable(maze,w,h,x,y-1) ||
          solvable(maze,w,h,x-1,y));
}

solvable(maze,5,5);

The second is from Aleksey Eschenko who wrote his solution in Ruby. Again, this solution is simple and to the point.

class Maze

  def initialize(array, width, heigth)
      @array, @width, @heigth = array, width, heigth
  end

  def routes
    calculate_routes([ [ [0, 0] ] ])
  end

  def [](x, y)
    if ( x >= @width || y >= @heigth || x < 0 || y < 0 ) then -1 else @array[y * @width + x] end
  end

  private

  def possible_steps(route)
    x, y = route.last
    [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]].select { |xy| !route.include?(xy) && self[*xy] == 1 }
  end

  def finished?(route)
    route.last == [@width - 1, @heigth - 1]
  end

  def calculate_routes(routes)
    return routes if routes.empty? || routes.select { |route| finished?(route) }.size == routes.size
    resultset = []
    routes.each do |route|
      if finished?(route)
        resultset << route
      else
        possible_steps(route).each { |xy| resultset << (route + [xy]) }
      end
    end
    calculate_routes(resultset)
  end

end

maze = Maze.new([ 1, 0, 1, 0,
                  1, 1, 1, 0,
                  1, 0, 1, 1,
                  1, 0, 0, 1], 4, 4)

puts !maze.routes.empty?

link