Katkat
Back

Implement Matrix Move and Logger

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests in-place array manipulation for submatrix coordinate transformations and the implementation of a thread-safe, time-windowed rate limiter using a sliding window approach.

Part 1: Matrix Shift

You are given an N x N matrix of integers and a command to move a submatrix defined by top-left (r1, c1) and bottom-right (r2, c2) by a displacement vector (dr, dc). If the move results in the submatrix overlapping with its previous position, implement the shift such that the original data is preserved correctly. Assume the target area remains within the N x N bounds.

Implement the function: void shiftSubmatrix(vector>& matrix, int r1, int c1, int r2, int c2, int dr, int dc)

Part 2: Time-Window Logger

Design a rate-limiting logger that records access timestamps. The logger must provide a method shouldLog(int timestamp) that returns true if the message should be logged, and false otherwise. A message should only be logged if it has not been logged in the last 10 seconds. You must ensure shouldLog operates in O(1) average time and maintains memory proportional only to the messages stored within the 10-second window.

Example

// Matrix Shift
Matrix: [[1, 2], [3, 4]], r1=0, c1=0, r2=0, c2=0, dr=1, dc=1
Result: [[1, 2], [3, 1]] // Element (0,0) moved to (1,1)

// Logger
logger.shouldLog(1);  // returns true
logger.shouldLog(11); // returns true
logger.shouldLog(11); // returns false

Hints

Hint 1

For the matrix shift, determine the order of iteration (top-to-bottom or bottom-to-top) based on the sign of the displacement vector to avoid overwriting elements before they are moved.

Hint 2

For the logger, use a Hash Map to store the last timestamp each unique message ID was processed, allowing O(1) lookup.

Hint 3

To optimize memory, periodically purge entries from the Hash Map that are older than the 10-second threshold.

Follow-up questions

  • How would you handle matrix shifts if the destination area overlaps with the source area in a way that requires an intermediate buffer?
  • How would you modify the logger to handle a high-concurrency environment where multiple threads call shouldLog simultaneously?
  • If the logger needs to support a 'burst' capacity (e.g., 5 logs every 10 seconds), what data structure would you use to replace the simple timestamp store?