How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Anthropic.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Anthropic during technical interviews.

Compute matrix trace and support updates | Anthropic Coding Question

Compute matrix trace and support updates

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an n x n integer matrix M, implement a function trace (M) that returns the sum of its main diagonal. Follow-ups: (a) If you receive q point updates (i, j, val) changing M[i][j] to val, design a data structure to return the current trace after each update in O( 1) time; (b) Extend the function to also compute the anti-diagonal sum efficiently; (c) Discuss time and space complexities and edge cases (non-square input, large n).

Quick Answer: This question evaluates proficiency in matrix manipulation, incremental updates, and complexity analysis, specifically maintaining main-diagonal and anti-diagonal sums under point updates.

Part 1: Compute the main diagonal trace of a square matrix

Given an integer matrix `matrix`, return the sum of its main diagonal, from top-left to bottom-right. If the matrix is empty, return `0`. If the matrix is not square, return `None`.

Constraints

0 <= n <= 2000, where n is the number of rows
-10^9 <= matrix[i][j] <= 10^9
If the matrix is non-empty, it should be square for a valid input

Examples

Input: ([[1, 2], [3, 4]],)

Expected Output: 5

Explanation: The main diagonal is 1 and 4, so the sum is 5.

Input: ([[7]],)

Expected Output: 7

Explanation: A 1x1 matrix has exactly one diagonal element.

Input: ([],)

Expected Output: 0

Explanation: The empty matrix has diagonal sum 0.

Input: ([[2, -1, 4], [0, 3, 5], [7, 8, -6]],)

Expected Output: -1

Explanation: The main diagonal is 2, 3, -6, which sums to -1.

Input: ([[1, 2, 3], [4, 5, 6]],)

Expected Output: None

Explanation: The matrix has 2 rows but each row has length 3, so it is not square.

Solution

def solution(matrix):
    n = len(matrix)
    if n == 0:
        return 0

    for row in matrix:
        if len(row) != n:
            return None

    trace = 0
    for i in range(n):
        trace += matrix[i][i]
    return trace

Time complexity: O(n), where n is the number of rows. Space complexity: O(1).

Hints

The main diagonal consists of entries where the row index equals the column index.
Before summing, verify that every row has length `n`.

Part 2: Support O(1) trace queries after point updates

You are given an `n x n` integer matrix `matrix` and a list of point updates. Each update is a tuple `(i, j, val)` meaning `matrix[i][j]` becomes `val` using 0-based indexing. Return a list where the `k`-th value is the current main diagonal trace after applying the `k`-th update. Your solution should do O(1) work per update after initialization. If the initial matrix is not square, or any update index is out of bounds, return `None`.

Constraints

0 <= n <= 2000
0 <= q <= 200000, where q is the number of updates
-10^9 <= matrix[i][j], val <= 10^9
Updates use 0-based indices

Examples

Input: ([[1, 2], [3, 4]], [(0, 1, 10), (1, 1, 7), (0, 0, -1)])

Expected Output: [5, 8, 6]

Explanation: The first update is off-diagonal, so the trace stays 5. Then 4 becomes 7, making the trace 8. Finally 1 becomes -1, making the trace 6.

Input: ([[5]], [(0, 0, 3), (0, 0, 3)])

Expected Output: [3, 3]

Explanation: A 1x1 matrix's only cell is always on the main diagonal.

Input: ([], [])

Expected Output: []

Explanation: An empty matrix with no updates produces no trace outputs.

Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]], [])

Expected Output: []

Explanation: If there are no updates, the returned list is empty.

Input: ([[1, 2, 3], [4, 5, 6]], [(0, 0, 9)])

Expected Output: None

Explanation: The initial matrix is not square, so the input is invalid.

Solution

def solution(matrix, updates):
    n = len(matrix)
    if n == 0:
        return [] if len(updates) == 0 else None

    for row in matrix:
        if len(row) != n:
            return None

    trace = 0
    for i in range(n):
        trace += matrix[i][i]

    result = []
    for i, j, val in updates:
        if not (0 <= i < n and 0 <= j < n):
            return None

        old_value = matrix[i][j]
        if i == j:
            trace += val - old_value

        matrix[i][j] = val
        result.append(trace)

    return result

Time complexity: O(n + q). Space complexity: O(1) extra space, or O(q) including the output list.

Hints

Do not recompute the whole trace after each update. Store the current trace in a variable.
Only updates with `i == j` change the trace, and the change is `val - old_value`.

Part 3: Maintain both main-diagonal and anti-diagonal sums under updates

You are given an `n x n` integer matrix `matrix` and a list of point updates. Each update is a tuple `(i, j, val)` meaning `matrix[i][j] = val` with 0-based indexing. After every update, return both the main diagonal sum and the anti-diagonal sum as a pair `(main_sum, anti_sum)`. Your solution should do O(1) work per update after initialization. If the initial matrix is not square, or any update index is out of bounds, return `None`. Note: in an odd-sized matrix, the center cell belongs to both diagonals.

Constraints

0 <= n <= 2000
0 <= q <= 200000
-10^9 <= matrix[i][j], val <= 10^9
Updates use 0-based indices
For anti-diagonal positions, `i + j == n - 1`

Examples

Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]], [(0, 2, 10), (1, 1, 0), (2, 0, -1)])

Expected Output: [(15, 22), (10, 17), (10, 9)]

Explanation: The first update changes only the anti-diagonal. The second update hits the center, so it changes both sums. The third update changes only the anti-diagonal.

Input: ([[1, 2], [3, 4]], [(0, 0, 5), (0, 1, 7)])

Expected Output: [(9, 5), (9, 10)]

Explanation: In a 2x2 matrix, (0,0) is on the main diagonal only, while (0,1) is on the anti-diagonal only.

Input: ([[4]], [(0, 0, -2)])

Expected Output: [(-2, -2)]

Explanation: In a 1x1 matrix, the single cell belongs to both diagonals.

Input: ([], [])

Expected Output: []

Explanation: An empty matrix with no updates yields an empty result.

Input: ([[1, 2, 3], [4, 5, 6]], [(0, 1, 9)])

Expected Output: None

Explanation: The matrix is not square, so the input is invalid.

Solution

def solution(matrix, updates):
    n = len(matrix)
    if n == 0:
        return [] if len(updates) == 0 else None

    for row in matrix:
        if len(row) != n:
            return None

    main_sum = 0
    anti_sum = 0
    for i in range(n):
        main_sum += matrix[i][i]
        anti_sum += matrix[i][n - 1 - i]

    result = []
    for i, j, val in updates:
        if not (0 <= i < n and 0 <= j < n):
            return None

        old_value = matrix[i][j]

        if i == j:
            main_sum += val - old_value
        if i + j == n - 1:
            anti_sum += val - old_value

        matrix[i][j] = val
        result.append((main_sum, anti_sum))

    return result

Time complexity: O(n + q). Space complexity: O(1) extra space, or O(q) including the output list.

Hints

Keep two running sums: one for the main diagonal and one for the anti-diagonal.
When `n` is odd, the center cell satisfies both `i == j` and `i + j == n - 1`, so one update may affect both sums.

Quick Overview

This question evaluates proficiency in matrix manipulation, incremental updates, and complexity analysis, specifically maintaining main-diagonal and anti-diagonal sums under point updates.