ZS Associates

Past interview problems (now retired)

Round 1 problem—reverse words algorithm
Devise an efficient algorithm to reverse a string word by word. For example, given the string “Most sentences don’t make sense backwards” the algorithm would return “backwards sense make don’t sentences Most”.

Use pseudo-code, diagrams, or any other tools you think would be helpful to describe your algorithm. Be sure to list any assumptions you make about the task.

Round 2 problem—Sparse matrix data structure
A sparse matrix is a two-dimensional grid of numbers where a very small percentage of the numbers are non-zero. A typical sparse matrix might be on the order of 100,000×200,000 and be one percent filled. The following 4×4 matrix would be considered sparse because only one of the cells contains a non-zero value:

For our purposes, a good sparse matrix data structure will meet at least the following requirements:

1. It will handle any M x N matrix where M and N are determined dynamically at runtime, and it should make no assumptions about the matrix size.
2. It will be just as effective for a 100,000×100,000 matrix as for a 100×100 matrix.
3. It efficiently stores the matrix. In other words, the size of the data structure should be proportional to the number of non-zero values in the cells, not to the number of total cells.
4. The addition of two matrices should be as efficient as possible. The speed of this algorithm should be proportional to the number of non-zero values in the cells, not to the number of total cells. Note that to add two matrices, A and B, you simply add up all of their corresponding cells: C(i, j) = A(i, j) + B(i, j). For example:

   0000 0000 0500 0001

   +

   0010 0000 0000 0001

   =

   0010 0000 0500 0002

Design a sparse matrix data structure that meets these requirements. Also, design an algorithm that uses your data structure to perform matrix addition. Feel free to describe your data structure and algorithm in pseudo-code or the computer language of your choice. Draw diagrams with annotations where needed to make your design clear.