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.

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.

Hints

  1. 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.
  2. 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.

Loading coding console...