Jobs

Interviews

Discussions

Check if Two Chessboard Squares Have the Same Color

Easy

Amazon

1 view

Topics:

Strings

You are given two strings, coordinate1 and coordinate2, representing the coordinates of a square on an 8 x 8 chessboard.

Return true if these two squares have the same color and false otherwise.

The coordinate will always represent a valid chessboard square. The coordinate will always have the letter first (indicating its column), and the number second (indicating its row).

For example:

If coordinate1 = "a1" and coordinate2 = "c3", return true because both squares are black.
If coordinate1 = "a1" and coordinate2 = "h3", return false because square "a1" is black and "h3" is white.

Write a function to determine if two chessboard squares have the same color given their coordinates.

Check if Two Chessboard Squares Have the Same Color

Easy

Amazon

1 view

Topics:

Strings

You are given two strings, coordinate1 and coordinate2, representing the coordinates of a square on an 8 x 8 chessboard.

Return true if these two squares have the same color and false otherwise.

The coordinate will always represent a valid chessboard square. The coordinate will always have the letter first (indicating its column), and the number second (indicating its row).

For example:

If coordinate1 = "a1" and coordinate2 = "c3", return true because both squares are black.
If coordinate1 = "a1" and coordinate2 = "h3", return false because square "a1" is black and "h3" is white.

Write a function to determine if two chessboard squares have the same color given their coordinates.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The input is a string of length 2 representing a square on the chessboard. What characters are valid for the column (first character) and the row (second character) of the chessboard square?
Are the column and row characters case-sensitive? For instance, should I treat 'a1' and 'A1' as the same square?
Is the input always guaranteed to be a valid chessboard square string with length 2, or should I handle invalid inputs (e.g., empty string, string of length greater than 2, invalid characters)?
Is there a specific return type? For example, should I return a boolean `true` or `false`, or a string like 'Same' or 'Different'?
If given invalid input, what is the expected return value? Should I return `null`, throw an exception, or return a default value like `false`?

Brute Force Solution

Approach

The brute force approach for this problem is like having a real chessboard and just visually checking each square's color. We figure out each square's color individually based on its position and then compare if they are the same.

Here's how the algorithm would work step-by-step:

Think of a chessboard where each square is labeled with a column letter (a through h) and a row number (1 through 8).
To find the color of the first square, consider that 'a1' is black. Then 'a2' must be white, 'a3' black, and so on. Similarly 'b1' is white, 'b2' is black, and so on.
Determine the color of the first square based on its column letter and row number. One way to do this is to add the letter's position in the alphabet to the row number. If that sum is even, the square is black. If it is odd, the square is white.
Repeat this process to determine the color of the second square.
Finally, compare the colors you found for each square. If they are the same, then the squares have the same color. If they are different, then they do not.

Code Implementation

def check_same_color(square_one, square_two):
    # Determine the color of the first square
    column_one_position = ord(square_one[0]) - ord('a') + 1
    row_one = int(square_one[1])

    sum_one = column_one_position + row_one

    square_one_is_black = sum_one % 2 == 0

    # Determine the color of the second square
    column_two_position = ord(square_two[0]) - ord('a') + 1
    row_two = int(square_two[1])

    sum_two = column_two_position + row_two
    
    square_two_is_black = sum_two % 2 == 0
    # Compare the colors of the squares
    if square_one_is_black == square_two_is_black:
        return True
    
    return False

Big(O) Analysis

Time Complexity

O(1) – The algorithm determines the color of each square based on simple arithmetic calculations involving the column letter and row number. Finding the alphabetical position of the column letter takes constant time. The addition and modulo operations also take constant time. Since these operations are performed a fixed number of times (twice, once for each square), the time complexity is constant regardless of the input. Thus, the overall time complexity is O(1).

Space Complexity

O(1) – The algorithm determines the color of each square by calculating the sum of the column's alphabetical index and the row number. It stores the color of each square (either implicitly or explicitly, but always a constant number of colors: two in this case). Since only a fixed number of variables (specifically, for storing the column index, row number, and possibly the color of each square) are used regardless of the input square coordinates, the auxiliary space remains constant. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The key is to realize we don't need to know the exact coordinates, just whether the two squares share the same color. We can figure this out using a simple trick: think about how chessboards alternate colors.

Here's how the algorithm would work step-by-step:

Imagine a chessboard. Notice how the color changes as you move across or down a row/column.
Consider a single square. The color of that square is determined by whether the column letter and row number are both 'even' or both 'odd'. If one is even and the other is odd, it's the other color.
Figure out if the first square's column and row are both 'even' or both 'odd'.
Figure out if the second square's column and row are both 'even' or both 'odd'.
If both squares have column and row that are both 'even' or both 'odd' then they are the same color, otherwise they are different colors.

Code Implementation

def check_chessboard_squares_color(square_one, square_two):

    column_one = ord(square_one[0])
    row_one = int(square_one[1])
    column_two = ord(square_two[0])
    row_two = int(square_two[1])

    # Check if both column and row are even or odd for the first square
    square_one_same_parity = (column_one % 2 == row_one % 2)

    # Check if both column and row are even or odd for the second square
    square_two_same_parity = (column_two % 2 == row_two % 2)

    # If both squares have the same parity, they have the same color
    if square_one_same_parity == square_two_same_parity:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(1) – The algorithm performs a fixed number of operations regardless of any input size. It extracts row and column information from two chessboard square coordinates, determines if each coordinate's row and column indices are both even or both odd, and then compares the results. These operations are constant time, involving only arithmetic and comparisons, and do not depend on the size of any input array or structure. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The provided steps outline a series of comparisons that involve extracting column and row information from the input strings, but they do not explicitly create or use any auxiliary data structures. The algorithm relies on determining whether these extracted values are 'even' or 'odd', which can be accomplished using simple arithmetic operations, without needing additional memory that scales with the input. Therefore, the space complexity is constant, independent of the input strings representing chessboard squares.

Edge Cases

Case	How to Handle
Invalid input string length (not equal to 2)	Return false if the string length is not 2, as it's not a valid square representation.
Invalid input: Non-letter for the column (first character)	Return false if the first character is not a letter between a and h (or A and H), indicating an invalid column.
Invalid input: Non-digit for the row (second character)	Return false if the second character is not a digit between 1 and 8, indicating an invalid row.
Both squares are the same square	The problem implies distinct squares but if the same input is provided twice the function should return true (same color).
Lowercase vs. Uppercase Letters	Convert the column letter to lowercase to ensure case-insensitive comparison and calculation.
Adjacent squares on the same row	Test for correct color determination when columns are next to each other.
Adjacent squares on the same column	Test for correct color determination when rows are next to each other.
Squares at extreme corners (a1, h8, a8, h1)	Verify correctness for squares at the corners of the chessboard.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The input is a string of length 2 representing a square on the chessboard. What characters are valid for the column (first character) and the row (second character) of the chessboard square?
Are the column and row characters case-sensitive? For instance, should I treat 'a1' and 'A1' as the same square?
Is the input always guaranteed to be a valid chessboard square string with length 2, or should I handle invalid inputs (e.g., empty string, string of length greater than 2, invalid characters)?
Is there a specific return type? For example, should I return a boolean `true` or `false`, or a string like 'Same' or 'Different'?
If given invalid input, what is the expected return value? Should I return `null`, throw an exception, or return a default value like `false`?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Think of a chessboard where each square is labeled with a column letter (a through h) and a row number (1 through 8).
To find the color of the first square, consider that 'a1' is black. Then 'a2' must be white, 'a3' black, and so on. Similarly 'b1' is white, 'b2' is black, and so on.
Determine the color of the first square based on its column letter and row number. One way to do this is to add the letter's position in the alphabet to the row number. If that sum is even, the square is black. If it is odd, the square is white.
Repeat this process to determine the color of the second square.
Finally, compare the colors you found for each square. If they are the same, then the squares have the same color. If they are different, then they do not.

Code Implementation

def check_same_color(square_one, square_two):
    # Determine the color of the first square
    column_one_position = ord(square_one[0]) - ord('a') + 1
    row_one = int(square_one[1])

    sum_one = column_one_position + row_one

    square_one_is_black = sum_one % 2 == 0

    # Determine the color of the second square
    column_two_position = ord(square_two[0]) - ord('a') + 1
    row_two = int(square_two[1])

    sum_two = column_two_position + row_two
    
    square_two_is_black = sum_two % 2 == 0
    # Compare the colors of the squares
    if square_one_is_black == square_two_is_black:
        return True
    
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine a chessboard. Notice how the color changes as you move across or down a row/column.
Consider a single square. The color of that square is determined by whether the column letter and row number are both 'even' or both 'odd'. If one is even and the other is odd, it's the other color.
Figure out if the first square's column and row are both 'even' or both 'odd'.
Figure out if the second square's column and row are both 'even' or both 'odd'.
If both squares have column and row that are both 'even' or both 'odd' then they are the same color, otherwise they are different colors.

Code Implementation

def check_chessboard_squares_color(square_one, square_two):

    column_one = ord(square_one[0])
    row_one = int(square_one[1])
    column_two = ord(square_two[0])
    row_two = int(square_two[1])

    # Check if both column and row are even or odd for the first square
    square_one_same_parity = (column_one % 2 == row_one % 2)

    # Check if both column and row are even or odd for the second square
    square_two_same_parity = (column_two % 2 == row_two % 2)

    # If both squares have the same parity, they have the same color
    if square_one_same_parity == square_two_same_parity:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Invalid input string length (not equal to 2)	Return false if the string length is not 2, as it's not a valid square representation.
Invalid input: Non-letter for the column (first character)	Return false if the first character is not a letter between a and h (or A and H), indicating an invalid column.
Invalid input: Non-digit for the row (second character)	Return false if the second character is not a digit between 1 and 8, indicating an invalid row.
Both squares are the same square	The problem implies distinct squares but if the same input is provided twice the function should return true (same color).
Lowercase vs. Uppercase Letters	Convert the column letter to lowercase to ensure case-insensitive comparison and calculation.
Adjacent squares on the same row	Test for correct color determination when columns are next to each other.
Adjacent squares on the same column	Test for correct color determination when rows are next to each other.
Squares at extreme corners (a1, h8, a8, h1)	Verify correctness for squares at the corners of the chessboard.