Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
It's more effective to keep values in a sorted List<Pair<int x, List<Pair<int y, value>>>>. That way you don't have to iterate through N*M elements. That's the whole point of the question: the input matrix is huge but spare. So, you need to come up with something that allows you not to iterate through all N*M elements.
This is an extension of the simpler problem of computing a dot product on two sparse arrays. We do not compute any multiples with zeros.
Given 'N' and 'M' entries in the sparse matrices A and B. We can brute force the filled entries - still substantially better than brute forcing the full array dimensions - to reach O(n*m) performance on time. However, matrix multiplication, as is the simpler dot product, is a ordered process that provides improvement.
So provide ordering operations on both arrays, prioritize horizontal ordering on A and vertical on B, as well as an A-B compare that serves as a index transformation to sort and 'flatten' the matrices into a linear operation. That way we can iterate unidirectionally in a single pass for both matrices.
Final result is O(n) for space. Time is O(n) if inputs are sorted or O(nlogn) if inputs are not sorted. In both cases 'n' is the number of filled entries - dimensions of the matrices is irrelevant.
/*
* 'Dot Product on Sprase Matrices'
*
* O(n) time and space complexity for multuply not including sorting where 'n'
* is number of used entries in sparse matrices A or B. Actual matrix
* dimensions are irrelevant (square, 1-d array, etc.) and have no effect on
* the algorithm or running time.
*
* If input arrays are not sorted then running time extends to O(nlogn) where,
* again, 'n' is the number of elements in the sparse array irrespective of the
* matrix dimensions.
*/
import java.util.Arrays;
import java.util.Comparator;
public class Value {
public int val, x, y;
public Value(int x, int y, int val)
{
this.x = x;
this.y = y;
this.val = val;
}
public String toString()
{
return ("(" + x + ", " + y + ") = " + val);
}
}
public class DotProduct {
private class ComparatorA implements Comparator<Value>
{
public int compare(Value a, Value b)
{
if (a.y < b.y)
return -1;
else if (a.y == b.y && a.x == b.x)
return 0;
else if (a.y == b.y && a.x < b.x)
return -1;
else
return 1;
}
}
private class ComparatorB implements Comparator<Value>
{
public int compare(Value a, Value b)
{
if (a.x < b.x)
return -1;
else if (a.x == b.x && a.y == b.y)
return 0;
else if (a.x == b.x && a.y < b.y)
return -1;
else
return 1;
}
}
private int compareIndexAB(Value a, Value b)
{
if (a.y < b.x)
return -1;
else if (a.y == b.x && a.x == b.y)
return 0;
else if (a.y == b.x && a.x < b.y)
return -1;
else
return 1;
}
public Value[] compute(Value[] A, Value[] B)
{
Arrays.sort(A, new ComparatorA());
Arrays.sort(B, new ComparatorB());
int max = A.length < B.length ? A.length : B.length;
Value[] C = new Value[max];
int sum;
int c = 0;
int b = 0;
boolean nonzero = false; // For empty empty return handling
for (int a = 0; a < A.length; a++) {
while (b < B.length && compareIndexAB(A[a], B[b]) > 0) {
b++;
}
if (b >= B.length)
break;
if (compareIndexAB(A[a], B[b]) == 0) {
nonzero = true;
int prod = A[a].val * B[b].val;
if (C[c] == null)
C[c] = new Value(A[a].y, 0, prod);
else if (C[c].x == A[a].y)
C[c].val += prod;
else
C[++c] = new Value(A[a].y, 0, prod);
}
}
if (!nonzero)
return new Value[0];
Value[] resizeC = new Value[c+1];
for (int i = 0; i <= c; i++)
resizeC[i] = C[i];
return resizeC;
}
public static void main(String[] args)
{
Value[] matrixA = {
new Value(45, 1000000, 1),
new Value(46, 1000000, 2),
new Value(47, 1000000, 3),
new Value(48, 1000000, 4),
new Value(1234, 123, 5),
};
Value[] matrixB = {
new Value(1000000, 45, 1),
new Value(1000000, 46, 2),
new Value(1000000, 47, 3),
new Value(1000000, 48, 4),
new Value(789, 5678, 5),
};
DotProduct dp = new DotProduct();
Value[] matrixC = dp.compute(matrixA, matrixB);
for (int i = 0; i < matrixC.length; i++)
System.out.println(matrixC[i]);
}
}
Assuming each key in the hashmap corresponds to a row and it's values correspond to the column.
public int dotProduct(Hashmap<Integer, Integer> map1, Hashmap<Integer, Integer> map2){
if((map1 == null && map2 == null) || (map1.isEmpty() && map2.isEmpty())) throw new NullPointerException();
if(map1.size() != map2.size()) throw new Exception(“Matrices need to be the same size”);
int result = 0;
for(Integer key : map1.keySet()){
int val1 = map1.get(key);
int val2 = map2.get(key);
result += (val1*val2);
}
return result;
}
- Rohit January 06, 2017