當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 6030|回复: 24
收起左侧

FB 电面

[复制链接] |试试Instant~ |关注本帖
悲伤网管 发表于 2015-8-19 02:58:59 | 显示全部楼层 |阅读模式

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

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

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

x
上周面的,内推两周后hr联系

第一题 大陆和海洋
第二题 在一些区间中,寻找一个点,使这个点能够落入尽量多的区间,提示我用暴力解法
           比如 区间: 2,3 | 3,5 | 4,5 | 1,5 | 1,2         那么4和5都是答案
.1point3acres网
这次运气好,碰上一个友好的白人,第二天收到通知水过了

求人品求offer!
共勉大家

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · Facebook|主题: 600, 订阅: 222
  • · fb|主题: 33, 订阅: 16
 楼主| 悲伤网管 发表于 2015-9-20 01:52:51 | 显示全部楼层
哈哈哈大雄 发表于 2015-9-20 01:37. Waral 博客有更多文章,
这个题,把所有线段的起始点和终点排序,然后遍历,设置一个counter,遇到起始点就加1,遇到终点就减1,找c ...
.1point3acres网
仍然是n^2
回复 支持 0 反对 2

使用道具 举报

psychiatrichwj 发表于 2015-8-19 22:31:16 | 显示全部楼层
LZ啥时候去on site?我也昨天收到邮件要on site
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-8-20 00:53:16 | 显示全部楼层
psychiatrichwj 发表于 2015-8-19 22:31.1point3acres网
LZ啥时候去on site?我也昨天收到邮件要on site

暂时准备下周晚点的时候去
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-20 01:12:54 | 显示全部楼层
大陆和海洋是什么题楼主。。。。
count islands那个leetcode原题嘛?
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-8-20 01:23:28 | 显示全部楼层
jiebour 发表于 2015-8-20 01:12.留学论坛-一亩-三分地
大陆和海洋是什么题楼主。。。。
count islands那个leetcode原题嘛?

是的      
回复 支持 反对

使用道具 举报

psychiatrichwj 发表于 2015-8-20 01:57:32 | 显示全部楼层
悲伤网管 发表于 2015-8-20 00:53
暂时准备下周晚点的时候去
.本文原创自1point3acres论坛
Good Luck! 来源一亩.三分地论坛.
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-8-20 03:24:41 | 显示全部楼层

一起加油啊
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-8-20 04:33:58 | 显示全部楼层
哎呀,lz好运气,我刚发了面经,可是通知我不能去onsite。。。。
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-8-20 04:39:29 | 显示全部楼层
hbsophia 发表于 2015-8-20 04:33
哎呀,lz好运气,我刚发了面经,可是通知我不能去onsite。。。。

看了你的帖,估计被老印黑了,继续努力吧
. 1point3acres
回复 支持 反对

使用道具 举报

gl891011 发表于 2015-8-20 04:54:01 | 显示全部楼层
楼主是new grad吗?.1point3acres网


补充内容 (2015-8-20 04:55):. 1point 3acres 论坛
投的是full time的new grad职位吗?
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-8-20 04:56:07 | 显示全部楼层
gl891011 发表于 2015-8-20 04:54.留学论坛-一亩-三分地
楼主是new grad吗?

是的            
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-20 05:06:37 | 显示全部楼层
区间覆盖问题, 应该是线段树吧
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-8-20 05:34:43 | 显示全部楼层
暴力解法是不是找出所有起点中的最小值 minstart,找出所有终点的最大值 minend,然后for every integer in the range of [a,b] 看看落在几个区间,用maxcount记录?
这个时间复杂度应该是o(n^2)吧,还有没有更好的方法了呀
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-8-20 05:46:05 | 显示全部楼层
hbsophia 发表于 2015-8-20 05:34
暴力解法是不是找出所有起点中的最小值 minstart,找出所有终点的最大值 minend,然后for every integer in ...

是这样的,我听错了题,相当于花了很多时间做另一道题,搞清题意的之后只有5分钟不到了,线段树应该是nlogn吧
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-11 10:55:26 | 显示全部楼层
hbsophia 发表于 2015-8-20 05:34
暴力解法是不是找出所有起点中的最小值 minstart,找出所有终点的最大值 minend,然后for every integer in ...

线段树

class Solution2 {
        class Interval {
                int sta;
                int end;.本文原创自1point3acres论坛
                public Interval(int sta, int end) {
                        this.sta = sta;
                        this.end = end;
                }
        }
        来源一亩.三分地论坛.
        class SegmentTreeNode {
                int sta;
                int end;
                int cnt;
                SegmentTreeNode left, right;
                public SegmentTreeNode(int sta, int end) {
                        this.sta = sta;. From 1point 3acres bbs
                        this.end = end;
                        left = null;
                        right = null;
                }
        }
       
        private SegmentTreeNode buildST(int sta, int end) {
                if (sta > end) {
                        return null;
                }-google 1point3acres
                if (sta == end) {
                        return new SegmentTreeNode(sta, end);
                }
                int mid = (sta+end)/2;
                SegmentTreeNode midNode = new SegmentTreeNode(sta, end);
                midNode.left = buildST(sta, mid);
                midNode.right = buildST(mid+1, end);
                return midNode;
        }. visit 1point3acres for more.
       
        SegmentTreeNode root = null;. more info on 1point3acres
        int maxNum = 0;
        .留学论坛-一亩-三分地
        private void updateST(SegmentTreeNode root, int sta, int end, HashMap<Integer, Integer> hash) {
                if (root.sta == sta && root.end == end && sta == end) {
                        root.cnt++;
                        if (root.cnt > maxNum) {
                                maxNum = root.cnt;
                        }
                        hash.put(root.sta, root.cnt);
                        return;
                }
                int mid = (root.sta+root.end)/2;
                if (end <= mid) {
                        updateST(root.left, sta, end, hash);. 围观我们@1point 3 acres
                }. visit 1point3acres for more.
                else if (sta > mid) {
                        updateST(root.right, sta, end, hash);
                }
                else {
                        updateST(root.left, sta, mid, hash);
                        updateST(root.right, mid+1, end, hash);
                }. Waral 博客有更多文章,
                //root.cnt = root.left.cnt+root.right.cnt;
        }
       
        public List<Integer> getmax(Interval[] num) {
                HashMap<Integer, Integer> hash = new HashMap<>();
                int min = num[0].sta, max = num[0].end;
                for (int i = 1; i < num.length; i++) {
-google 1point3acres                        if (num.sta < min) {
                                min = num.sta;
                        }. 围观我们@1point 3 acres
                        if (num.end > max) {. 一亩-三分-地,独家发布
                                max = num.end;. more info on 1point3acres
                        }
                }
                root = buildST(min, max);
                for (int i = 0; i < num.length; i++) {
                        updateST(root, num.sta, num.end, hash);
                }. 一亩-三分-地,独家发布
                Set<Integer> key = hash.keySet();
                List<Integer> res = new LinkedList<>();
                for (int x: key) {
                        if (hash.get(x) == maxNum) {
                                res.add(x);
                        }
                }
                return res;
        }
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-11 12:05:20 | 显示全部楼层
hbsophia 发表于 2015-8-20 05:34. 牛人云集,一亩三分地
暴力解法是不是找出所有起点中的最小值 minstart,找出所有终点的最大值 minend,然后for every integer in ...

看到上面有人提到线段树就没多想了。。直接设置一个hashmap,从min到max,然后遍历一遍区间,给这个区间内的数的hash value加1,返回最大数量,应该是O(n)吧
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-11 13:24:30 | 显示全部楼层
hj867955629 发表于 2015-9-11 12:05
看到上面有人提到线段树就没多想了。。直接设置一个hashmap,从min到max,然后遍历一遍区间,给这个区间 ...

好方法,只是要是有一个区间,比如[3,100000]这种,岂不是要把中间的每一个integer 都放hashmap, 岂不是hashmap会很大?

多谢讨论
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-11 14:10:57 | 显示全部楼层
hbsophia 发表于 2015-9-11 13:24
好方法,只是要是有一个区间,比如[3,100000]这种,岂不是要把中间的每一个integer 都放hashmap, 岂不 ...
. Waral 博客有更多文章,
就是空间换时间嘛,要是遍历,也得从3遍历到100000的每个数,看在各个区间的个数对吧
回复 支持 反对

使用道具 举报

哈哈哈大雄 发表于 2015-9-20 01:37:05 | 显示全部楼层
这个题,把所有线段的起始点和终点排序,然后遍历,设置一个counter,遇到起始点就加1,遇到终点就减1,找counter的最大值就可以了。注意排序的时候,如果一个起始点和一个终点的值相同,起始点放前面。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-21 00:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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