6/17, LinkedIn 面经题

Sparse Matrix Multiplication

我现在知道这题为什么 AC 率这么高了。。因为直接写个 triple nested loop 也能过。。

然后就是以 1021ms 的傲人速度打败了 3% 的用户 =。= 绝大多数 submission 在 60~70ms 之间。

所以看来这题的主要思路还是“空间换时间”。

public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int rowsA = A.length;
        int colsA = A[0].length;
        int rowsB = B.length;
        int colsB = B[0].length;

        int[][] rst = new int[rowsA][colsB];

        for(int i = 0; i < rowsA; i++){
            for(int j = 0; j < colsB; j++){
                for(int k = 0; k < colsA; k++){
                    if(A[i][k] == 0 || B[k][j] == 0) continue;
                    rst[i][j] += A[i][k] * B[k][j];
                }

            }
        }

        return rst;
    }
}

经过一番简单优化之后，时间已然降到了 324ms，用 List of Lists 存 A/B 矩阵中不为 0 的 row/col

这题用 HashMap，Key = Integer, Value = List，600ms;

改用 List of Lists，324ms;

最后用 List[] 里面放 List，248ms.

public class Solution {
    private class Tuple{
        int index;
        int val;
        public Tuple(int index, int val){
            this.index = index;
            this.val = val;
        }
    }

    public int[][] multiply(int[][] A, int[][] B) {
        int rowsA = A.length;
        int colsA = A[0].length;
        int rowsB = B.length;
        int colsB = B[0].length;

        int[][] rst = new int[rowsA][colsB];

        List[] rowList = new List[rowsA];
        List[] colList = new List[colsB];

        for(int i = 0; i < rowsA; i++){
            List<Tuple> newList = new ArrayList<Tuple>();
            for(int j = 0; j < colsA; j++){
                if(A[i][j] != 0) newList.add(new Tuple(j, A[i][j]));
            }
            rowList[i] = newList;
        }

        for(int i = 0; i < colsB; i++){
            List<Tuple> newList = new ArrayList<Tuple>();
            for(int j = 0; j < rowsB; j++){
                if(B[j][i] != 0) newList.add(new Tuple(j, B[j][i]));
            }
            colList[i] = newList;
        }

        for(int i = 0; i < rowsA; i++){
            for(int j = 0; j < colsB; j++){
                rst[i][j] = multiply(rowList[i], colList[j]); 
            }
        }

        return rst;
    }

    private int multiply(List<Tuple> A, List<Tuple> B){
        if(A == null || B == null) return 0;
        if(A.size() == 0 || B.size() == 0) return 0;

        int sum = 0;
        int ptrA = 0;
        int ptrB = 0;
        while(ptrA < A.size() && ptrB < B.size()){
            if(A.get(ptrA).index == B.get(ptrB).index){
                sum += A.get(ptrA++).val * B.get(ptrB++).val;
            } else if(A.get(ptrA).index < B.get(ptrB).index){
                ptrA ++;
            } else {
                ptrB ++;
            }
        }
        return sum;
    }
}

优化方法参考论坛这个帖子，里面提到了一个 CMU Lecture ，明天有空看看。

• 70ms 的解其实很简单；考虑到外面都是 i,j,k 的三重循环，所有操作都在最里面执行，可以直接把index 的顺序交换，这样可以利用其中某个位置为 0 的特点，直接跳过最内圈的循环。

• 交换 j , k

public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int rowsA = A.length;
        int colsA = A[0].length;
        int rowsB = B.length;
        int colsB = B[0].length;

        int[][] rst = new int[rowsA][colsB];

        for(int i = 0; i < rowsA; i++){
            for(int k = 0; k < colsA; k++){
                if(A[i][k] == 0) continue;

                for(int j = 0; j < colsB; j++){
                    if(B[k][j] == 0) continue;
                    rst[i][j] += A[i][k] * B[k][j];
                }

            }
        }

        return rst;
    }
}

• 交换 i , k

public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int rowsA = A.length;
        int colsA = A[0].length;
        int rowsB = B.length;
        int colsB = B[0].length;

        int[][] rst = new int[rowsA][colsB];


        for(int k = 0; k < colsA; k++){
            for(int j = 0; j < colsB; j++){
                if(B[k][j] == 0) continue;

                for(int i = 0; i < rowsA; i++){
                    if(A[i][k] == 0) continue;
                    rst[i][j] += A[i][k] * B[k][j];
                }

            }
        }

        return rst;
    }
}

Isomorphic Strings

这题考察的是，如何实现一个 “双向 one-to-one onto mapping (bijection)”，原 domain 是 String S 的字符集，目标 domain 是 String T 的字符集。不能出现 one-to-many 或者 many-to-one.

写一会儿很快就可以发现，一个 hashmap 是不够的，至少不够快。因为一个 hashmap 只能做一个方向的 mapping，不能高效反方向查找有没有出现 one-to-many / many-to-one 的情况。

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if(s.length() != t.length()) return false;

        HashMap<Character, Character> mapS = new HashMap<Character, Character>();
        HashMap<Character, Character> mapT = new HashMap<Character, Character>();

        for(int i = 0; i < s.length(); i++){
            char charS = s.charAt(i);
            char charT = t.charAt(i);

            if(mapT.containsKey(charT) && mapT.get(charT) != charS) return false;
            if(mapS.containsKey(charS) && mapS.get(charS) != charT) return false;

            mapS.put(charS, charT);
            mapT.put(charT, charS);
        }

        return true;
    }
}

既然输入都是字符串，方便起见，可以用 int[256] 代替 hashmap 加速。

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if(s.length() != t.length()) return false;

        int[] mapS = new int[256];
        int[] mapT = new int[256];

        for(int i = 0; i < s.length(); i++){
            char charS = s.charAt(i);
            char charT = t.charAt(i);

            if(mapT[charT] != 0 && mapT[charT] != (int) charS) return false;
            if(mapS[charS] != 0 && mapS[charS] != (int) charT) return false;

            mapS[charS] = (int)charT; 
            mapT[charT] = (int)charS;
        }

        return true;
    }
}