Find a golden tile from a list of tiles I had an interview and was asked a problem. I provided a solution and wanted to make sure if this is correct.

There is a Tile class. It has a boolean variable isGoldenTile which is false for all but true for one tile.

There is a List&lt;Tile&gt; neighbors. These are list of its immediate neighbors which are tiles.

There is a method getNeighbors() which returns the list of neighbors.

Finally, there is a method findGoldenTile which returns a Tile object. This returns the golden tile.

In no way I could alter the class except for the method body for findGoldenTile.

Here is my solution:

public class Tile {

    private boolean isGoldenTile = false;   
    private List&lt;Tile&gt; neighbors = null;

    public Tile(boolean isGoldenTile, List&lt;Tile&gt; neighbors) {
        this.isGoldenTile = isGoldenTile;
        this.neighbors = neighbors;
    }

    public boolean isGoldenTile() {
        return isGoldenTile;
    }

    public List&lt;Tile&gt; getNeighbors() {
        return neighbors;
    }

    public Tile findGoldenTile() {
        if(this.isGoldenTile == true){
            return this;
        } else if (this.getNeighbors().size() &gt; 0){
            for(int i=0;i&lt;this.getNeighbors().size();i++){
                if(this.getNeighbors().get(i).isGoldenTile == true){
                    return this.getNeighbors().get(i);
                }
            }
        } else {
            for(int i=0;i&lt;this.getNeighbors().size();i++){
                return this.getNeighbors().get(i).findGoldenTile();
            }
        }
        return null;
    }
}
You need to keep track of visited tiles, or you risk ending in an infinite (recursive) loop. If you use recursion, and if you are not allowed to change the class, this is difficult, as you'd need to add another parameter to findGoldenTile holding the already visited tiles.

Alternatively, you could not make it recursive, but with a queue and with the set of visited tiles in the method itself. Something like this (not tested):

public Tile findGoldenTile() {
    Set&lt;Tile&gt; visited = new HashSet&lt;&gt;();
    LinkedList&lt;Tile&gt; queue = new LinkedList&lt;&gt;();
    queue.add(this);
    visited.add(this);
    while (! queue.isEmpty()) {
        Tile tile = queue.pop();
        if (tile.isGoldenTile) {
            return tile;
        }
        for (Tile x : tile.neighbors) {
            if (! visited.contains(x)) {
                queue.add(x);
                visited.add(x);
            }
        }
    }
    return null;
}