Facebook 第一轮电面

刚面完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

第一道题做得还凑合，第二道题在面试官提示下才勉强做出，唉。

第二题是把起点和终点分成两个数组，然后用一个count，遇到起点就＋1，遇到终点就－1，这样做吗？

第二题楼主能贴个代码吗

第二题感觉像是跟LC 218 Skyline的那个有点像啊，把所有range的边界sort一下，用一个stack存储边界，遍历所有的边界，碰到左边界入栈右边界出栈，每次有变化时统计有range最多的那个

liujiajunwin 发表于 2016-10-5 07:29
第二题感觉像是跟LC 218 Skyline的那个有点像啊，把所有range的边界sort一下，用一个stack存储边界，遍历所 ...

每次有变化时统计有range最多的那个? are you explain some more details? thanks

iPhD 发表于 2016-10-5 08:38
第二题是把起点和终点分成两个数组，然后用一个count，遇到起点就＋1，遇到终点就－1，这样做吗？

能具体点吗大神？

iPhD 发表于 2016-10-5 08:38
第二题是把起点和终点分成两个数组，然后用一个count，遇到起点就＋1，遇到终点就－1，这样做吗？

Bingo!! 就是leetcode的一道变种题

第二题是leetcode 370 Range Addition 的变种吧， 需要先记录一个最小值作为偏移量

写了一下第二题，请大家帮忙看下～

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.         }
    
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.     }

复制代码

第二题是不是count frequency啊?

感觉第二题就是当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)
    
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:28
感觉第二题就是当maxStart>minEnd的时候更新一下结果吧？不知道对错呀

突然发现地下室就是正解！因为必定是开始或结尾的元素为返回值！！

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++){
   
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而不是所有的话。。。

由feedback了么？是不是被问2题比较有希望。。。我才被问了一道。。。

第二题：

google: Find the point where maximum intervals overlap

max_overlapping(vector<pair<int, int>> &ranges)
{
    int n = (int)ranges.size();

    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--;
        }
    }

    return result;
}

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]

海盗包子 发表于 2016-10-5 10:13
写了一下第二题，请大家帮忙看下～

注意边界
sum[range[1] - shift + 1]
是不是越界了

海盗包子 发表于 2016-10-5 10:13
写了一下第二题，请大家帮忙看下～

和你想的差不多，sum那里减的部分判断下是否越界。end+1 < len

第二题很多面经里也有吧，leetcode meetroom II。数字范围小开个数组弄，数字范围大弄个最小堆存end。

LumiG 发表于 2016-10-10 15:19
第二题很多面经里也有吧，leetcode meetroom II。数字范围小开个数组弄，数字范围大弄个最小堆存end。

好像不太一样？这个题是求重叠的点的index， meeting room II求的是最大的被重叠次数

forestwn 发表于 2016-10-10 15:44
好像不太一样？这个题是求重叠的点的index， meeting room II求的是最大的被重叠次数

在找到最大重叠次数的时候，顺便存一下index呗？好像可以吧。