6/17, LinkedIn 面经题

Sparse Matrix Multiplication

优化方法参考论坛这个帖子，里面提到了一个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;
    }
}

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;
    }
}