I applied online and received an email from a recruiter. She then scheduled me for a phone interview with a Google Engineer. The interview was completely technical. The question involved creating three vectors to represent a sparse matrix. The engineer was quite helpful. The hardest part of the interview was thinking, talking, and coding simultaneously.

Sparse matrices are usually stored by only storing the non-zero values. But, there is no single standard format for doing this. One such format is called Compressed Sparse Column (CSC). Example: The following matrix is stored in CSC format using three arrays, vals, rows, and cols. /0 1 2 3 4
| a 0 0 0 0 | 0 | 0 c f 0 0 | 1 | 0 0 0 0 h | 2 | b d g 0 i | 3 | 0 0 0 0 0 | 4 | 0 e 0 0 0 | 5 \ / vals = [a, b, c, d, e, f, g, h, i] ← double values rows = [0, 3, 1, 3, 5, 1, 3, 2, 3] cols = [0, 2, 5, 7, 7] ← position in the vals array (think of it as pointers into “vals”) length of the cols array == the number of columns in the matrix Generate this representation of the matrix from a sequence of triples (row, col, val). Example: (1, 1, c), (3, 4, i), ...