《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 5753|回复: 24
收起左侧

FB 电面

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

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

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

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

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

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

这次运气好,碰上一个友好的白人,第二天收到通知水过了
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
求人品求offer!. from: 1point3acres.com/bbs
共勉大家

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · Facebook|主题: 516, 订阅: 172
  • · fb|主题: 33, 订阅: 16
 楼主| 悲伤网管 发表于 2015-9-20 01:52:51 | 显示全部楼层
哈哈哈大雄 发表于 2015-9-20 01:37
这个题,把所有线段的起始点和终点排序,然后遍历,设置一个counter,遇到起始点就加1,遇到终点就减1,找c ...
. From 1point 3acres bbs
仍然是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
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原题嘛?

是的      
回复 支持 反对

使用道具 举报

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

Good Luck!
回复 支持 反对

使用道具 举报

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

一起加油啊
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| 悲伤网管 发表于 2015-8-20 04:39:29 | 显示全部楼层
hbsophia 发表于 2015-8-20 04:33. from: 1point3acres.com/bbs
哎呀,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 ...
. 1point 3acres 璁哄潧
是这样的,我听错了题,相当于花了很多时间做另一道题,搞清题意的之后只有5分钟不到了,线段树应该是nlogn吧
回复 支持 反对

使用道具 举报

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

线段树

class Solution2 {. visit 1point3acres.com for more.
        class Interval {
                int sta;
                int end;
                public Interval(int sta, int end) {
                        this.sta = sta;. more info on 1point3acres.com
                        this.end = end;. 1point 3acres 璁哄潧
                }
        }
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷       
        class SegmentTreeNode {. Waral 鍗氬鏈夋洿澶氭枃绔,
                int sta;
                int end;
                int cnt;
                SegmentTreeNode left, right;
                public SegmentTreeNode(int sta, int end) {
                        this.sta = sta;
                        this.end = end;
                        left = null;
                        right = null;
                }
. visit 1point3acres.com for more.        }
       
        private SegmentTreeNode buildST(int sta, int end) {
                if (sta > end) {
                        return null;
                }
                if (sta == end) {
                        return new SegmentTreeNode(sta, end);. 1point 3acres 璁哄潧
                }
                int mid = (sta+end)/2;. 1point 3acres 璁哄潧
                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;.1point3acres缃
        . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        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;. 鍥磋鎴戜滑@1point 3 acres
                        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        hash.put(root.sta, root.cnt);. 鍥磋鎴戜滑@1point 3 acres
                        return;
                }
                int mid = (root.sta+root.end)/2;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                if (end <= mid) {
                        updateST(root.left, sta, end, hash);
                }. more info on 1point3acres.com
                else if (sta > mid) {
                        updateST(root.right, sta, end, hash);
                }. visit 1point3acres.com for more.
                else {
                        updateST(root.left, sta, mid, hash);
                        updateST(root.right, mid+1, end, hash);
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴                }
                //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++) {
                        if (num.sta < min) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                                min = num.sta;
                        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        if (num.end > max) {. 1point 3acres 璁哄潧
                                max = num.end;
                        }
                }. Waral 鍗氬鏈夋洿澶氭枃绔,
                root = buildST(min, max);-google 1point3acres
                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) {. visit 1point3acres.com for more.
                        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, 岂不 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
就是空间换时间嘛,要是遍历,也得从3遍历到100000的每个数,看在各个区间的个数对吧
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-21 10:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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