6/28, LinkedIn 面经题

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:

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:

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

几个特殊情况,:

• 一行只有一个单词, 没有完美填充

• 一行只有一个单词, 完美填充

• 最后一行左对齐

开始写的, 过了18/24, 挂在了"world owes you a living; the"; 应该world后跟两个space, you后面跟两个space

好吧, 看了答案后原来extra space要一个一个用.

这道题正确的姿势是计算each和extra, each总是大于等于1的, extra是要append多少个" ".

each = (L-len)/(w-i-1) + 1; extra = (L-len)%(w-i-1);

    public List<String> fullJustify(String[] words, int L) {
        List<String> ans = new ArrayList<String>();
        int w = 0;
        for(int i=0;i<words.length;i=w){
            w = i;
            int len = -1;//notice
            for(;w<words.length&&len+words[w].length()+1<=L;w++) //notice <=L
                len+= words[w].length() + 1;

            int each = 1; int extra = 0;
            if(w!=i+1 && w!=words.length){  // two special cases: if not only 1 word, not last line
                each = (L-len)/(w-i-1) + 1; //w-i words, w-i-1 space
                extra = (L-len)%(w-i-1);
            }

            StringBuilder sb = new StringBuilder(words[i]); //notice append first word, then while ( append space, append words)
            for(int j=i+1;j<w;j++){
                for(int s = each;s>0;s--) sb.append(' '); 
                if(extra>0){
                    sb.append(' ');
                    extra--;
                }
                sb.append(words[j]);

            }
            String tmp = sb.toString(); //check if only one word, if last line, append extra space in the end
            while(tmp.length()<L) tmp+=' ';
            ans.add(tmp);
        }
        return ans;
    }

这题不怎么考算法思想和数据结构，就是看你怎么处理各种 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 最坏情况下也只会在一个单词后面多加上一个；+

• 如果是一个单词一行的情况，则计算剩余空白，都填上空格。

• 设立新起点，新一轮扫描。

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