> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/linkedin_mian_jing/76-_linkedin_mian_jing.md).

# 7/6, LinkedIn 面经

## [Find Leaves of Binary Tree](https://leetcode.com/problems/find-leaves-of-binary-tree/)

这题本身不难，但是有一个常见错误：

### 在 dfs 中直接 root = null 是无法删除 root 的.

### 因为对于 object， java 是 pass by value, 传递过去的是 object reference.

### 在[这个帖子](http://javadude.com/articles/passbyvalue.htm)中举例：

![](/files/-MUt7aVxc5W5ZeVE4D7Y)

### 换句话讲，dfs 中作为参数的 TreeNode root 是一个新建的 reference，默认指向的是原参数 root 的同一个位置。因此我们可以对它指向的 object 进行各种操作.

### 但是当我们更改这个 reference 指向时，我们只是改了函数自己的那个 copy 所指向的 object，而对原始参数指向的东西没有任何改变。

### 于是这题如果试图在 dfs 中用 root = null 删除节点，实际上我们不会删除任何节点，只会更改在自己这层 call 中， root 指向的节点而已。因此我们之前可以用其他 method call 在 dfs 中对各种 list, set, map 和 collection 里面的值进行修改，但是改 method call 里面的 reference 并不会对原 object 造成任何影响。

![](/files/-MUt7aVyjtd3qJdI6vUE)

```java
public class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();

        while(root != null) {
            List<Integer> list = new ArrayList<Integer>();
            if(dfs(list, root)) root = null;
            rst.add(list);
        }

        return rst;
    }

    private boolean dfs(List<Integer> list, TreeNode root){
        if(root == null) return false;
        if(root.left == null && root.right == null){
            list.add(root.val);
            return true;
        }

        if(dfs(list, root.left)) root.left = null;
        if(dfs(list, root.right)) root.right = null;

        return false;
    }
}
```

## [Find the Celebrity](https://leetcode.com/problems/find-the-celebrity/)

对于两个人 A 与 B, 有如下可能：

#### knows(A, B)

* **A --> B ( A knows B )**
  * **A 一定不是明星**
* **A <-- B ( B knows A)**
  * **B 一定不是明星**
* **A ... B ( 互相不认识 )**
  * **B 一定不是明星**

因为给定条件“所有人都认识明星，而明星不认识任何人”，对于任意一对 A 和 B，我们仅仅做一次 knows 比较就可以排除掉一个人，我们就可以存一个 ptr 依次扫描整个数组。

当最后只剩下一个可能性的时候，我们依然有必要检查一下，因为我们不确定这个 cur 是不是认识数组里的其他人，或者是不是其他人都认识 cur. 因此再一次循环进行判断 + 记录认识 cur 的人数就可以了。

```java
public class Solution extends Relation {
    public int findCelebrity(int n) {
        int cur = 0;
        for(int i = 1; i < n; i++){
            if(knows(cur, i)) cur = i;
        }

        int knowCount = 0;
        for(int i = 0; i < n; i++){
            if(i == cur) continue;

            if(knows(cur, i)) return -1;
            else if(knows(i, cur)) knowCount ++;
        }

        return knowCount == n - 1 ? cur: -1;
    }
}
```

## [ Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/)

老题了，前缀积数组的应用。

```java
public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int N = nums.length;

        int[] leftCumProd = new int[N + 1];
        int[] rightCumProd = new int[N + 1];

        leftCumProd[0] = 1;
        rightCumProd[N] = 1;

        for(int i = 0; i < N; i++){
            leftCumProd[i + 1] = leftCumProd[i] * nums[i];
        }
        for(int i = N - 1; i >= 0; i--){
            rightCumProd[i] = rightCumProd[i + 1] * nums[i];
        }

        int[] rst = new int[N];
        for(int i = 0; i < N; i++){
            rst[i] = leftCumProd[i] * rightCumProd[i + 1];
        }

        return rst;
    }
}
```

## [Factor Combinations](https://leetcode.com/problems/factor-combinations/)

Word Search II 之后留下了后遗症，看到这种问题也想用记忆化搜索加快速度。

不过这题的 subproblem 不太一样。 因为当最开始的 n 真的等于质数时，我们返回 empty list; 但是如果这是个 dfs 嵌套的 method call，我们却要把这个质数加到 list 里。 换句话说，同样 size / interval 的 subproblem， 返回的结果却要依情况而定，这是违反了记忆化搜索和动态规划性质的。

### 简单说就是，这题的 subproblem 之间，不具有 optimal substructure.

dfs(12) 并不等于 2 + dfs(6) 和 3 + dfs(4) 与 4 + dfs(3) ..

于是我们仔细观察 sample output 中，n = 32 的正解，重新排列顺序之后得到：

#### n = 32

* **\[16,2]**
* **\[8, 4]**
* **\[8, 2, 2]**
* **\[4, 4, 2]**
* **\[4, 2, 2, 2]**
* **\[2, 2, 2, 2, 2]**

我们可以发现把解按照递减顺序排列之后，这是一个类似 combination 的问题，因为：

* **每一个解是若干个元素的组合，解与解之间大小不等**
* **同一组解之间，元素的选取有单调性 (去重)**

具体实现上，为了保证不盲目把初始 n 加到结果中，第一层 dfs 里传进去的 prev 是 n - 1.

### 这题的 dfs 里 base case 还不太一样，我们做的是试图直接把 n 加进去作为一个解，同时要注意不能直接 return ，否则后面的解就都看不到了。

### 真正的 return ，是在对于 n 来讲从大到小连 i = 2 都尝试过作为 factor 之后自然结束搜索。

```java
public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();

        dfs(rst, new ArrayList<Integer>(), n, n - 1);

        return rst;
    }

    private void dfs(List<List<Integer>> rst, 
                     List<Integer> list, int n, int prev){
        if(n <= prev){
            list.add(n);
            rst.add(new ArrayList<Integer>(list));
            list.remove(list.size() - 1);
            //return ;
        }

        for(int i = n / 2; i >= 2; i--){
            if(n % i == 0 && i <= prev){
                list.add(i);
                dfs(rst, list, n / i, i);
                list.remove(list.size() - 1);
            }
        }
    }
}
```

## [Repeated DNA Sequences](https://leetcode.com/problems/repeated-dna-sequences/)

我想了半天怎么用 KMP 做这题复杂度比较低，看到 tag 里有 hashtable 就直接用 hashmap 套用了一下，然后不但 AC 了还在运行速度上超过了 76% 的人。。。这题的用意到底是什么。。。

唯一需要注意的是对于出现超过 2 次的 str 不要重复添加，因此 hashmap 里留一个 count ，根据 count 行事。

```java
public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        HashMap<String, Integer> map = new HashMap<>();
        List<String> list = new ArrayList<>();
        int N = s.length();
        for(int i = 0; i <= N - 10; i++){
            String str = s.substring(i, i + 10);
            if(map.containsKey(str)){
                int count = map.get(str);
                if(count == 1) list.add(str);
                map.put(str, count + 1);
            } else {
                map.put(str, 1);
            }
        }

        return list;
    }
}
```

### 去地里看了一圈，这题更有意思的解法是利用 DNA 只有四种字母的性质去做 encode / decode.

![](/files/-MUt7aWAt7exhhlNH2r1)

因为字母只有四种可能，我们可以用 2 bits 表示任意字母；同时因为 sequence 长度为 10，所以我们只需要 20 bits 就可以 Uniquely represent 一个 sequence，即自己实现无 collision 的 hashing. 简便起见，一个 32-bit int 就够了。

encode 时，对于每一个给定的 substring，遍历每个字母，然后根据字母决定其数字，给最后两位赋值之后 << 2.

decode 时，每次把当前数字除以 4 看余数，根据余数决定字母，而后 >> 2.

这样对于每一个 string / int ，其 encode / decode 都是唯一的。

空间占用为 2^20 = 1048576 个 int = 4.194304 MB ，代表可能的 hash 值数量。

```java
public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> list = new ArrayList<>();
        int N = s.length();
        int[] hash = new int[1048576];
        for(int i = 0; i <= N - 10; i++){
            String str = s.substring(i, i + 10);
            int index = encode(str);
            hash[index] ++;
            if(hash[index] == 2) list.add(str);
        }

        return list;
    }

    private int encode(String s){
        int num = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            num = num << 2;
            if(c == 'A') num += 0; 
            if(c == 'C') num += 1;
            if(c == 'G') num += 2;
            if(c == 'T') num += 3;
        }
        return num;
    }

    private String decode(int num){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < 10; i++){
            if(num % 4 == 0) sb.append('A');
            if(num % 4 == 1) sb.append('C');
            if(num % 4 == 2) sb.append('G');
            if(num % 4 == 3) sb.append('T');

            num = num >> 2;
        }
        return sb.reverse().toString();
    }
}
```

## [Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/)

轻松愉快，一次 AC.

```java
public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String str : tokens){
            if(!isOperator(str)){
                stack.push(Integer.parseInt(str));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();

                if(str.equals("+")) stack.push(num1 + num2);
                if(str.equals("-")) stack.push(num1 - num2);
                if(str.equals("*")) stack.push(num1 * num2);
                if(str.equals("/")) stack.push(num1 / num2);
            }
        }

        return stack.peek();
    }

    private boolean isOperator(String str){
        if(str.equals("+") || str.equals("-")) return true;
        if(str.equals("/") || str.equals("*")) return true;
        return false;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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/76-_linkedin_mian_jing.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.