A strong answer
In C, C++, Java, NumPy's default and most languages, a two-dimensional array is stored row-major: row 0's elements side by side, then row 1's, and so on. Element [i][j] of an n-column matrix of 8-byte doubles is at base + (i × n + j) × 8.
Memory reaches the processor in 64-byte cache lines, eight doubles at a time. Walking along a row reads consecutive addresses, so each line serves eight reads, and the hardware prefetcher spots the stream and fetches lines ahead. Walking down a column jumps n × 8 bytes per read: 8,000 bytes for a 1,000-column matrix. Each read lands on a different line and uses 8 of its 64 bytes, and once the matrix is bigger than the cache, the line is usually evicted before the loop comes back for its neighbors. The arithmetic is identical; the number of trips to memory is up to eight times higher, and the prefetcher helps less.
The fix is to make the inner loop walk the contiguous dimension, by swapping the loops. When both directions are needed, as in matrix multiplication, process the matrix in tiles small enough to stay in cache. To verify, measure both versions on a matrix larger than the last-level cache and on a small one, and use a profiler such as perf stat to compare cache-miss counts.
What the interviewer is listening for
- Row-major layout and the address formula.
- Cache lines, and the fraction of each line that each loop actually uses.
- That the effect depends on the matrix being larger than the cache.
- A fix, and a way to confirm the cause with measurements.
Common mistakes
- Saying column access is slower "because of more calculations". The index arithmetic is the same.
- Assuming every language is row-major. Fortran, MATLAB and Julia store matrices column by column, so the fast loop order is reversed.
- Quoting a fixed speedup. It depends on the matrix size, element size and machine.