CareerCup

typedef unordered_map<int, int> Value;
typedef unordered_map<int, Value> Entry;

Class SparseMatrix {
public:
	int m;
	int n;
	
	Entry entries;
	
	int GetValue(const int row, const int col) const {
		Entry::iterator rowIt = entries.find(row);
		if (rowIt == entries.end()) {
			return 0;
		}
		
		Value::iterator colIt = (rowIt->second).find(k);
		if (colIt == (m1It->second).end()) {
			return 0;
		}
		
		return colIt->second;
	}
};

void DotProduct(const SparseMatrix& m1, const SparseMatrix& m2, SparseMatrix& ret)
{
	ret.m = ret.n = 0;
	ret.entries.clear();
	
	if (m1.n != m2.m) {
		return;
	}
	
	for (int i = 0; i < m1.m; ++i) {
		for (int l = 0; l < m2.m; ++l) {
			int ele = 0;
			for (int k = 0; k < m1.n; ++k) {
				ele += (m1.GetValue(i, k) * m2.GetValue(k, j);
			}
			
			if (ele != 0) {
				ret[i][j] = ele;
		}
	}
}

We can use array of linked list, with column and data as the node value for only non-zero 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;
}