2017/7/13-Facebook电面

45分钟电面，今天下午刚刚面完。面试官是个中国姐姐，人非常好，面试全程都特别友善。一开始很紧张，结果上来她先跟我聊了一会儿，问了问我的background，上过哪些专业课，最喜欢/不喜欢什么课、为什么etc.，大约聊了五六分钟。聊完天以后放松多了就开始做题，面试官只准备了一道题。

【题目】
两个input：
1）desired time range to arrange a meeting -- TimeRange desired_time
2）a list of busy intervals -- List<TimeRange> busy_intervals

output:
list of time ranges where a meeting can be scheduled, 会议没有时长限制 -- List<TimeRange>

class TimeRange {
    double start,
    double end

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

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

- 12], [[8 - 9], [13 - 14]]
    output: [[10 - 12]]

补充内容 (2017-7-14 04:33):
3. input: [7-16], [[8-10], [9-12.5], [14-15]]
   output: [[7-8], [12.5, 14], [15-16]]

补充内容 (2017-7-17 22:10):
一语成谶啊，一大早就收到拒信了，不过脸书的面试体验还是很好的！大家加油努力刷题~

发一个我想的跟大家交流下，基本思路就是排序之后一遍pass，如果当前busy interval 的开始是在 desired 的start 和 end 之间，则加入list，然后更新start 为此busy interval的end时间。
```
vector<Interval> intervals = {{8, 10}, {9, 12}, {14, 15}};
    sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){return a.start < b.start;});
    int s = 9, e = 14;
    for (int i = 0; i < intervals.size(); ++i) {
        if (intervals[i].start > e) break;
        if (intervals[i].end < s) continue;
        if (intervals[i].start > s) {
            cout << s << " -> " << intervals[i].start << endl;
        }         
        s = intervals[i].end;
    }
    if (s < e) cout << s << " -> " << e << endl;
```

是这题吧，加自己merge intervals
163. Missing Ranges

```
import java.util.*;
public class fb1{
        static class TimeRange{
                double start;
                double end;
                public TimeRange(double a, double b) {
                        start = a;
                        end = b;
                }
        }

/*
1. input: [9 - 14.5], [[8 - 10], [9 - 12.5], [14 - 15]]
   output: [[12.5 - 14]]
2. input: [10 - 12], [[8 - 9], [13 - 14]]
    output: [[10 - 12]]. 1point3acres.com/bbs

3. input: [7-16], [[8-10], [9-12.5], [14-15]]
   output: [[7-8], [12.5, 14], [15-16]]
*/
        public static List<TimeRange> getFreeTimeRange(TimeRange meetingTime, List<TimeRange> busyTime) {
                List<TimeRange> res = new ArrayList<>();
                if(meetingTime == null) return res;
                if(busyTime == null || busyTime.size() == 0) {
                        res.add(meetingTime);
                        return res;
                }

                Collections.sort(busyTime, new Comparator<TimeRange>(){
                        public int compare(TimeRange a, TimeRange b) {
                                return a.start == b.start ? (int)(a.end - b.end) : (int)(a.start - b.start);
                        }
                });

                List<TimeRange> merged = new ArrayList<>();
                double start = busyTime.get(0).start, end = busyTime.get(0).end;
                for(int i = 1; i < busyTime.size(); i++) {
                        if(busyTime.get(i).start <= end) {
                                end = Math.max(end, busyTime.get(i).end);
                        }
                        else {
                                merged.add(new TimeRange(start, end));
                                start = busyTime.get(i).start;
                                end = busyTime.get(i).end;
                        }
                }
                merged.add(new TimeRange(start, end));

                //[9-16], [[8-10], [11-13], [15-17]];
                double s = meetingTime.start;
                double e = meetingTime.end;

                for(int i = 0; i < merged.size(); i++) {
                        if(merged.get(i).start >= e) break;
                        else if(merged.get(i).end >= e){
                                e = merged.get(i).start;
                                break;
                        }
                        if(merged.get(i).end <= s) continue;
                        if(merged.get(i).start <= s) {
                                s = merged.get(i).end;
                                continue;
                        }
                        res.add(new TimeRange(s, merged.get(i).start));
                        s = merged.get(i).end;
                }

                if(s < e) res.add(new TimeRange(s, e));

                return res;
        }

        public static void main(String[] args) {
                TimeRange meetingTime = new TimeRange(7,15);
                List<TimeRange> busyTime = new ArrayList<>();
                busyTime.add(new TimeRange(8,10));
                busyTime.add(new TimeRange(9,12.5));
                busyTime.add(new TimeRange(14,16));

                List<TimeRange> res = getFreeTimeRange(meetingTime, busyTime);
                for(TimeRange tr : res) {
                        System.out.print(tr.start +"->" + tr.end + "; ");
                }
        }
}
```
这样么。

fb 18年new grad 已经开始了吗

同问楼主是18new grad么

竟然不是leetcode的原题了？

补充内容 (2017-7-17 12:38):
楼主用的是Python，能不能po一下代码？谢谢谢谢

kennethinsnow 发表于 2017-7-17 09:58
是这题吧，加自己merge intervals
163. Missing Ranges

看了一下，好像确实是诶。我题刷得不要多，所以原先没见过163

littlegrass 发表于 2017-7-17 10:44
fb 18年new grad 已经开始了吗

应该没有吧。我是17 grad，在找工作这件事上比较迟钝，5月才找人内推的 不过听去了fb的朋友说upcoming grad 8、9月份就可以开始找人推过去了

mtrsen 发表于 2017-7-17 11:28
同问楼主是18new grad么

不是的，我是一个比较拖延的17 grad。。

david.fang 发表于 2017-7-17 12:28
竟然不是leetcode的原题了？

补充内容 (2017-7-17 12:38):

对，不是利口原题，但是相似。代码没存，我的代码逻辑分为两段，第一段用merge interval的代码就可以，第二段用一个指针指着meeting interval的start，然后扫busy_interval, 把busy interval的start和指针作比较，再根据不同结果取出free interval。据面试官提醒第一第二段可以并在一起做，2 passes 变成 1 pass