【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

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

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

2017/7/13-Facebook电面

[复制链接] |试试Instant~ |关注本帖
Lyd. 发表于 7 天前 | 显示全部楼层 |阅读模式

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

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

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

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

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

-google 1point3acresoutput:
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。

写得差不多开始检查的时候面试官提了一组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))。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

最后问的是觉得自己的代码哪里可以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]]
    output: [[10 - 12]]. visit 1point3acres.com for more.

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

.鏈枃鍘熷垱鑷1point3acres璁哄潧补充内容 (2017-7-17 22:10):
一语成谶啊,一大早就收到拒信了,不过脸书的面试体验还是很好的!大家加油努力刷题~

评分

1

查看全部评分

本帖被以下淘专辑推荐:

kennethinsnow 发表于 4 天前 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
是这题吧,加自己merge intervals. more info on 1point3acres.com
163. Missing Ranges
回复 支持 反对

使用道具 举报

littlegrass 发表于 4 天前 | 显示全部楼层
关注一亩三分地微博:
Warald
fb 18年new grad 已经开始了吗
回复 支持 反对

使用道具 举报

mtrsen 发表于 4 天前 | 显示全部楼层
同问楼主是18new grad么
回复 支持 反对

使用道具 举报

david.fang 发表于 4 天前 | 显示全部楼层
竟然不是leetcode的原题了?

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

使用道具 举报

 楼主| Lyd. 发表于 4 天前 | 显示全部楼层
kennethinsnow 发表于 2017-7-17 09:58
是这题吧,加自己merge intervals
163. Missing Ranges

看了一下,好像确实是诶。我题刷得不要多,所以原先没见过163
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| Lyd. 发表于 4 天前 | 显示全部楼层
mtrsen 发表于 2017-7-17 11:28
同问楼主是18new grad么

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

使用道具 举报

 楼主| Lyd. 发表于 4 天前 | 显示全部楼层
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 发表于 昨天 04:45 | 显示全部楼层
```
import java.util.*;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
public class fb1{
        static class TimeRange{
                double start;
                double end;
                public TimeRange(double a, double b) {
                        start = a;
                        end = b;
                }. 1point 3acres 璁哄潧
        }
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
/*. from: 1point3acres.com/bbs
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. 1point 3acres 璁哄潧
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
3. input: [7-16], [[8-10], [9-12.5], [14-15]]. 1point3acres.com/bbs
   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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                if(busyTime == null || busyTime.size() == 0) {
                        res.add(meetingTime);. 1point3acres.com/bbs
                        return res;
                }
. 鍥磋鎴戜滑@1point 3 acres
                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);. more info on 1point3acres.com
                        }
                });. Waral 鍗氬鏈夋洿澶氭枃绔,

                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) {. visit 1point3acres.com for more.
                                end = Math.max(end, busyTime.get(i).end);
                        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        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));

                //[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){. 1point 3acres 璁哄潧
                                e = merged.get(i).start;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                break;
                        }. 鍥磋鎴戜滑@1point 3 acres
                        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;
                }.1point3acres缃

                if(s < e) res.add(new TimeRange(s, e));
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                return res;
        }. Waral 鍗氬鏈夋洿澶氭枃绔,

        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));. 鍥磋鎴戜滑@1point 3 acres
                busyTime.add(new TimeRange(14,16));

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-21 10:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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