Matrix

Question 1

Given m x n matrix, what’s the formula to compute the number the diagonals in the matrix even if m != n?

Answer 1

diagonal_cnt = m + n - 1

Question 2

Given 2 positions in a matrix, implement a tiny method to check if they are on the same diagonal.

input: row1, col1, row2, col2
output: True or False

Answer 2

def is_same_diagonal(row1, col1, row2, col2):
          # same left diagonal?                     # same right diagonal?
return ((row1 - col1) == (row2 - col2)) or ((row1 + col1) == (row2 + col2))

Question 3

Implement

Solution to the N-Queens Problem with time complexity of O(N!) and space complexity of O(N)

Answer 3

def solve_n_queens_count(n):
    count = 0

    def backtrack(row, cols, slash_diags, backslash_diags):
        nonlocal count
        if row == n:
            count += 1
            return

        for col in range(n):
            slash = row - col
            backslash = row + col

            if col in cols or slash in slash_diags or backslash in backslash_diags:
                continue

            # Choose
            cols.add(col)
            slash_diags.add(slash)
            backslash_diags.add(backslash)

            # Explore
            backtrack(row + 1, cols, slash_diags, backslash_diags)

            # Unchoose
            cols.remove(col)
            slash_diags.remove(slash)
            backslash_diags.remove(backslash)

    backtrack(0, set(), set(), set())
    return count