## Problem You are given an `(m+1) x (n+1)` matrix where the last row contains the XOR of each column and the last column contains the XOR of each row. One cell in the original `m x n` region is corrupted (flipped bits). Find the coordinates of the corrupted cell and restore its correct value. ```python def find_and_fix_corrupted( matrix: list[list[int]] ) -> tuple[int, int, int]: """Return (row, col, corrected_value).""" ... ``` ``` Original 2x2 (with checksums as 3x3): 1 2 3 9 1 9 3 4 5 1 5 12 Column 1 checksum: 9 XOR 5 = 12, expected 7 -> mismatch -> col=1 Row 0 checksum: 1 XOR 9 = 10, expected 3 -> mismatch -> row=0 Corrected value: 9 XOR 10 XOR 3 = 2 Output: (0, 1, 2) ``` ## Follow-ups 1. Prove that XOR of a row and its checksum equals 0 when uncorrupted. How does corruption change this? 2. What if two cells are corrupted? Can you still detect and fix them with this scheme? 3. How does this relate to RAID-5 parity? Describe the analogy. 4. Extend to 3D: a cube with checksum planes on all three faces. How do you locate a single corrupted voxel?

InterviewDB Experience

Encoded Matrix: Decode a 2D Matrix Encoded with Row and Column XOR Checksums

Onsite

Interview Experience

Problem You are given an (m+1) x (n+1) matrix where the last row contains the XOR of each column and the last column contains the XOR of each row. One cell in the original m x n region is corrupted (flipped bits). Find the coordinates of the corrupted cell and restore its correct value. Follow-ups Prove that XOR of a row and its checksum equals 0 when uncorrupted. How does corruption change this? What if two cells are corrupted? Can you still detect and fix them with this scheme? How does this r…

Full Details

🔒

Unlock all Instacart questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a candidate experience report from a instacart interview during the onsite round.

It covers the following topics: Bit Manipulation, Coding, Onsite, Matrix .

Topics

Bit Manipulation Coding Onsite Matrix

Encoded Matrix: Decode a 2D Matrix Encoded with Row and Column XOR Checksums

Interview Experience

Full Details

About This Question

Topics

More Instacart Interview Questions