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

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.

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.

Loading coding console...

Quick Overview

Process Mutable Matrix Sum Queries

Constraints

Examples

Hints