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 Take-home Project rounds at LinkedIn.

What role is this question designed for?

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

Process Mutable Matrix Sum Queries | LinkedIn Coding Question

Process Mutable Matrix Sum Queries

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given a 2D integer matrix and a list of queries. There are two query types: - `set r c v`: update the value at row `r` and column `c` to `v` - `get r1 r2 c1 c2`: return the sum of all elements in the submatrix formed by rows in the half-open range `[r1, r2)` and columns in the half-open range `[c1, c2)` Use 0-based indexing. The input format is: 1. An integer `rows` 2. An integer `cols` 3. `rows` lines, each containing `cols` integers for the matrix 4. An integer `q` for the number of queries 5. `q` query lines, each in one of the two formats above For every `get` query, output the computed sum on its own line. Example input: - `rows = 2` - `cols = 3` - matrix: - `[1, 2, 3]` - `[4, 5, 6]` - `q = 5` - queries: - `get 0 2 1 3` - `set 0 1 10` - `get 0 2 1 3` - `set 0 0 -3` - `get 0 1 0 2` Example output: - `16` - `24` - `7` Your task is to implement this query processor efficiently.

Quick Answer: This question evaluates a candidate's understanding of efficient mutable 2D range-query and point-update data structures and algorithms for computing submatrix sums under dynamic updates, and falls under the Coding & Algorithms domain.

You are given a 2D integer matrix and a list of queries. Each query is one of two types: 'set r c v' updates the value at row r and column c to v, and 'get r1 r2 c1 c2' asks for the sum of all elements in the submatrix with rows in the half-open range [r1, r2) and columns in the half-open range [c1, c2). Use 0-based indexing. Because there may be many updates and sum requests, your solution should process queries efficiently. In this function version of the problem, return the answers to all 'get' queries as a list in the order they appear.

Constraints

1 <= rows, cols <= 500
1 <= rows * cols <= 100000
0 <= len(queries) <= 200000
-10^9 <= matrix[r][c], v <= 10^9
For 'set' queries: 0 <= r < rows and 0 <= c < cols
For 'get' queries: 0 <= r1 <= r2 <= rows and 0 <= c1 <= c2 <= cols

Examples

Input: ([[1, 2, 3], [4, 5, 6]], ['get 0 2 1 3', 'set 0 1 10', 'get 0 2 1 3', 'set 0 0 -3', 'get 0 1 0 2'])

Expected Output: [16, 24, 7]

Explanation: The first query sums columns 1..2 across both rows: 2 + 3 + 5 + 6 = 16. After setting matrix[0][1] = 10, the same rectangle sums to 10 + 3 + 5 + 6 = 24. After setting matrix[0][0] = -3, the final query asks for the first row, first two columns: -3 + 10 = 7.

Input: ([[5]], ['get 0 1 0 1', 'set 0 0 -2', 'get 0 1 0 1', 'get 0 0 0 1'])

Expected Output: [5, -2, 0]

Explanation: This checks a single-cell matrix and an empty row range. The final query has r1 == r2, so the submatrix is empty and its sum is 0.

Input: ([[1, 1, 1], [1, 1, 1], [1, 1, 1]], ['get 0 3 0 3', 'set 1 1 5', 'get 1 3 1 3', 'set 2 0 4', 'get 2 3 0 2', 'get 0 2 0 2'])

Expected Output: [9, 8, 5, 8]

Explanation: The whole matrix initially sums to 9. After setting the center to 5, the bottom-right 2x2 block sums to 5 + 1 + 1 + 1 = 8. After setting matrix[2][0] = 4, row 2 columns 0..1 sum to 4 + 1 = 5. The top-left 2x2 block then sums to 1 + 1 + 1 + 5 = 8.

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

Expected Output: [3, -1, 9, 0]

Explanation: The whole matrix sums to 3. The second query looks only at row 0, columns 1..2: 2 + (-3) = -1. After updating matrix[1][1] to 7, column 1 across both rows sums to 2 + 7 = 9. The final query has an empty column range, so its sum is 0.

Hints

A normal 2D prefix sum makes range-sum queries fast, but a single update would force you to rebuild too much information. Think about a data structure that supports both point updates and prefix sums efficiently in 2D.
If you can quickly compute the sum of the rectangle [0, r) x [0, c), then any query rectangle can be answered with inclusion-exclusion.

Quick Overview

This question evaluates a candidate's understanding of efficient mutable 2D range-query and point-update data structures and algorithms for computing submatrix sums under dynamic updates, and falls under the Coding & Algorithms domain.