到底为啥那么多人转Data Science

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
[Google级团队]
实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 5204|回复: 20
收起左侧

Facebook 第一轮电面

[复制链接] |试试Instant~ |关注本帖
stilltracy 发表于 2016-10-5 07:13:10 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类General 博士 实习@Facebook - 内推 - 技术电面  | Other | 其他

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

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

x
刚面完FB 电面第一轮,考了两道题:.鐣欏璁哄潧-涓浜-涓夊垎鍦
1. 整数的幂: power(a, b), a >=0, b>= 0;. 1point3acres.com/bbs
   follow on: 在log(b) 复杂度内实现;
2. Given a vector of ranges, return the integer that intersects with the most number of ranges.  
e.g.: func ([ [-1, 2], [0,0], [1,1] ] ) == 0 | 1

第一道题做得还凑合,第二道题在面试官提示下才勉强做出,唉。
iPhD 发表于 2016-10-5 08:38:00 | 显示全部楼层
第二题是把起点和终点分成两个数组,然后用一个count,遇到起点就+1,遇到终点就-1,这样做吗?
回复 支持 1 反对 0

使用道具 举报

kobe24 发表于 2016-10-5 07:27:34 | 显示全部楼层
第二题楼主能贴个代码吗
回复 支持 反对

使用道具 举报

头像被屏蔽
liujiajunwin 发表于 2016-10-5 07:29:59 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-10-5 08:30:01 | 显示全部楼层
liujiajunwin 发表于 2016-10-5 07:29. visit 1point3acres.com for more.
第二题感觉像是跟LC 218 Skyline的那个有点像啊,把所有range的边界sort一下,用一个stack存储边界,遍历所 ...
. 鍥磋鎴戜滑@1point 3 acres
每次有变化时统计有range最多的那个? are you explain some more details? thanks
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-10-5 08:54:02 | 显示全部楼层
iPhD 发表于 2016-10-5 08:38.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二题是把起点和终点分成两个数组,然后用一个count,遇到起点就+1,遇到终点就-1,这样做吗?

能具体点吗大神?
回复 支持 反对

使用道具 举报

pineapple1985 发表于 2016-10-5 08:57:43 来自手机 | 显示全部楼层
iPhD 发表于 2016-10-5 08:38
第二题是把起点和终点分成两个数组,然后用一个count,遇到起点就+1,遇到终点就-1,这样做吗?
. Waral 鍗氬鏈夋洿澶氭枃绔,
Bingo!! 就是leetcode的一道变种题
回复 支持 反对

使用道具 举报

海盗包子 发表于 2016-10-5 10:01:37 | 显示全部楼层
第二题是leetcode 370 Range Addition 的变种吧, 需要先记录一个最小值作为偏移量
回复 支持 反对

使用道具 举报

海盗包子 发表于 2016-10-5 10:13:24 | 显示全部楼层
写了一下第二题,请大家帮忙看下~. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  1. public int mostNumber(int[][] ranges) {
  2.         int shift = Integer.MAX_VALUE;
  3.         int max = Integer.MIN_VALUE;
  4.         for (int[] range : ranges) {
  5.             shift = Math.min(shift, range[0]);
  6.             max = Math.max(max, range[1]);  
  7.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8.         int len = max - shift + 1;
  9.         int[] sum = new int[len + 1];. from: 1point3acres.com/bbs
  10.         for (int[] range : ranges) {
  11.             sum[range[0] - shift]++;
  12.             sum[range[1] - shift + 1]--;   
  13.         }
  14.         int most = 0, cur = 0, val = 0;
  15.         for(int i = 0; i < sum.length; i++) {
  16.             cur += sum[i];
  17.             if(cur > most) {
  18.                 most = cur;
  19.                 val = i + shift;
  20.             }
  21.         }
  22.         return val;
  23.     }
复制代码
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-10-5 13:07:47 | 显示全部楼层
第二题是不是count frequency啊?
回复 支持 反对

使用道具 举报

xiangmo 发表于 2016-10-6 09:28:51 | 显示全部楼层
感觉第二题就是当maxStart>minEnd的时候更新一下结果吧?不知道对错呀
  1. int solve(vector<pair<int,int>> &ranges){
  2.         if(ranges.empty())
  3.                 return INT_MAX;. more info on 1point3acres.com
  4.         sort(ranges.begin(),ranges.end());
  5.         int start=0;. 鍥磋鎴戜滑@1point 3 acres
  6.         int res=INT_MAX;
  7.         int count=0;
  8.         int maxStart=INT_MIN;
  9.         int minEnd=INT_MAX;
  10.         for(int i=0;i<ranges.size();i++){
  11.                 int tmp=maxStart;
  12.                 maxStart=max(maxStart,ranges[i].first);
  13.                 minEnd=min(minEnd,ranges[i].second);
  14.                 if(maxStart>minEnd){. visit 1point3acres.com for more.
  15.                         if(i-start>count){
  16.                                 res=tmp;
  17.                                 count=i-start;
  18.                         }.1point3acres缃
  19.                 }.1point3acres缃
  20.         }. 1point3acres.com/bbs
  21.         if(res==INT_MAX)
  22.                 return maxStart;
  23.         return res;
  24. }
复制代码

. 鍥磋鎴戜滑@1point 3 acres

.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-10-6 09:30):
然后再更新一下start的位置为i。。忘记写了。。

补充内容 (2016-10-6 09:32):
然后更新下maxstart,minend,start,count..
回复 支持 反对

使用道具 举报

xiangmo 发表于 2016-10-6 09:45:36 | 显示全部楼层
xiangmo 发表于 2016-10-6 09:28
感觉第二题就是当maxStart>minEnd的时候更新一下结果吧?不知道对错呀

突然发现地下室就是正解!因为必定是开始或结尾的元素为返回值!!
回复 支持 反对

使用道具 举报

TheBlackMamba 发表于 2016-10-6 11:20:37 | 显示全部楼层
  1. int func(vector<pair<int, int> > v){
  2.         sort(v.begin(), v.end());
  3.         int l = v.size();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4.         priority_queue<int, vector<int>, greater<int> > pq;
  5.         int res_max = 0;
  6.         for(int i = 0; i < l; i++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.                 while(!pq.empty() && v[i].first > pq.top()){
  8.                         pq.pop();
  9.                 }
  10.                 pq.push(v[i].second);
  11.                 res_max = max(res_max, m[v[i].first]);
  12.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.         return res_max;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14. }
复制代码
最小堆应该可以吧? 如果返回其中一个int而不是所有的话。。。
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-10-10 13:04:23 | 显示全部楼层
由feedback了么?是不是被问2题比较有希望。。。我才被问了一道。。。
回复 支持 反对

使用道具 举报

minggr 发表于 2016-10-10 14:21:37 | 显示全部楼层
第二题:

google: Find the point where maximum intervals overlap
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
max_overlapping(vector<pair<int, int>> &ranges)
{
    int n = (int)ranges.size();. 鍥磋鎴戜滑@1point 3 acres
. from: 1point3acres.com/bbs
    vector<int> start, end;

    for (auto p: ranges) {
        start.push_back(p.first);
        end.push_back(p.second);
    }

    sort(start.begin(), start.end());
    sort(end.begin(), end.end());

    int count = 0, max_count = 0;
    int i = 0, j = 0;
    int result = start[0];

    while (i < n && j < n) {
        if (start < end[j]) {
            i++;
            if (++count > max_count) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                max_count = count;
                result = start;
            }
        } else {
            j++;
            count--;. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
    }

    return result;
}

int main(). From 1point 3acres bbs
{
    vector<pair<int,int>> ranges;
    ranges.push_back(make_pair(-1,2));
    ranges.push_back(make_pair(0,0));
    ranges.push_back(make_pair(1,1));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

    cout << max_overlapping(ranges) << endl;
    return 0;
}[/code]
回复 支持 反对

使用道具 举报

forestwn 发表于 2016-10-10 14:53:46 | 显示全部楼层
海盗包子 发表于 2016-10-5 10:13
写了一下第二题,请大家帮忙看下~

注意边界
sum[range[1] - shift + 1].鐣欏璁哄潧-涓浜-涓夊垎鍦
是不是越界了
回复 支持 反对

使用道具 举报

类与对象tju 发表于 2016-10-10 15:00:47 | 显示全部楼层
海盗包子 发表于 2016-10-5 10:13
写了一下第二题,请大家帮忙看下~

和你想的差不多,sum那里减的部分判断下是否越界。end+1 < len
回复 支持 反对

使用道具 举报

LumiG 发表于 2016-10-10 15:19:27 | 显示全部楼层
第二题很多面经里也有吧,leetcode meetroom II。数字范围小开个数组弄,数字范围大弄个最小堆存end。
回复 支持 反对

使用道具 举报

forestwn 发表于 2016-10-10 15:44:15 | 显示全部楼层
LumiG 发表于 2016-10-10 15:19
第二题很多面经里也有吧,leetcode meetroom II。数字范围小开个数组弄,数字范围大弄个最小堆存end。

好像不太一样?这个题是求重叠的点的index, meeting room II求的是最大的被重叠次数
回复 支持 反对

使用道具 举报

LumiG 发表于 2016-10-11 03:40:35 | 显示全部楼层
forestwn 发表于 2016-10-10 15:44. from: 1point3acres.com/bbs
好像不太一样?这个题是求重叠的点的index, meeting room II求的是最大的被重叠次数
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
在找到最大重叠次数的时候,顺便存一下index呗?好像可以吧。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-4-25 15:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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