> 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/628-_linkedin_mian_jing_ti.md).

# 6/28, LinkedIn 面经题

## [Two Sum III - Data structure design](https://leetcode.com/problems/two-sum-iii-data-structure-design/)

这是个典型的 data structure design trade off 问题，因为 add() 和 find() 函数总有一个会很慢，问题在于让那个慢，就要取决于具体的 workload. 真问到这种问题一定要先问清楚。

### 需要注意的 corner case 是，\[add(0), find(0)]，这类情况，还有 \[add(2), add(2), find(4)] 这类。

### Quick-Find:

```java
public class TwoSum {

    HashSet<Integer> num = new HashSet<>();
    HashSet<Integer> sum = new HashSet<>();

    // Add the number to an internal data structure.
    public void add(int number) {
        if(num.contains(number)) {
            sum.add(number * 2);
        } else {
            Iterator<Integer> iter = num.iterator();
            while(iter.hasNext()){
                int num = iter.next();
                sum.add(num + number);
            }
            num.add(number);
        }
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        return sum.contains(value);
    }
}
```

### 事实证明，拿到 iterator 手动 iter.next 要比直接用 enhanced for loop 快。

### Quick-Add:

```java
public class TwoSum {

    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    // Add the number to an internal data structure.
    public void add(int number) {
        if(map.containsKey(number)){
            map.put(number, 2);
        } else {
            map.put(number, 1);
        }
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        Iterator<Integer> iter = map.keySet().iterator();

        while(iter.hasNext()){
            int key = iter.next();
            if(map.containsKey(value - key)){
                if(key != value - key || map.get(key) == 2) return true;
            }
        }
        return false;
    }
}
```

## [Text Justification](https://leetcode.com/problems/text-justification/)

这题不怎么考算法思想和数据结构，就是看你怎么处理各种 test case 以及字符串边边角角的细节问题。。

假如 L = 10 的话，我们需要重点考虑的是这么几种情况；

* **x x x \_ \_ x x \_ x x**
* **x x x x x \_ \_ \_ \_ \_**
* **x x x \_ x \_ x \_ x \_**
* 每一行最左面肯定是填满的，没有空余；
* 每一个单词后面都要空格分开，结尾除外；
* 每一行最右面可能正好填满，也可能有空格；
* 如果正好到了最后一个单词，或者连续两个大单词无法 fit 到同一行，则只有一个单词，后面全是空格；

于是我们的设计思路围绕着这几种情况考虑：

* 维护目前空间占用，如果下一个单词放不下了就开始在 \[start, end] 区间内构造单词
* 让每个单词自带一个空格占用
* 为了应对一个单词正好占满整行的情况，起始空间占用为 -1，此后依次增加 word\[i].length + 1;

进入填词阶段：

* 每个单词后面的空格数为标准 space + extra，其中 space 默认为 1， extra 默认为 0；
* 如果不是一行只有一个单词的情况，则根据 gap 数计算 space 与 extra 值；
  * space = (剩余空间 / gap 数) + 1;
  * extra = (剩余空间 % gap 数)；
* 启动 StringBuilder，先把第一个单词填上；
* 而后进入循环按照 space 与 extra 数填充；extra 最坏情况下也只会在一个单词后面多加上一个；
* 如果是一个单词一行的情况，则计算剩余空白，都填上空格。
* 设立新起点，新一轮扫描。

```java
public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> list = new ArrayList<String>();

        int N = words.length;
        int right = 0;
        for(int left = 0; left < N; left = right){
            // Each word comes with one space;
            // Except the first word, so start with -1.
            int len = -1;
            for(right = left; right < N && len + words[right].length() + 1 <= maxWidth; right ++){
                len += words[right].length() + 1;
            }

            // Those are in case there's only one word picked, or in last line
            int space = 1;
            int extra = 0;
            if(right != left + 1 && right != N){
                // right - left - 1 is number of gaps
                space = (maxWidth - len) / (right - left - 1) + 1;
                extra = (maxWidth - len) % (right - left - 1);
            }
            StringBuilder sb = new StringBuilder(words[left]);
            for(int i = left + 1; i < right; i++){
                for(int j = 0; j < space; j++) sb.append(' ');
                if(extra-- > 0) sb.append(' ');
                sb.append(words[i]);
            }

            int rightSpace = maxWidth - sb.length();
            while(rightSpace-- > 0) sb.append(' ');
            list.add(sb.toString());
        }

        return list;
    }
}
```


---

# 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/628-_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.