Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Each non-empty item in the sheet is a triplet (row, col, data) and this is stored in an array.
This is not optimal for traversing/access but it is a solution.
These triplets can be extended to contain "ponters" (aka indexes in the array) to the next/previous/upper/lower cells as well.
And we can have a supporting array to the first cell of columns/rows.
If the buffer is of fixed size, we will need to know the maximum capacity. For that we will need to know the maximum number of rows and the maximum number of columns. The maximum capacity then is the number of rows times the number of columns. The buffer will need to be divided in such a way that it accommodates for all the cells in the excel sheet and all elements are easily stored from the excel sheet, and mapped to it. Each row has a fixed amount of cells, which are the columns. So the buffer can be divided into a set of rows of y columns, with y the maximum number of columns. So the first y indices of the buffer correspond to row 1 column y entries. Similary, for the second and the third row. Hence, the row of the entry from the buffer can be mapped by integer division of the index from y. The column number can be mapped with modulus of y +1 (buffer starts from zero). When an entry has to be stored, it can be stored at the position (y*row)+column, where y is max column.
In a 2-d array that is row major, you access an element by matrix[i][j]. This access refers to the ith row and jth column and gives you the element where the ith row and jth column intersect. Take a matrix with two rows and three columns. Attach the second row to the end of the first row. Now you have an array of six columns. To access ith row and jth element on ith row: i*3 + j where 0<=i<=1 and 0<=j<=2
If the content of excel sheet, i.e number of cells used, doesn't increase or decrease..then..to minimize the amount of buffer (proportional to number of used cells)
we can use one extra array for keeping the index of each row's beginning (index into the one dimensional buffer)
then a[i][j] = data[arr[i]+j]
Obviously the format is CSV
The data is stored in flat file. The data in a particular columns is delimited by space or tab. The rows/records are separated by newline. Let say we have n columns in a record/row. To access the particular data(x,y) we can count x newline('\n') and y-1 spaces and read the data.
We can decide the method according to the feature of the matrix.
- Gabriel October 17, 2012If the matrix is a sparse matrix, we can use some compression storage methods, or etc.