# 6/17, LinkedIn 面经题

## [Sparse Matrix Multiplication](https://leetcode.com/problems/sparse-matrix-multiplication/)

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

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

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

```java
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.

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

优化方法参考论坛[这个帖子](https://leetcode.com/discuss/71912/easiest-java-solution)，里面提到了一个 [CMU Lecture](http://www.cs.cmu.edu/~scandal/cacm/node9.html) ，明天有空看看。

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

```java
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**

```java
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](https://leetcode.com/problems/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 的情况。

```java
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 加速。

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/linkedin_mian_jing/617-_linkedin_mian_jing_ti.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.