Depth-First Search (DFS) is a popular algorithmic pattern used to traverse or search through data structures, particularly graphs and trees. It explores as far as possible along each branch before backtracking.

Here's an overview of how to use DFS in coding interviews, followed by example questions and their solutions using this pattern:

Step 1: Understand the Problem First, ensure you have a clear understanding of the problem requirements and constraints. Identify whether DFS is applicable to the problem at hand. DFS is useful when you need to explore all possibilities or find a specific path in a graph or tree structure.

Step 2: Design the DFS Algorithm Next, design the DFS algorithm based on the problem requirements. The general steps for implementing DFS are as follows:

1. Choose a starting point or node.
2. Visit the current node and mark it as visited.
3. Explore all unvisited neighboring nodes by recursively applying DFS to them.
4. Backtrack to the previous node and continue exploring other unvisited neighbors until all nodes are visited.

Step 3: Implement DFS Code Template Implement the DFS code template, which usually involves recursion or using a stack explicitly. The code template for DFS looks as follows:

def dfs(node, visited):
    # Base case: If the node has already been visited, return
    if node in visited:
        return

    # Mark the node as visited
    visited.add(node)

    # Process the current node
    # (e.g., perform required operations or checks)

    # Recursive DFS on neighboring nodes
    for neighbor in node.neighbors:
        dfs(neighbor, visited)

Step 4: Apply DFS to Example Questions Now let's look at a couple of example questions where DFS can be applied:

Example 1: Number of Islands Given a 2D grid consisting of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are surrounded by water.

Input:
[
  ['1', '1', '1', '1', '0'],
  ['1', '1', '0', '1', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '0', '0', '0']
]

Output: 1

Solution:

def numIslands(grid):
    if not grid:
        return 0

    num_rows = len(grid)
    num_cols = len(grid[0])
    visited = set()
    island_count = 0

    def dfs(row, col):
        if row < 0 or col < 0 or row >= num_rows or col >= num_cols:
            return
        if grid[row][col] == '0' or (row, col) in visited:
            return

        visited.add((row, col))
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)

    for row in range(num_rows):
        for col in range(num_cols):
            if grid[row][col] == '1' and (row, col) not in visited:
                island_count += 1
                dfs(row, col)

    return island_count

Example 2: Word Search Given a 2D board of letters and a word, determine if the word can be formed by sequentially adjacent cells (horizontally or vertically) on the board. Each cell may only be used once.

board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED"

Output: True

Solution:

def exist(board, word):
    if not board:
        return False

    num_rows = len(board)
    num_cols = len(board[0])
    visited = set()

    def dfs(row, col, index):
        if index == len(word):
            return True
        if (
            row < 0
            or col < 0
            or row >= num_rows
            or col >= num_cols
            or board[row][col] != word[index]
            or (row, col) in visited
        ):
            return False

        visited.add((row, col))
        if (
            dfs(row + 1, col, index + 1)
            or dfs(row - 1, col, index + 1)
            or dfs(row, col + 1, index + 1)
            or dfs(row, col - 1, index + 1)
        ):
            return True

        visited.remove((row, col))
        return False

    for row in range(num_rows):
        for col in range(num_cols):
            if board[row][col] == word[0] and dfs(row, col, 0):
                return True

    return False

These are just a couple of examples demonstrating how to use Depth-First Search (DFS) in coding interview questions. The DFS pattern can be applied to a wide range of problems involving graph traversal or pathfinding. Remember to adapt the code template and algorithm design based on the specific requirements of each problem.