推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2011|回复: 26
收起左侧

2017/7/13-Facebook电面

[复制链接] |试试Instant~ |关注本帖
Lyd. 发表于 2017-7-14 04:27:56 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
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
. more info on 1point3acres.com
output:
list of time ranges where a meeting can be scheduled, 会议没有时长限制 -- List<TimeRange>

class TimeRange {
    double start,
    double end
}

基本就是利口56的变形。我的思路是先把busy_intervals根据开始时间sort一下,再把有重合的时间段merge起来,生成一个没有overlap并且已经排好序的list of busy_intervals。接下来再用一个指针过这个处理过的list生成returned list。
-google 1point3acres
写得差不多开始检查的时候面试官提了一组example input,carry我de出了一个bug,炒鸡感恩&#128514;。后来又问我能不能想出一些edge case来测试一下逻辑。我举了一个meeting interval在两个busy_interval之间的edge case,听到她说good job。用这组input过了一遍代码又发现一个小bug,唉。。。安妮魏,她举了一个我没提到的edge case过了一下我的代码,说好像没有什么问题了,转而问我时间复杂度。我的答案是sort部分用的是python自带函数:O(nlog(n));merge是one pass:O(n);生成output也是one pass:O(n),所以总的复杂度是O(nlog(n))。. from: 1point3acres.com/bbs
.1point3acres缃
最后问的是觉得自己的代码哪里可以improve。我一开始以为她指的是time complexity,就回答感觉必须要sort的吧,所以时间复杂度应该降不了了,结果她指的是code本身。我卡了一下,说有些小地方可以稍稍refactor一下更简洁些,一下想不到其他的。然后她就说其实没必要过两遍,可以一边merge的时候一边就生成output list了,瞬间觉得自己蠢爆了。。。

还剩几分钟,是我问问题的环节。问了下她在fb工作多久了,喜不喜欢fb的工作环境。聊了大概七八分钟,很愉快,面试官主动讲了一些她以前在哪工作呀、为什么觉得fb好啊之类的事情。整个面试超时了大概六分钟。

不知道能不能过。。自我感觉还不错,但是感觉小姐姐是个很有经验的面试官,所以尽管面试过程挺愉快的,也有可能转头就把我跪了,何况我的两个bug都不算是自己发现的。。。
求过求保佑!&#128591;


补充内容 (2017-7-14 04:32):
补充几个test case:
1. input: [9 - 14.5], [[8 - 10], [9 - 12.5], [14 - 15]]
   output: [[12.5 - 14]]
2. input: [10 - 12], [[8 - 9], [13 - 14]]. From 1point 3acres bbs
    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):
一语成谶啊,一大早就收到拒信了,不过脸书的面试体验还是很好的!大家加油努力刷题~

评分

1

查看全部评分

本帖被以下淘专辑推荐:

jingshihao 发表于 2017-7-28 09:19:26 | 显示全部楼层
发一个我想的跟大家交流下,基本思路就是排序之后一遍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;. more info on 1point3acres.com
    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; . 鍥磋鎴戜滑@1point 3 acres
        }         
        s = intervals[i].end;
    }
    if (s < e) cout << s << " -> " << e << endl;
```
回复 支持 2 反对 0

使用道具 举报

kennethinsnow 发表于 2017-7-17 09:58:35 | 显示全部楼层
是这题吧,加自己merge intervals
163. Missing Ranges
回复 支持 反对

使用道具 举报

littlegrass 发表于 2017-7-17 10:44:17 | 显示全部楼层
fb 18年new grad 已经开始了吗
回复 支持 反对

使用道具 举报

mtrsen 发表于 2017-7-17 11:28:27 | 显示全部楼层
同问楼主是18new grad么
回复 支持 反对

使用道具 举报

david.fang 发表于 2017-7-17 12:28:20 | 显示全部楼层
竟然不是leetcode的原题了?

补充内容 (2017-7-17 12:38):
楼主用的是Python,能不能po一下代码?谢谢谢谢
回复 支持 反对

使用道具 举报

 楼主| Lyd. 发表于 2017-7-17 13:41:51 | 显示全部楼层
kennethinsnow 发表于 2017-7-17 09:58
是这题吧,加自己merge intervals
163. Missing Ranges
. from: 1point3acres.com/bbs
看了一下,好像确实是诶。我题刷得不要多,所以原先没见过163
回复 支持 反对

使用道具 举报

 楼主| Lyd. 发表于 2017-7-17 13:43:41 | 显示全部楼层
littlegrass 发表于 2017-7-17 10:44
fb 18年new grad 已经开始了吗

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

使用道具 举报

 楼主| Lyd. 发表于 2017-7-17 13:43:55 | 显示全部楼层
mtrsen 发表于 2017-7-17 11:28 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
同问楼主是18new grad么

不是的,我是一个比较拖延的17 grad。。
回复 支持 反对

使用道具 举报

 楼主| Lyd. 发表于 2017-7-17 13:47:04 | 显示全部楼层
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
回复 支持 反对

使用道具 举报

cooldogrj 发表于 2017-7-20 04:45:27 | 显示全部楼层
```
import java.util.*;
public class fb1{
        static class TimeRange{
                double start;. more info on 1point3acres.com
                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]].鏈枃鍘熷垱鑷1point3acres璁哄潧
*/. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        public static List<TimeRange> getFreeTimeRange(TimeRange meetingTime, List<TimeRange> busyTime) {
                List<TimeRange> res = new ArrayList<>();. from: 1point3acres.com/bbs
                if(meetingTime == null) return res;
                if(busyTime == null || busyTime.size() == 0) {
                        res.add(meetingTime);-google 1point3acres
                        return res;.1point3acres缃
                }

                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;. visit 1point3acres.com for more.
                for(int i = 1; i < busyTime.size(); i++) {. from: 1point3acres.com/bbs
                        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;
                        }-google 1point3acres
                }
                merged.add(new TimeRange(start, end));. From 1point 3acres bbs

                //[9-16], [[8-10], [11-13], [15-17]];
                double s = meetingTime.start;-google 1point3acres
                double e = meetingTime.end;. from: 1point3acres.com/bbs

                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;. visit 1point3acres.com for more.
                        if(merged.get(i).start <= s) {
                                s = merged.get(i).end;. From 1point 3acres bbs
                                continue;
                        }
                        res.add(new TimeRange(s, merged.get(i).start));
                        s = merged.get(i).end;
. 1point3acres.com/bbs                }

                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<>();
.1point3acres缃                busyTime.add(new TimeRange(8,10));
                busyTime.add(new TimeRange(9,12.5));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                busyTime.add(new TimeRange(14,16));. 1point3acres.com/bbs
. 1point 3acres 璁哄潧
                List<TimeRange> res = getFreeTimeRange(meetingTime, busyTime);
                for(TimeRange tr : res) {
                        System.out.print(tr.start +"->" + tr.end + "; ");
                }
        }
}
```
这样么。
回复 支持 反对

使用道具 举报

bustu 发表于 2017-7-25 10:37:56 | 显示全部楼层
求问楼主,会议没有时长限制 是指什么呢?desired_time.start 和 desired_time.end 代表的是会议开始和结束的时间吗?如果是这样的话,那desired_time.end - desired_time.start 不就是会议时长吗?. From 1point 3acres bbs
谢谢
回复 支持 反对

使用道具 举报

christwsy 发表于 2017-7-26 12:27:02 | 显示全部楼层
感觉好像没看懂busy interval和desired的关系。。
回复 支持 反对

使用道具 举报

shuoshuo 发表于 2017-7-26 12:51:04 | 显示全部楼层
是不是可定义一个长度为24的boolean数组,busyt ime置为1, 找到meeting time的区间内为0的字段
回复 支持 反对

使用道具 举报

mchzh 发表于 2017-7-26 13:22:40 | 显示全部楼层
这是new grad还是社招?
回复 支持 反对

使用道具 举报

 楼主| Lyd. 发表于 2017-7-28 06:33:05 | 显示全部楼层
mchzh 发表于 2017-7-26 13:22
这是new grad还是社招?

应该是new grad。是university recruiting的hr联系我的
回复 支持 反对

使用道具 举报

 楼主| Lyd. 发表于 2017-7-28 06:33:51 | 显示全部楼层
shuoshuo 发表于 2017-7-26 12:51
是不是可定义一个长度为24的boolean数组,busyt ime置为1, 找到meeting time的区间内为0的字段

hmmm感觉这个不错!但是还有9:30这样非整点的时间怎么办呢?
回复 支持 反对

使用道具 举报

 楼主| Lyd. 发表于 2017-7-28 06:34:27 | 显示全部楼层
christwsy 发表于 2017-7-26 12:27
感觉好像没看懂busy interval和desired的关系。。

hmmm哪里没看懂。。会议只能发生在desired interval中非busy的时间段
回复 支持 反对

使用道具 举报

 楼主| Lyd. 发表于 2017-7-28 06:35:28 | 显示全部楼层
bustu 发表于 2017-7-25 10:37
求问楼主,会议没有时长限制 是指什么呢?desired_time.start 和 desired_time.end 代表的是会议开始和结束 ...

就是会议不需要一定持续多久。start和end只是一个区间,这个区间内任何非busy的时间段都可以排会议。
回复 支持 反对

使用道具 举报

 楼主| Lyd. 发表于 2017-7-28 06:36:23 | 显示全部楼层
cooldogrj 发表于 2017-7-20 04:45
```
import java.util.*;
public class fb1{

我是写python的,java好久不写已经生疏了。。不好意思
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-20 23:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表