一亩三分地论坛

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

Facebook 第一轮电面

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

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

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

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

x
刚面完FB 电面第一轮,考了两道题:
1. 整数的幂: power(a, b), a >=0, b>= 0;
   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 | 显示全部楼层
第二题楼主能贴个代码吗. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

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

使用道具 举报

kobe24 发表于 2016-10-5 08:30:01 | 显示全部楼层
liujiajunwin 发表于 2016-10-5 07:29
第二题感觉像是跟LC 218 Skyline的那个有点像啊,把所有range的边界sort一下,用一个stack存储边界,遍历所 ...

每次有变化时统计有range最多的那个? are you explain some more details? thanks
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

pineapple1985 发表于 2016-10-5 08:57:43 来自手机 | 显示全部楼层
iPhD 发表于 2016-10-5 08:38
第二题是把起点和终点分成两个数组,然后用一个count,遇到起点就+1,遇到终点就-1,这样做吗?

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;. 1point3acres.com/bbs
  3.         int max = Integer.MIN_VALUE;
  4.         for (int[] range : ranges) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  5.             shift = Math.min(shift, range[0]); . visit 1point3acres.com for more.
  6.             max = Math.max(max, range[1]);  
  7.         }
  8.         int len = max - shift + 1;
  9.         int[] sum = new int[len + 1];
  10.         for (int[] range : ranges) {
  11.             sum[range[0] - shift]++;
    . 1point 3acres 璁哄潧
  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];. visit 1point3acres.com for more.
  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;
  4.         sort(ranges.begin(),ranges.end());
  5.         int start=0;
  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){
  15.                         if(i-start>count){
  16.                                 res=tmp;
  17.                                 count=i-start;
  18.                         }
  19.                 }
  20.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.         if(res==INT_MAX)
    . 1point 3acres 璁哄潧
  22.                 return maxStart;
  23.         return res;
  24. }
复制代码




补充内容 (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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.         for(int i = 0; i < l; i++){. Waral 鍗氬鏈夋洿澶氭枃绔,
  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]);-google 1point3acres
  12.         }
  13.         return res_max;
  14. }
复制代码
最小堆应该可以吧? 如果返回其中一个int而不是所有的话。。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

minggr 发表于 2016-10-10 14:21:37 | 显示全部楼层
第二题:
. 1point3acres.com/bbs
google: Find the point where maximum intervals overlap

max_overlapping(vector<pair<int, int>> &ranges)
{
    int n = (int)ranges.size();
. more info on 1point3acres.com
    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());
. From 1point 3acres bbs
    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--;
        }
    }

    return result;. 鍥磋鎴戜滑@1point 3 acres
}

int main()
{
    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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
好像不太一样?这个题是求重叠的点的index, meeting room II求的是最大的被重叠次数

在找到最大重叠次数的时候,顺便存一下index呗?好像可以吧。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-15 12:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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