一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 7519|回复: 50
收起左侧

facebook 二面题目求解题思路

[复制链接] |试试Instant~ |关注本帖
primbo 发表于 2016-3-12 09:05:46 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
interval [startTime, stoptime)   ----integral  time stamps
给这样的一串区间 I1, I2......In  
找出 一个 time stamp  出现在interval的次数最多。
startTime <= t< stopTime 代表这个数在区间里面出现过。

example:  [1,3),  [2, 7),   [4,  8),   [5, 9)
5和6各出现了三次, 所以答案返回5,6。
有没有大神有思路 求指导

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-3-13 03:47):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
具体代码参照后面。meeting room 变形。

评分

2

查看全部评分

emmarong 发表于 2016-3-12 13:35:45 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这题就是LC上面的meeting rooms换了马甲。meeting rooms求最少需要多少个room,也就是某个时刻有几个并行的会议,这个题目求时刻有最大的并行interval数量,差不多,按照start time排一遍,再用一个heap放结束时间就可以了。贴个python版本的:

  1. import heapq
  2. def integraltimestamps2(intervals):
  3.     intvs = sorted(intervals, key = lambda x : x[0])
  4.     edges = sorted([intv[0] for intv in intervals]+[intv[1] for intv in intervals])
  5.     results = []
  6.     moccurs = 0
  7.     ongoing = []
  8.     intvid = 0
  9.     for e in edges:
  10.         if results and len(ongoing) == moccurs:
  11.             results += range(results[-1]+1,e)
  12.         while ongoing and e >= ongoing[0]:
  13.             heapq.heappop(ongoing)
  14.         while intvid < len(intvs) and e >= intvs[intvid][0]:. 鍥磋鎴戜滑@1point 3 acres
  15.             heapq.heappush(ongoing, intvs[intvid][1])
  16.             intvid += 1
  17.         if len(ongoing) > moccurs:
  18.             moccurs = len(ongoing)
  19.             results = [e]. more info on 1point3acres.com
  20.         elif len(ongoing) == moccurs:
  21.             results.append(e)
  22.     return results
复制代码
回复 支持 4 反对 0

使用道具 举报

xutopia 发表于 2016-3-12 10:22:40 | 显示全部楼层
关注一亩三分地微博:
Warald
把所有的startTime和stopTime排序过一遍。碰到start当前interval数+1,否则-1,算出最大的interval overlap数。接下来具体最多的overlap在哪里也很容易找吧
回复 支持 2 反对 0

使用道具 举报

何打发123 发表于 2016-7-27 07:23:16 | 显示全部楼层
感谢楼主分享~~ 自己写了一个 大概思路是记录到了每一点目前有的interval的数量 各位求指正~~
  1. import java.util.*;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  2. . From 1point 3acres bbs
  3. class Interval{
  4.         int start, end;
  5.         public Interval(int s, int e){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.                 start = s;
  7.                 end = e;
  8.         }
  9. }

  10. class Point{-google 1point3acres
  11.         int time;
  12.         boolean flag;
  13.         Interval interval;
  14.         public Point(int t, boolean f, Interval i){
  15.                 time = t;
  16.                 flag = f;. 鍥磋鎴戜滑@1point 3 acres
  17.                 interval = i;
  18.         }
  19. }

  20. class myComparator implements Comparator<Point>{.鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.         public int compare(Point i1, Point i2){. 1point 3acres 璁哄潧
  22.                 if(i1.time == i2.time){
  23.                         //finish first
  24.                         if(!i1.flag && i2.flag){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  25.                                 return -1;
  26.                         }else return 1;
  27.                 }
  28.                 return i1.time - i2.time;
  29.         }.1point3acres缃
  30. }

  31. class Solution {
  32.         public ArrayList<Integer> scheduel(ArrayList<Interval> arr){
  33.                 ArrayList<Integer> res = new ArrayList<Integer>();
  34.                 if(arr == null || arr.size() == 0) return res;
  35.                 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  36.                 ArrayList<Point> pointList = new ArrayList<Point>();
  37.                
  38.                 for(int i = 0; i < arr.size(); i++){. 1point 3acres 璁哄潧
  39.                         Interval cur = arr.get(i);. From 1point 3acres bbs
  40.                         Point startPoint = new Point(cur.start, true, cur); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  41.                         Point endPoint = new Point(cur.end, false, cur);. 1point3acres.com/bbs
  42.                         pointList.add(startPoint);
  43.                         pointList.add(endPoint);. more info on 1point3acres.com
  44.                 }
  45.                
  46.                 //sort as start time. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  47.                 Collections.sort(pointList, new myComparator());
  48.                
  49.                 ArrayList<Interval> maxIntervalList = new ArrayList<Interval>();
  50.                 int max = 0, num = 0;
  51.                 for(Point p : pointList){
  52.                         if(p.flag == true){
  53.                                 num++;
  54.                                 if(num >= max){
  55.                                         if(num > max){. visit 1point3acres.com for more.
  56.                                                 maxIntervalList.clear();. 1point 3acres 璁哄潧
  57.                                         }
  58.                                        
  59.                                         max = num;
  60.                                         Interval x = new Interval(p.time, p.time);
  61.                                         maxIntervalList.add(x);
  62.                                 }
  63.                         }else{
  64.                                 if(num == max){
  65.                                         Interval lastInterval = maxIntervalList.get
  66.                                         (maxIntervalList.size() - 1);
  67.                                         lastInterval.end = p.time;
  68.                                 }
    . 鍥磋鎴戜滑@1point 3 acres
  69.                                 num--;
  70.                         }
  71.                 }
  72.                 for(Interval temp : maxIntervalList){
  73.                         for(int moment = temp.start; moment < temp.end; moment++){. Waral 鍗氬鏈夋洿澶氭枃绔,
  74.                                 res.add(moment);
  75.                         }
  76.                 }
  77.                 return res;
  78.         }
  79.         . visit 1point3acres.com for more.
  80.         public static void main(String[] args) {
  81.                 Solution r = new Solution();
  82.                 Interval a = new Interval(2,7);
  83.                 Interval b = new Interval(1,3);
  84.                 Interval c = new Interval(4,8);
  85.                 Interval d = new Interval(5,9);
  86.                 Interval f = new Interval(7,9);
  87.                
  88.                 ArrayList<Interval> res = new ArrayList<Interval>();
  89.                 res.addAll(Arrays.asList(a, b, c, d, f));
  90.                 ArrayList<Integer> m = r.scheduel(res);       
  91.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  92.                 for(Integer k : m){
  93.                         System.out.println(k);
  94.                 }
  95.         }
  96.                
  97. }
复制代码
回复 支持 1 反对 0

使用道具 举报

guschen802 发表于 2016-3-12 09:17:48 | 显示全部楼层
一個很蠢的思路。準備一個數組,大小是。。End_MAX - Start_MIN -1; 然後每個區間的跑一遍。。在數組里計數,最後返回計數最高的數據。時間應該是O(mn),(m = AVG interval length, n = interval count), 空間O(n) n是範圍跨度的長度

补充内容 (2016-3-12 09:18):
應該有更好的做法吧?求大神、
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

guschen802 发表于 2016-3-12 09:32:08 | 显示全部楼层
又想了一個,merge interval 變形, merge的部分,也就是重疊的部分,用hashmap計數,最後返回map最高的,寫看看代碼,等會上
回复 支持 反对

使用道具 举报

guschen802 发表于 2016-3-12 09:53:41 | 显示全部楼层
  1. public class Solution {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2.     public static void main(String[] args) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  3.         List <Interval> list = new ArrayList<>();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4.         list.add(new Interval(1,3));
  5.         list.add(new Interval(2,7));
  6.         list.add(new Interval(4,8));
  7.         list.add(new Interval(5,9));
  8.         List<Integer> result = findMost(list);. 1point3acres.com/bbs
  9.         for (Integer it : result) {
  10.             System.out.println(it);
  11.         }. 鍥磋鎴戜滑@1point 3 acres
  12.     }
  13. . 1point3acres.com/bbs
  14.     public static List<Integer> findMost(List <Interval> intervals) {
  15.         //assume intervals sorted. more info on 1point3acres.com
  16.         List<Integer> result = new ArrayList<>();. visit 1point3acres.com for more.
  17.         if (intervals == null || intervals.size() == 0) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18.             return result;. visit 1point3acres.com for more.
  19. . From 1point 3acres bbs
  20.         Map<Integer, Integer> map = new HashMap<>();
  21.         List <Interval> newIntervals = new ArrayList<>();//merged list
  22.         newIntervals.add(intervals.get(0));
  23.         for (int i = 1; i < intervals.size(); i++) {
  24.             Interval pre = newIntervals.get(newIntervals.size() -1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  25.             Interval cur = intervals.get(i);
  26.             int s = -1, e = -1;//overlap interval
  27.             if (cur.start < pre.end) {
  28.                 s = cur.start;
  29.             } else {
  30.                 newIntervals.add(cur);
  31.                 continue;
  32.             }
  33.             if (cur.end <= pre.end) {.1point3acres缃
  34.                 e = cur.end;
  35.             } else {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  36.                 e = pre.end;
  37.                 pre.end = cur.end;
  38.             }
  39.             for (int j = s; j < e; j++) {
  40.                 if (map.containsKey(j)) {
  41.                     map.put(j, map.get(j)+1);
  42.                 } else {
  43.                     map.put(j, 2);
  44.                 }
  45.             }
  46.         }

  47.         if (map.size() == 0) {. 鍥磋鎴戜滑@1point 3 acres
  48.             // if no over lap
  49.             for (Interval in : intervals) {
  50.                 for (int i = in.start; i < in.end; i++) {
  51.                     result.add(i);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  52.                 }
  53.             }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  54.             return result;
  55.         } else {
  56.             int max = 0;
  57.             for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
  58.                 if (entry.getValue() > max) {
  59.                     max = entry.getValue();
  60.                     result.clear();
  61.                     result.add(entry.getKey());
  62.                 } else if (entry.getValue() == max) {. from: 1point3acres.com/bbs
  63.                     result.add(entry.getKey());
  64.                 }
  65.             }
  66.         }
  67.         return result;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  68.     }
  69. }

  70. class Interval{-google 1point3acres
  71.     //[ start, end )
  72.     int start;
  73.     int end;

  74.     public Interval(int start, int end) {. From 1point 3acres bbs
  75.         this.start = start;
  76.         this.end = end;
  77.     }. Waral 鍗氬鏈夋洿澶氭枃绔,
  78. }
复制代码

补充内容 (2016-3-12 10:25):
HashMap的空間還能進一步減少,使用TreeMap, 每次有重疊的interval時,取出小於重疊部分之前的數據并計算最大值,這樣能保證總interval很長的時候map不會太大
回复 支持 反对

使用道具 举报

guschen802 发表于 2016-3-12 10:33:59 | 显示全部楼层
xutopia 发表于 2016-3-12 10:22
把所有的startTime和stopTime排序过一遍。碰到start当前interval数+1,否则-1,算出最大的interval overlap ...

可以再清楚點嘛?
回复 支持 反对

使用道具 举报

 楼主| primbo 发表于 2016-3-12 11:17:34 | 显示全部楼层
xutopia 发表于 2016-3-12 10:22
把所有的startTime和stopTime排序过一遍。碰到start当前interval数+1,否则-1,算出最大的interval overlap ...

牛啊,DP的思想。这一遍过的时候就可以不断更新最大的overlap数,同时更新区间。
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-3-12 11:42:46 | 显示全部楼层
另一个思路,如果nlogn 可以用binary index tree.  interval update single query。timestamp 需要离散化,细节得注意。
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-3-12 12:29:56 | 显示全部楼层
Chi2829 发表于 2016-3-12 11:42
另一个思路,如果nlogn 可以用binary index tree.  interval update single query。timestamp 需要离散化, ...

贴个Python binary index tree代码,求code review,求拍。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
class BIT(object):. 1point3acres.com/bbs
    def __init__(self, n):
        self.size = size = n + 1
        self.bit = [0] * size

    def _lowbit(self, x):
        return x & -x

    def add(self, i, val):
        while i < self.size:
            self.bit += val
            i += self._lowbit(i)

    def sum(self, i):
        res = 0. Waral 鍗氬鏈夋洿澶氭枃绔,
        while i > 0:
            res += self.bit
            i -= self._lowbit(i)
        return res


class Solution(object):

    def frequent_timestamp(self, inputs):. visit 1point3acres.com for more.
        result = []
        # assume input is a list of timestamps [start, end]
        stamps = reduce(lambda x, y: x + y, inputs). visit 1point3acres.com for more.
        stamps = sorted(set(stamps))
        # discretize
        time_idx_dict, idx_time_dict = {}, {}
        idx = 0
        for i, time in enumerate(stamps):. 1point 3acres 璁哄潧
            idx += 1
            if i > 0 and time - stamps[i-1] > 1:
                idx_time_dict[idx] = range(stamps[i-1] + 1, time). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                idx += 1
            idx_time_dict[idx] = [time].鏈枃鍘熷垱鑷1point3acres璁哄潧
            time_idx_dict[time] = idx

        bit = BIT(idx)
        for start, end in inputs:
            bit.add(start, 1)
            bit.add(end, -1)
        idxcnts = [bit.sum(i) for i in range(1, idx + 1)]
        maxidx = max(idxcnts)
        for i in range(idx):
            if idxcnts == maxidx:-google 1point3acres
                result += idx_time_dict[i+1]
        return result


if __name__ == "__main__":
    timestamps = [[1, 3],  [2, 7],   [4, 8],   [5, 9]]
    stampcounter = Solution(). visit 1point3acres.com for more.
    print stampcounter.frequent_timestamp(timestamps)

补充内容 (2016-3-12 12:41):
有个小bug,函数的倒数第六行的range应为range(1, idx), 倒数第4行的应该是range(idx-1),因为最大的timestamp永远是取不到的。
回复 支持 反对

使用道具 举报

 楼主| primbo 发表于 2016-3-12 12:32:46 | 显示全部楼层
xutopia 发表于 2016-3-12 10:22
把所有的startTime和stopTime排序过一遍。碰到start当前interval数+1,否则-1,算出最大的interval overlap ...

大神能指导的详细一点儿么?
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-3-12 13:52:11 | 显示全部楼层
emmarong 发表于 2016-3-12 13:35
这题就是LC上面的meeting rooms换了马甲。meeting rooms求最少需要多少个room,也就是某个时刻有几个并行的 ...

&#128077;这个代码很简洁啊!没做过meeting room,但是这么看和skyline也很像!results可能还要去个重。明天好好研究一下!多谢!
回复 支持 反对

使用道具 举报

 楼主| primbo 发表于 2016-3-12 21:48:05 | 显示全部楼层
emmarong 发表于 2016-3-12 13:35
这题就是LC上面的meeting rooms换了马甲。meeting rooms求最少需要多少个room,也就是某个时刻有几个并行的 ...

真是啊。和meeting  room的思路是一样的。最后queue的size就是overlap interval最多的啊!!为啥我没有想到。晕死。但是最后结果要输出重复最多次数的timestamp啊。难道需要拿着这个次数再过一遍么?
回复 支持 反对

使用道具 举报

 楼主| primbo 发表于 2016-3-12 21:48:17 | 显示全部楼层
emmarong 发表于 2016-3-12 13:35
这题就是LC上面的meeting rooms换了马甲。meeting rooms求最少需要多少个room,也就是某个时刻有几个并行的 ...

真是啊。和meeting  room的思路是一样的。最后queue的size就是overlap interval最多的啊!!为啥我没有想到。晕死。但是最后结果要输出重复最多次数的timestamp啊。难道需要拿着这个次数再过一遍么?
回复 支持 反对

使用道具 举报

 楼主| primbo 发表于 2016-3-12 21:49:04 | 显示全部楼层
Chi2829 发表于 2016-3-12 13:52
&#128077;这个代码很简洁啊!没做过meeting room,但是这么看和skyline也很像!results可能还要去个重。 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
研究出来了指导一下。
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-3-12 23:49:24 | 显示全部楼层
Chi2829 发表于 2016-3-12 13:52. 1point3acres.com/bbs
&#128077;这个代码很简洁啊!没做过meeting room,但是这么看和skyline也很像!results可能还要去个重。 ...

写了个heap的python版本。求指导。
  1. import heapq
  2. -google 1point3acres
  3. def frequent_timestamp2(intervals):
  4.     intvs = sorted(intervals, key=lambda x: x[0])  # sort by starting time
  5.     endtimes = []  # a heap to keep end times.鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.     results = []
  7.     maxcnt, currcnt = 1, 0  # maximum overlap count and current overlap count
  8.     for i in range(len(intvs)):
  9.         newstart, newend = intvs[i]  # start and end time of a new interval
  10.         while endtimes and endtimes[0] <= newstart:
  11.             # while start time of curr interval >= smallest end time of an visited interval, pop the old endtime from heap and check count
  12.             oldend = heapq.heappop(endtimes)
  13.             if currcnt > maxcnt:
  14.                 results = range(intvs[i-1][0], oldend)
  15.                 maxcnt = currcnt
  16.             elif currcnt == maxcnt:
  17.                 results += range(intvs[i-1][0], oldend)
  18.             currcnt -= 1
  19.         heapq.heappush(endtimes, newend)  # push endtime of curr interval to heap
  20.         currcnt += 1
  21.     if currcnt > maxcnt:
  22.         results = range(intvs[-1][0], endtimes[0])
  23.     elif currcnt == maxcnt:
  24.         results += range(intvs[-1][0], endtimes[0])
    .1point3acres缃
  25.     return results
复制代码
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-3-13 00:00:39 | 显示全部楼层
primbo 发表于 2016-3-12 21:49
研究出来了指导一下。

他说的挺清楚的啊,我的写法和他细节有些小区别。

先对所有interval按照start time排序,得到排序后数组 intvs。同时初始化一个min heap用来保存现在visit过interval的endtime。用两个变量maxcnt和currcnt记录到最大overlap数和现在的overlap数。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后对排序后的intvs遍历。对每个当前interval,先看已经visit过interval的最小结束时间(heap里保存的)是不是小等于当前interval的开始时间,如果是的话就check现在的overlap数和maxcnt的关系并update结果。 每次pop出heap最小的end时间时,相当于remove了一个interval,现在overlap树currcnt减1。当heap记录的结束时间的最小值大等于当前interval的起始值时,把当前interval的结束时间放入heap,相当于把interval加入,并且currcnt加上1。

你可能需要仔细的琢磨一下,画个图什么的。考虑清楚一次以后就容易了。
回复 支持 反对

使用道具 举报

 楼主| primbo 发表于 2016-3-13 00:03:53 | 显示全部楼层
Chi2829 发表于 2016-3-13 00:00
他说的挺清楚的啊,我的写法和他细节有些小区别。
. visit 1point3acres.com for more.
先对所有interval按照start time排序,得到排序后数 ...

亲,求给一个java或者c++的版本。
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-3-13 00:07:14 | 显示全部楼层
primbo 发表于 2016-3-13 00:03
亲,求给一个java或者c++的版本。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
亲,你这不是难为我吗...转专业现在只会写写python。你当伪码看啊!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-26 10:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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