FB电面 02-01-2019

既然找上门了就考一下，结果跪了。

题目：给出两个vector<Interval>,返回overlapped interval list
EX1: A = (0, 3) (4, 6) (9 ,12)
       B = (1, 3) (5, 10) (11, 14)
re

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

15:07):
面试官是阿三，极浓的口音，不过我练过，能听清楚。EX 1是一开始出的题，写出来后直接怼给我EX2，卡在那里。只要碰到阿三，成功率减50%

public class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
      public String toString(){
          return start+" "+ end;
      }
    }

    private List<Interval> intersectionOfIntervals(List<Interval> a, List<Interval> b){
        List<Interval> ans = new ArrayList<>();
        //assume a and b are sorted, and non intersecting within its own list
        int indexA = 0;
        int indexB = 0;
        while(indexA<a.size() && indexB<b.size()){
            Interval intvA = a.get(indexA);
            Interval intvB = b.get(indexB);
            ans.add(new Interval(Math.max(intvA.start, intvB.start), Math.min(intvB.end, intvA.end)));
            if(intvA.end == intvB.end){
                indexA++;
                indexB++;
            }
            else if(intvA.end > intvB.end){
                indexB++;

            }
            else{
                indexA++;
            }
        }
        return ans;
    }

import java.util.*;  
  
public class MergeInterval {  
    static class Interval {  
        int start;  
        int end;  
        public Interval(int s, int e) {  
            start = s;  
            end = e;  
        }  
    }  
    public static List<Interval> mergeInterval(List<Interval> l1, List<Interval> l2) {  
        List<Interval> res = new ArrayList<>();  
        if (l1.size() == 0 || l2.size() == 0) return res;  
        int i = 0;  
        int j = 0;  
        while (i < l1.size() && j < l2.size()) {  
            Interval curr1 = l1.get(i);  
            Interval curr2 = l2.get(j);  
            if ((curr1.start >= curr2.start && curr1.start < curr2.end)   
                    || (curr2.start >= curr1.start && curr2.start < curr1.end)) {  
                Interval next = new Interval(0, 0);  
                next.start = Math.max(curr1.start, curr2.start);  
                next.end = Math.min(curr1.end, curr2.end);  
                res.add(next);  
            }  
            if (curr1.end == curr2.end) {  
                i++;  
                j++;  
            } else if (curr1.end > curr2.end) {  
                j++;  
            } else {  
                i++;  
            }  
        }  
        return res;  
    }  
      
    public static void main(String[] args) {  
        List<Interval> l1 = new ArrayList<>();  
        l1.add(new Interval(0, 3));  
        l1.add(new Interval(4, 6));  
        l1.add(new Interval(9, 12));  
        List<Interval> l2 = new ArrayList<>();  
        l2.add(new Interval(1, 3));  
        l2.add(new Interval(5, 10));  
        l2.add(new Interval(11, 14));  
        List<Interval> l3 = new ArrayList<>();  
        l3.add(new Interval(2, 8));  
        List<Interval> l4 = new ArrayList<>();  
        l4.add(new Interval(2, 4));  
        l4.add(new Interval(5, 6));  
        l4.add(new Interval(7, 9));  
        List<Interval> res1 =mergeInterval(l1, l2);  
        System.out.println("EX1:");  
        for (int i = 0; i < res1.size(); i++) {  
            System.out.print(res1.get(i).start + " " + res1.get(i).end + " -> ");  
        }  
        System.out.println();  
        List<Interval> res2 = mergeInterval(l3, l4);  
        System.out.println("EX2:");  
        for (int i = 0; i < res2.size(); i++) {  
            System.out.print(res2.get(i).start + " " + res2.get(i).end + " -> ");  
        }  
    }  
}  

如果这两个都没排好序 有0(n) 的解法吗 如果是排序的，可以直接merge 把 类似merge sort 的过程 两个指针指向头 依次遍历

mmao3 发表于 2019-2-1 15:10
如果这两个都没排好序 有0(n) 的解法吗 如果是排序的，可以直接merge 把 类似merge sort 的过程 两个指针指 ...

这就是我一开始的写法，而且不止这个，结果中的Interval是不止要更新end, 还要更新start. 可是这题EX 2否定了这个写法。感觉这个更像是scheduling 的问题。

麻倉枼 发表于 2019-2-2 05:20
这就是我一开始的写法，而且不止这个，结果中的Interval是不止要更新end, 还要更新start. 可是这题EX 2否 ...

拿你第二个例子来说 A = (2, 8)
        B = (2, 4) (5, 6) (7, 9)
两个指针 i , j 分别指向A,B，谁小更新谁， 2,4 2,8 overlap(2,4) j指针+1, 5,6 2,8 overlap (5,6) j指针继续更新 7, 9 2,8 oeverlap (7,8) 此时i小，更新i, 一个指针已经到头，循环结束。感觉这个提与schedual 没有关系，就是考察双指针

mmao3 发表于 2019-2-1 16:27
拿你第二个例子来说 A = (2, 8)
        B = (2, 4) (5, 6) (7, 9)
两个指针 i , j 分别指向A,B，谁小 ...

本人蠢，感觉有道理哦。那么如果没conflict的话哪个指针继续走？

麻倉枼 发表于 2019-2-2 05:37
本人蠢，感觉有道理哦。那么如果没conflict的话哪个指针继续走？

如果两个没有交集 移动小的 。有交集，计算完之后，也是移动小的。永远是谁小移动谁，跟merge sort 的merge 过程是一样的
例如 （1，2） （5，6）
（3，5）（9，10）
（1，2） 和 （3，5）没有交集， 那么（1，2）不可能跟（3，5）后面的再有交集，所以我们可以安全的移动它

mmao3 发表于 2019-2-1 17:39
如果两个没有交集 移动小的 。有交集，计算完之后，也是移动小的。永远是谁小移动谁，跟merge sort 的mer ...

好吧，这样的确可以的，感觉这个就是答案了，造福后人吧。

Ronald4545 发表于 2019-2-2 08:31
public class Interval {
      int start;
      int end;

太强了，连class 都帮写了。

下面这句之前是不是要判断一下 将要创造的这个interval是否合法（s < e )?

ans.add(new Interval(Math.max(intvA.start, intvB.start), Math.min(intvB.end, intvA.end)));

你是對的
需要檢查intvA and intvB 有沒有 intersect,
沒有, skip ans.add, and go to bottom to decide what to do with indexA and index