一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3398|回复: 24
收起左侧

FB 电面

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

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

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

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

x
上周面的,内推两周后hr联系. Waral 鍗氬鏈夋洿澶氭枃绔,

第一题 大陆和海洋
第二题 在一些区间中,寻找一个点,使这个点能够落入尽量多的区间,提示我用暴力解法
           比如 区间: 2,3 | 3,5 | 4,5 | 1,5 | 1,2         那么4和5都是答案 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

这次运气好,碰上一个友好的白人,第二天收到通知水过了

求人品求offer!. 1point 3acres 璁哄潧
共勉大家.1point3acres缃

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
 楼主| 悲伤网管 发表于 2015-9-20 01:52:51 | 显示全部楼层
哈哈哈大雄 发表于 2015-9-20 01:37
这个题,把所有线段的起始点和终点排序,然后遍历,设置一个counter,遇到起始点就加1,遇到终点就减1,找c ...

仍然是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
大陆和海洋是什么题楼主。。。。
. 1point 3acres 璁哄潧count islands那个leetcode原题嘛?
. 鍥磋鎴戜滑@1point 3 acres
是的      
回复 支持 反对

使用道具 举报

psychiatrichwj 发表于 2015-8-20 01:57:32 | 显示全部楼层
悲伤网管 发表于 2015-8-20 00:53
暂时准备下周晚点的时候去

Good Luck!
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-8-20 03:24:41 | 显示全部楼层
psychiatrichwj 发表于 2015-8-20 01:57-google 1point3acres
Good Luck!

一起加油啊
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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


补充内容 (2015-8-20 04:55):
投的是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 ...
. more info on 1point3acres.com
是这样的,我听错了题,相当于花了很多时间做另一道题,搞清题意的之后只有5分钟不到了,线段树应该是nlogn吧
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-11 10:55:26 | 显示全部楼层
hbsophia 发表于 2015-8-20 05:34
暴力解法是不是找出所有起点中的最小值 minstart,找出所有终点的最大值 minend,然后for every integer in ...
. 鍥磋鎴戜滑@1point 3 acres
线段树

class Solution2 {
        class Interval {
                int sta;
                int end;
                public Interval(int sta, int end) {
                        this.sta = sta;
                        this.end = end;
                }
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
       
        class SegmentTreeNode {. 1point3acres.com/bbs
                int sta;. more info on 1point3acres.com
                int end; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                int cnt;
                SegmentTreeNode left, right;
                public SegmentTreeNode(int sta, int end) {
                        this.sta = sta;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        this.end = end;
                        left = null;
                        right = null;
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }
       
        private SegmentTreeNode buildST(int sta, int end) {
                if (sta > end) {. 1point 3acres 璁哄潧
                        return null;
                }
                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;
        }
       
        SegmentTreeNode root = null;
        int maxNum = 0;
       
        private void updateST(SegmentTreeNode root, int sta, int end, HashMap<Integer, Integer> hash) {. visit 1point3acres.com for more.
                if (root.sta == sta && root.end == end && sta == end) {
                        root.cnt++;
                        if (root.cnt > maxNum) {.1point3acres缃
                                maxNum = root.cnt;
                        }
                        hash.put(root.sta, root.cnt);
                        return;
                }
                int mid = (root.sta+root.end)/2;. 1point 3acres 璁哄潧
                if (end <= mid) {
                        updateST(root.left, sta, end, hash);
                }
                else if (sta > mid) {. From 1point 3acres bbs
                        updateST(root.right, sta, end, hash);
                }
                else {
                        updateST(root.left, sta, mid, hash);
                        updateST(root.right, mid+1, end, hash);
                }
-google 1point3acres                //root.cnt = root.left.cnt+root.right.cnt;-google 1point3acres
        }
       
        public List<Integer> getmax(Interval[] num) {. 1point 3acres 璁哄潧
                HashMap<Integer, Integer> hash = new HashMap<>();
                int min = num[0].sta, max = num[0].end;
                for (int i = 1; i < num.length; i++) {
                        if (num.sta < min) {-google 1point3acres
                                min = num.sta;
                        }
                        if (num.end > max) {
                                max = num.end;
                        }
                }
                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,然后遍历一遍区间,给这个区间 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
好方法,只是要是有一个区间,比如[3,100000]这种,岂不是要把中间的每一个integer 都放hashmap, 岂不是hashmap会很大?

多谢讨论
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-11 14:10:57 | 显示全部楼层
hbsophia 发表于 2015-9-11 13:24
好方法,只是要是有一个区间,比如[3,100000]这种,岂不是要把中间的每一个integer 都放hashmap, 岂不 ...

就是空间换时间嘛,要是遍历,也得从3遍历到100000的每个数,看在各个区间的个数对吧
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 22:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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