一亩三分地论坛

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

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

Facebook 第一轮电面

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

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

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

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

x
刚面完FB 电面第一轮,考了两道题:
1. 整数的幂: power(a, b), a >=0, b>= 0;
   follow on: 在log(b) 复杂度内实现;.1point3acres缃
2. Given a vector of ranges, return the integer that intersects with the most number of ranges.  . From 1point 3acres bbs
e.g.: func ([ [-1, 2], [0,0], [1,1] ] ) == 0 | 1. Waral 鍗氬鏈夋洿澶氭枃绔,

第一道题做得还凑合,第二道题在面试官提示下才勉强做出,唉。
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 | 显示全部楼层
第二题感觉像是跟LC 218 Skyline的那个有点像啊,把所有range的边界sort一下,用一个stack存储边界,遍历所有的边界,碰到左边界入栈右边界出栈,每次有变化时统计有range最多的那个
回复 支持 反对

使用道具 举报

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;
  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];
  10.         for (int[] range : ranges) {
  11.             sum[range[0] - shift]++;
  12.             sum[range[1] - shift + 1]--;   
  13.         }-google 1point3acres
  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;
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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;
    . 1point 3acres 璁哄潧
  17.                                 count=i-start;
  18.                         }
  19.                 }
  20.         }
  21.         if(res==INT_MAX)
  22.                 return maxStart;. 1point 3acres 璁哄潧
  23.         return res;
  24. }
复制代码
.鐣欏璁哄潧-涓浜-涓夊垎鍦



补充内容 (2016-10-6 09:30):
然后再更新一下start的位置为i。。忘记写了。。

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

使用道具 举报

xiangmo 发表于 2016-10-6 09:45:36 | 显示全部楼层
xiangmo 发表于 2016-10-6 09:28. visit 1point3acres.com for more.
感觉第二题就是当maxStart>minEnd的时候更新一下结果吧?不知道对错呀
. 鍥磋鎴戜滑@1point 3 acres
突然发现地下室就是正解!因为必定是开始或结尾的元素为返回值!!
回复 支持 反对

使用道具 举报

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;. more info on 1point3acres.com
  6.         for(int i = 0; i < l; i++){
  7.                 while(!pq.empty() && v[i].first > pq.top()){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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();. more info on 1point3acres.com

    vector<int> start, end;
.鏈枃鍘熷垱鑷1point3acres璁哄潧
    for (auto p: ranges) {
        start.push_back(p.first); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        end.push_back(p.second);
    }-google 1point3acres

    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) {. From 1point 3acres bbs
        if (start < end[j]) {
            i++;. Waral 鍗氬鏈夋洿澶氭枃绔,
            if (++count > max_count) {
                max_count = count;
                result = start;
            }. 1point 3acres 璁哄潧
        } else {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            j++;
            count--;
        }
    }

    return result;
}

int main()
{
    vector<pair<int,int>> ranges;. more info on 1point3acres.com
    ranges.push_back(make_pair(-1,2));
    ranges.push_back(make_pair(0,0));
    ranges.push_back(make_pair(1,1));
. visit 1point3acres.com for more.
    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].鏈枃鍘熷垱鑷1point3acres璁哄潧
是不是越界了
回复 支持 反对

使用道具 举报

类与对象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呗?好像可以吧。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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