CS-OA cs-vo Faang

Capital One OA – Capital One 面试真题 – codesignal

Capital One 近期发放OA中,仍然是常规的codesignal的套路,限时70分钟做4道原创题,本次分享的是其中2道题。

Code Writing

Given a square matrix n x n (where n is guaranteed to be odd) that contains only the values 0, 1, and 2, you are allowed in one operation to change the number in any cell of the matrix to a different number (0, 1, or 2). Your task is to compute the minimum number of cells that need to be changed to write the letter 'Y' on the matrix.

The letter 'Y' is correctly represented on the matrix if and only if:

  • All numbers on the diagonals starting from the upper-left and upper-right corners down to the center of the matrix, as well as the numbers stretching down vertically from the center of the matrix, are equal.
  • All other numbers that are not part of the 'Y' should be equal and be different from the numbers that make up the 'Y'.

Note: For a square matrix of size n x n, there are exactly six possible ways of writing 'Y' on the matrix. The cells that make up the 'Y' letter and the cells that make up its background can be equal to 0 and 1, 0 and 2, 1 and 0, 1 and 2, 2 and 0, and 2 and 1, respectively.

Below, you can see an example of the letter 'Y' for a 5 x 5 matrix:

You are given a matrix of size n x n (where n is odd), containing only the integers 0, 1, and 2. The goal is to transform the matrix so that it forms the letter 'Y' using the integer 2, while the integer 0 represents the background. You may change the values of any cell, but the objective is to minimize the number of cells changed.

Problem Example

For a matrix of size n = 5, the letter 'Y' can be formed as shown in the example. The cells used to form the 'Y' are set to 2, and the background cells are set to 0. Here is an example of how the matrix should look:

2 0 0 0 2
0 2 0 2 0
0 0 2 0 0
0 0 2 0 0
0 0 2 0 0

Task Constraints

  • The matrix size n varies from 3 to 99.
  • Each cell of the matrix contains only the values 0, 1, or 2.

Function Input/Output

  • Input: An n x n matrix as a list of lists.
  • Output: The minimum number of changes needed to form the letter 'Y'.

Python 3 Syntax Tips

This will help you to print a message to the console or perform basic operations in Python.

# Prints help message to the console
# Returns a string
def helloWorld(name):
print("This prints to the console when you Run the code")
return "Hello, " + name

Codewriting

You are given operations, an array containing the following two types of operations:

  • [0, a, b] - Create and save a rectangle of size a x b.
  • [1, a, b] - Answer the question: "Could a box of size a x b fit inside each of the earlier saved rectangles?" It is possible to rotate the rectangles by 90 degrees; i.e., a rectangle of dimensions a x b can be rotated so that its dimensions are b x a.

Your task is to return an array of booleans, representing the answers to the second type of operation, in the order they appear.

Note: The operations should proceed iteratively, so when operations[i] is executed, only the results of the previous operations 0, 1, ..., i-1 are available.

Example

  • For operations = [[1, 1, 1]], the output should be solution(operations) = [true]. There are no rectangles, so return true because there were no rectangles that the box was unable to fit inside.
  • For operations = [[0, 100000, 100000]], the output should be solution(operations) = []. The rectangle of size 105×10510^5 \times 10^5105×105 was successfully created. Since this type of operation returns nothing and there are no other operations, the answer is an empty array.
  • For operations = [[0, 3, 3], [0, 5, 2], [1, 3, 2], [1, 2, 4]], the output should be:
    • A 3 x 3 rectangle is added;
    • A 5 x 2 rectangle is added;
    • We need to check if it's possible to store a box of a size 3 x 2 inside each of the rectangles from operations 1 and 2.
      • A box of a size 3 x 2 can be stored in the 3 x 3 rectangle as-is.
      • A box of a size 3 x 2 can be stored in the 5 x 2 rectangle as-is.
      • The box fits inside both rectangles, so add true to the result.
    • We need to check if it's possible to store a box of a size 2 x 4 inside each of the rectangles from operations 1 and 2.
      • A box of a size 2 x 4 can be stored in the 5 x 2 rectangle as-is, but not in the 3 x 3.
      • Thus, add false to the result.

The final result for the operations would be [true, false].

We successfully tackled these 4 questions in just over 20 minutes. If you require assistance with completing Online Assessments (OA), please do not hesitate to contact us. Additionally, we offer services such as interview proxying and interview coaching. Our goal is to provide you with comprehensive support to ensure you excel in your career endeavors.

如果您对自己完成这4题没有信心,可以联系我们,我们将确保您的算法题获得满分。同时我们还提供面试代面,面试辅助等服务。详情请查看

Leave a Reply

Your email address will not be published. Required fields are marked *