I recently gave an interview and was asked the following question. I posted this here Finding path in Maze also, and someone suggested I should try Code Review. So here it goes.

A maze is a group of linked Places. Each Place has a North, South, East, and West Place adjacent to it. There are two special pre-defined Place's: Place Wall represents a wall - the mouse can't go there. Place Cheese is ... cheese! The connections between Places are symmetrical - if you start from any Place and go North and then South, you return to where you were.

To simplify things, the maze has no closed loops - that is, if you start in any Place and follow any path, you eventually either hit a wall or find cheese - you never come back to the Place you started unless you actually retrace your steps.

A mouse starts off in some Place and searches around for Cheese. When it finds Cheese, it returns a set of directions - a string of the letters NSEW that lead from where it started to the Cheese.

The following framework defines the classes and functions. Some other code not included here generates a maze by creating a bunch of Place's and linking them. It then calls mouse(), passing some starting Place from the maze:

interface Place {

// Return the adjacent Place in the given direction
public Place goNorth();
public Place goSouth();
public Place goEast();
public Place goWest();

// Returns true only for the special "Wall" place
public bool isWall();

// Returns true only for the special "Cheese" place
public bool isCheese();
};

class Mouse {
  public Mouse() {}

  // Return a string of the letters NSEW which, if used to traverse the
  // the maze from startingPoint, will reach a Place where isCheese() is
  // true.  Return null if you can't find such a path.
  public String findCheese(Place startingPoint) {
    ... fill this in ...
  }
}

Implement findCheese(). You can add any fields or helper methods you need to Mouse. Extra credit: Eliminate the "no closed loops" restriction. That is, change your code so that it works correctly even if there might be a path like SSNEEW that leads the mouse back to the Place it started from.

This is what I tried. I understand this won't be the best or optimized solution, and wanted feedback as to what I else I could try. I have not considered the extra credit part

public String findCheese(place startingPoint)
{
    //Call helper function in all 4 directions;
    return findCheeseHelper(startingPoint,new StringBuilder("N")).append(
        findCheeseHelper(startingPoint,new StringBuilder("S"))).append(
            findCheeseHelper(startingPoint,new StringBuilder("E"))).append(
                findCheeseHelper(startingPoint,new StringBuilder("W"))).toString();
}


public StringBuilder findCheeseHelper(place startingPoint, StringBuilder direction)
{
    StringBuilder nDir=new StringBuilder("");
    StringBuilder sDir=new StringBuilder("");
    StringBuilder eDir=new StringBuilder("");
    StringBuilder wDir=new StringBuilder("");

    //Rerturn which direction this step came from if cheese found
    if(startingPoint.isCheese())
    {
        return direction;
    }
    //Specify this is not a correct direction by returning an empty String
    else if(startingPoint.isWall())
    {
        return "";
    }

    //Explore all other 3 directions (except the one this step came from)
    if(direction=="N")
    {
        sDir=findCheeseHelper(startPoint.goSouth(), new StringBuilder("N"));
        eDir=findCheeseHelper(startPoint.goEast(), new StringBuilder("E"));
        wDir=findCheeseHelper(startPoint.goWest(), new StringBuilder("W"));
    }
    else if(direction=="E")
    {
        nDir=findCheeseHelper(startPoint.goNorth(), new StringBuilder("N"));
        sDir=findCheeseHelper(startPoint.goSouth(), new StringBuilder("S"));
        wDir=findCheeseHelper(startPoint.goWest(), new StringBuilder("E"));
    }
    else if(direction=="W")
    {
        nDir=findCheeseHelper(startPoint.goNorth(), new StringBuilder("N"));
        sDir=findCheeseHelper(startPoint.goSouth(), new StringBuilder("S"));
        eDir=findCheeseHelper(startPoint.goEast(), new StringBuilder("W"));
    }
    else if(direction=="S")
    {
        nDir=findCheeseHelper(startPoint.goNorth(), new StringBuilder("S"));
        eDir=findCheeseHelper(startPoint.goEast(), new StringBuilder("E"));
        wDir=findCheeseHelper(startPoint.goWest(), new StringBuilder("W"));
    }

    //If I hit wall in every direction, I will get empty string and so specify to calling 
    //function that this is not a correct direction
    if(nDir.equals("") && sDir.equals("") && eDir.equals("") && wDir.equals(""))
        return new StringBuilder("");

    //If Cheese was found in even 1 direction, return direction to come to this step, appended with the path
    // forward to the calling function
    return direction.append(nDir).append(sDir).append(eDir).append(wDir);
}