Facebook Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

a datastructure is driven by the operations one wants to perform on it. The question screams for clarification of this operations.

Since it's sparse, a pure array seems not the solution although in practice it depends on the expected size of the matrix (average, max) and the numbers of matrices to be stored.
For example if we have to deal with 3 sparse matrices of size10x10 with average 2 elements being not 0 in all cases I can think of the best representation is a two dimensional array. If we need to keep tenths or hunderts of thousands of such 10x10 matrices in memory or if a single matrix has large dimensions, say 100'000 x 100'000 this representation may not be good anymore.

Thinking about the operations one potentially may want to perform on such matrices like addition and multiplication we do not require random access to single elements but sequential access for addition and random access of a whole row / column where the elements of that row / column are accessed sequentially.

In case of addition we need m*n operations anyway, be it to add the elements or to initialize the result with 0.

For multiplication the thing is different. m x n * n x p matrix will result in a m x p matrix. So, if we have to trie to access every element we end up with O(m x n + n x p) compared to optimal if it is sparse that is O(n x p) assuming, for simplicity, the number of elements in both matrices that are not 0 is smaller than n x p.

It seems a linked list per row and per column may be a good choice for addition and multiplication. This would store the value and column-index for a row, or value and row-index for a column.

It is slow to insert/delete and random read single elments. As well attention to construction needs to be payed (how to fill the data structure initially). If we want to speed up random access (read) we could maintain a hashmap on top. If insert/delete of single elements needs optimization while still providing reasonable access to all elements of a column (in row order) and vice versa for a row the linked lists could be replaced by balanced search trees.

- Chris November 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good explanation, but, I think, you could still use the same approach with linked lists for addition as well - that gives you better performance, than m*n. And the result will be a spare matrix as well: for result row i you'll have a new linked list of length A[i].Length (length of linked list for i row in matrix A) + B[i].Length (length of linked list for i row in matrix B) as max.

- Alex M. February 08, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think a sorted hash map is the best option with key being the position of element in row-order or column-order format and value being the value of the element.
We can traverse the hash table in a sorted manner.

- kevseb1993 November 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SparseMatrix {
	class CF { // column Family
		int colSeq;
		String colName;
		String dataType; // T
		String data; // Object data

		// Date timeStamp
		// int versionId;

		CF nextColumn; //skip to next not null column
	}
	private Map<Long, CF> matrix;
}

- Ashis Kumar Chanda November 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Map<RowNumber, Map<CF.ColSeQ, CF>> matrix;

- Ashis Kumar Chanda November 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I decided to go with 2 arrays of linked list per matrix: one for rows and one for columns.
I tested the code and it seems to work. Posting only the interesting part. You can devise the rest.
This is C#.

static Matrix dotProduct(Matrix a, Matrix b)
        {
            if (a.nCl != b.nRows)
                throw new ArgumentException();
            Matrix res = new Matrix(a.nRows, b.nCl);

            for (int r = 0; r < a.nRows; r++)
            {
                for (int c = 0; c < b.nCl; c++)
                {
                    var row = a.rows[r];
                    var cl = b.columns[c];
                    if (row == null || cl == null )
                        continue;
                    var rowIt = row.GetEnumerator();
                    var clIt = cl.GetEnumerator();
                    var rNext = rowIt.MoveNext() ? rowIt.Current : null;
                    var cNext = clIt.MoveNext() ? clIt.Current : null;
                    int x = 0;
                    while (rNext != null && cNext != null)
                    {
                        if (rNext.cl == cNext.row)
                        {
                            x += rNext.v*cNext.v;
                            rNext = rowIt.MoveNext() ? rowIt.Current : null;
                            cNext = clIt.MoveNext() ? clIt.Current : null;
                        }
                        else if (rNext.cl < cNext.row)
                        {
                            rNext = rowIt.MoveNext() ? rowIt.Current : null;
                        }
                        else
                        {
                            cNext = clIt.MoveNext() ? clIt.Current : null;
                        }
                    }
                    if (x != 0)
                    {
                        if (res.rows[r] == null) res.rows[r] = new LinkedList<El>();
                        if (res.columns[c] == null) res.columns[c] = new LinkedList<El>();
                        var el = new El()
                        {
                            cl = c,
                            row = r,
                            v = x
                        };
                        res.rows[r].AddLast(el);
                        res.columns[c].AddLast(el);
                    }
                }
            }
            return res;
        }

- M42 November 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class SparseMatrix:
	def __init__(self, matrix):
		self.num_rows = len(matrix)
		self.num_columns = len(matrix[0])
		self.values = dict()
		for i in self.num_rows:
			for j in self.num_columns:
				self.values[(i,j)] = matrix[i][j]
	
	def shape(self):
		return (self.num_rows, self.num_columns)
	
	def dot(self, other):
		if self.shape() != other.shape():
			raise Exception("Matrices must have same shape")
		ans = 0
		for (r, c) in self.values:
			if (r, c) in other.values:
				ans += self.values[(r,c)]*other.values[(r,c)]
		return ans

- anon November 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pseudo code:
1. think the matrix as 1-d array, index = i*rows + j;
2. create map<Integer, Integer> for each matrix, for non zero value, store in map, map.put(index, value)
3. calculation, get value from each map, do calculation only for data with value.

- hank November 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For these types of questions, it's usually safe to assume that sparse matrices implies few N entries relative to very large dimensionality M. For example, N=100 values in sparse matrix size M=2^50, which implies that direct array storage is completely out of the question.

The related (separate) question involves dot product computation (a linear operation), which gives some hints to what the running order should be. Regardless, the answer to this question - as it stands - is really any structure with space growth that tracks the number of loaded entries independently of the matrix dimensions.

- ttsou December 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use one of the following
1. Table representation
total#rows total#columns total#nonZeroValues // header row first row of table
//next rows below the actual values
// if a row as two values then there will be two rows here

2. LinkedList representation
// this is bit complex, than first one
//it has three nodes HeaderNode, RowNode and ColumnNode
//HeaderNode -> Total#rows,Total#column, pointer to next row
//RowNode -> Row#,pointerToNextRow,pointerToNextColumn
//ColumnNode -> Column#,Value, pointerToNextColumn(if a row as more than one nonZero values)

- Raj January 20, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More