DEV Community

loading...

Discussion on: These problem-solving patterns will help you ace your next coding interview

Collapse
darthbob88 profile image
Raymond Price

I'd also add in a discussion of graph search, because that's the one that always gets me on technical screens.

Graph Search

The basic algorithm of graph search is

  1. Keep a list of nodes to search, initialized with a starter node. Optionally, keep a list of nodes you have visited.
  2. For each node in that list, search that node.
    1. If you've found the target, return.
    2. Otherwise, mark that node as visited and add that node's neighbors to the list to search.
  3. If you have run out of nodes to search, return an error.

Given a starting point (xStart, yStart) on a chessboard of size N * N, and an ending point (xEnd, yEnd), what is the minimum number of moves for a chess knight to get from the start to the end?

function minKnightMoves(n, xStart, yStart, xEnd, yEnd) {
    // Initialize chessboard. The value of each entry represents the number of moves to get there, as well as indicating whether we've visited that node.
    const chessboard = []
    for (let ii = 0; ii < n; ii++) {
      chessboard[ii] = [];
      for (let jj = 0; jj < n; jj++) {
        chessboard[ii][jj] = 0;
      }
    }

    // List of nodes to search. Using array with [x, y] to represent points.
    // We want to do breadth-first search, so we're using a FIFO queue.
    // Depth-first search would require a LIFO stack. 
    const nodeList = [ [xStart, yStart] ];

    // Search through each node.
    while (nodeList.length > 0) {
        const currNode = nodeList.pop();
        const currX = currNode[0];
        const currY = currNode[1];

        // If we've found the target, return the result
        if (currX == xEnd && currY == yEnd) {
            return chessboard[currX][currY];
        }

        // Search this node's neighbors
        if ((currX + 2 < n && currX + 2 >= 0) && (currY + 1 >= 0 && currY + 1 < n) && (chessboard[currX + 2][currY+1] == 0)) {
            chessboard[currX + 2][currY+1] = chessboard[currX][currY] + 1;

            if (currX + 2 == xEnd &&  currY + 1 == yEnd) {
                return chessboard[currX + 2][currY+1];
            } else {
                nodeList.push([currX + 2, currY + 1]);
            }
        }
        // Repeat the above for all 8 possible knight's moves from this node.

    }

    // We've searched every possible node and haven't found it. 
    return -1;
}
Enter fullscreen mode Exit fullscreen mode