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 Onsite rounds at Microsoft.

What role is this question designed for?

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

Implement Matrix Move and Logger | Microsoft Coding Question

Quick Overview

This question evaluates array manipulation and in-place algorithm design for handling overlapping submatrix moves, along with data-structure and time-window reasoning for implementing a rate-limited logger that supports O(1)-average-time checks and bounded memory.

Implement Matrix Move and Logger

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement the following two coding tasks. 1. **Move a submatrix in place.** You are given an `m x n` matrix, a source rectangle defined by its top-left corner `(r1, c1)` and bottom-right corner `(r2, c2)` inclusive, and a destination top-left corner `(nr, nc)`. The destination rectangle has the same height and width as the source rectangle. Update the original matrix **in place** so that the destination rectangle contains exactly the original values from the source rectangle. The source and destination rectangles may overlap, and the final destination contents must match what you would get if the source rectangle had been copied before any writes occurred. Use only `O(1)` extra space besides a few temporary variables. 2. **Implement a rate-limited logger.** Design a `Logger` class with a configurable time window `windowSeconds` and a method `shouldAllow(key, timestamp) -> bool`. A request for `key` should be allowed only if the same key has not been allowed during the previous `windowSeconds` seconds. Assume timestamps are non-decreasing. Your implementation should support high call volume with `O(1)` average-time checks and should remove expired state so memory usage does not grow without bound.

Quick Answer: This question evaluates array manipulation and in-place algorithm design for handling overlapping submatrix moves, along with data-structure and time-window reasoning for implementing a rate-limited logger that supports O(1)-average-time checks and bounded memory.

Part 1: Move a Submatrix In Place

You are given a 2D integer matrix and two rectangles of the same size. The source rectangle is defined by its top-left corner `(r1, c1)` and bottom-right corner `(r2, c2)`, inclusive. The destination rectangle is defined by its top-left corner `(nr, nc)` and has the same height and width as the source rectangle. Update the original matrix in place so that the destination rectangle contains exactly the original values from the source rectangle. The source and destination rectangles may overlap. The final destination must match what you would get if the source rectangle had been copied to a temporary buffer before any writes happened. For easier testing, return the modified matrix after performing the move. All indices are 0-based.

Constraints

1 <= m, n <= 500
0 <= r1 <= r2 < m
0 <= c1 <= c2 < n
Let height = r2 - r1 + 1 and width = c2 - c1 + 1
0 <= nr and nr + height - 1 < m
0 <= nc and nc + width - 1 < n
Matrix values fit in a 32-bit signed integer
Use only O(1) extra space besides a few temporary variables

Examples

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

Expected Output: [[1, 2, 3, 4], [5, 6, 1, 2], [9, 10, 5, 6]]

Explanation: A 2x2 block is copied to a non-overlapping destination.

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

Expected Output: [[1, 2, 3], [4, 1, 2], [7, 4, 5]]

Explanation: The destination overlaps the source and is down-right, so reverse row and column traversal is needed.

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

Expected Output: [[5, 6, 3], [8, 9, 6], [7, 8, 9]]

Explanation: The destination overlaps the source and is up-left, so normal top-left traversal is safe.

Input: ([[42]], 0, 0, 0, 0, 0, 0)

Expected Output: [[42]]

Explanation: Edge case: a single-cell matrix moved onto itself stays unchanged.

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

Expected Output: [[2, 3, 4, 4, 5]]

Explanation: A 1-row submatrix shifts left with overlap, so columns must be processed left to right.

Hints

Think of this as a 2D version of `memmove`: if the destination is below or to the right of the source, copying in the usual top-left to bottom-right order can destroy values you still need to read.
Choose row order based on vertical shift and column order based on horizontal shift. For example, if the destination starts lower than the source, process rows from bottom to top.

Part 2: Implement a Rate-Limited Logger

Design the behavior of a rate-limited logger. You are given a time window `window_seconds`. A request for `key` at time `timestamp` should be allowed only if the same key has not been allowed during the previous `window_seconds` seconds. More precisely, if a key was last allowed at time `t`, then it may be allowed again only at time `t + window_seconds` or later. Timestamps are non-decreasing. Your solution should support high call volume with O(1) average-time checks and should remove expired state so memory usage does not grow without bound. For this function-based version, you are given all logger calls at once. Return the result of `shouldAllow(key, timestamp)` for each call in order.

Constraints

1 <= window_seconds <= 10^9
0 <= len(keys) == len(timestamps) <= 2 * 10^5
0 <= timestamps[i] <= 10^9
timestamps is non-decreasing
Each key is a non-empty string

Examples

Input: (10, ['foo', 'bar', 'foo', 'foo', 'bar'], [1, 2, 3, 11, 12])

Expected Output: [True, True, False, True, True]

Explanation: A key allowed at time 1 can be allowed again at time 11 when the 10-second window has fully passed.

Input: (3, ['a', 'a', 'a', 'a'], [1, 3, 4, 7])

Expected Output: [True, False, True, True]

Explanation: At time 3 the previous allow at time 1 is still within the last 3 seconds, but time 4 is allowed because 4 - 1 = 3.

Input: (5, [], [])

Expected Output: []

Explanation: Edge case: no logger calls.

Input: (2, ['x', 'y', 'x', 'y', 'x'], [1, 1, 2, 3, 4])

Expected Output: [True, True, False, True, True]

Explanation: Different keys are tracked independently, and timestamps may repeat as long as they do not decrease.

Input: (1, ['k', 'k', 'k'], [5, 5, 6])

Expected Output: [True, False, True]

Explanation: Edge case: repeated requests at the exact same timestamp are blocked, but the next second is allowed for a 1-second window.

Hints

A hash map can tell you the most recent allowed timestamp for each key.
Because timestamps never go backward, expired allowed entries can be removed from the front of a queue.

Quick Overview