2-D Matrix Transpose with Memory-Layout Discussion

Transpose an `n x n` or general 2-D matrix, then discuss row-major vs column-major layout, cache locality, in-place constraints, and large-matrix performance. This appears in Linux / System Software-style rounds. Requirements Implement matrix transpose for a 2-D matrix. Possible versions: vector<vector<int>> transpose(const vector<vector<int>>& a); void transpose_square_in_place(vector<vector<int>>& a); Base requirements: Return a[j][i] at output position [i][j]. Handle empty matrix and non-square matrix for the out-of-place version. For square matrices, support an in-place version by swapping only i < j. Discussion follow-ups: Row-major vs column-major layout. Cache friendliness when reading rows and writing columns. Why an out-of-place transpose may have poor write locality. How to block / tile a large matrix transpose. In-place transpose constraints for non-square matrices. Notes The simple out-of-place solution is O(R x C) time and O(R x C) extra space. The square in-place version is O(N^2) time and O(1) extra space. For large matrices, the core performance issue is locality. In row-major memory, reading a[i][j] by increasing j is contiguous, but writing out[j][i] jumps across rows. A blocked transpose improves locality: for block_i in range(0, R, B): for block_j in range(0, C, B): transpose the B x B tile Pick B so a tile fits cache. The interviewer may care more about this reasoning than about the basic loop. Preparation Write both out-of-place and square in-place versions in C++. Be ready to explain why vector<vector<T>> is not the same as one contiguous flat array. Practice the flat-array index formula: row-major idx = r * cols + c.