一亩三分地论坛

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

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

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的次数最多。. from: 1point3acres.com/bbs
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 | 显示全部楼层
这题就是LC上面的meeting rooms换了马甲。meeting rooms求最少需要多少个room,也就是某个时刻有几个并行的会议,这个题目求时刻有最大的并行interval数量,差不多,按照start time排一遍,再用一个heap放结束时间就可以了。贴个python版本的:
  1. . Waral 鍗氬鏈夋洿澶氭枃绔,
  2. import heapq
  3. def integraltimestamps2(intervals):
  4.     intvs = sorted(intervals, key = lambda x : x[0])
  5.     edges = sorted([intv[0] for intv in intervals]+[intv[1] for intv in intervals])
  6.     results = []
  7.     moccurs = 0
  8.     ongoing = []
  9.     intvid = 0
  10.     for e in edges:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  11.         if results and len(ongoing) == moccurs:
  12.             results += range(results[-1]+1,e)
  13.         while ongoing and e >= ongoing[0]:
  14.             heapq.heappop(ongoing)
  15.         while intvid < len(intvs) and e >= intvs[intvid][0]:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  16.             heapq.heappush(ongoing, intvs[intvid][1])
  17.             intvid += 1. visit 1point3acres.com for more.
  18.         if len(ongoing) > moccurs:
  19.             moccurs = len(ongoing)
  20.             results = [e]
  21.         elif len(ongoing) == moccurs:
  22.             results.append(e)
  23.     return results
复制代码
回复 支持 4 反对 0

使用道具 举报

何打发123 发表于 2016-7-27 07:23:16 | 显示全部楼层
感谢楼主分享~~ 自己写了一个 大概思路是记录到了每一点目前有的interval的数量 各位求指正~~
  1. import java.util.*;

  2. class Interval{
  3.         int start, end;
  4.         public Interval(int s, int e){. from: 1point3acres.com/bbs
  5.                 start = s;
  6.                 end = e;
  7.         }
  8. }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  9. class Point{
  10.         int time;
  11.         boolean flag;
  12.         Interval interval;. Waral 鍗氬鏈夋洿澶氭枃绔,
  13.         public Point(int t, boolean f, Interval i){
  14.                 time = t;
  15.                 flag = f;
  16.                 interval = i;
  17.         }
  18. }

  19. class myComparator implements Comparator<Point>{
  20.         public int compare(Point i1, Point i2){
  21.                 if(i1.time == i2.time){
  22.                         //finish first
  23.                         if(!i1.flag && i2.flag){
  24.                                 return -1;
  25.                         }else return 1;
  26.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  27.                 return i1.time - i2.time;
  28.         }
  29. }

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

使用道具 举报

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

使用道具 举报

guschen802 发表于 2016-3-12 09:53:41 | 显示全部楼层
  1. public class Solution {
  2.     public static void main(String[] args) {
  3.         List <Interval> list = new ArrayList<>();. visit 1point3acres.com for more.
  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);
  9.         for (Integer it : result) {
  10.             System.out.println(it);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.         }
  12.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  13.     public static List<Integer> findMost(List <Interval> intervals) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.         //assume intervals sorted
  15.         List<Integer> result = new ArrayList<>();
  16.         if (intervals == null || intervals.size() == 0)
  17.             return result;
  18. . From 1point 3acres bbs
  19.         Map<Integer, Integer> map = new HashMap<>();
  20.         List <Interval> newIntervals = new ArrayList<>();//merged list
  21.         newIntervals.add(intervals.get(0));
  22.         for (int i = 1; i < intervals.size(); i++) {. From 1point 3acres bbs
  23.             Interval pre = newIntervals.get(newIntervals.size() -1);
  24.             Interval cur = intervals.get(i);
  25.             int s = -1, e = -1;//overlap interval. 1point3acres.com/bbs
  26.             if (cur.start < pre.end) {
  27.                 s = cur.start;
  28.             } else {
  29.                 newIntervals.add(cur);
  30.                 continue;
  31.             }. more info on 1point3acres.com
  32.             if (cur.end <= pre.end) {
  33.                 e = cur.end;
  34.             } else {
  35.                 e = pre.end;
  36.                 pre.end = cur.end;
  37.             }
  38.             for (int j = s; j < e; j++) {
  39.                 if (map.containsKey(j)) {
  40.                     map.put(j, map.get(j)+1);
  41.                 } else {
  42.                     map.put(j, 2);
  43.                 }
  44.             }
  45.         }

  46.         if (map.size() == 0) {
  47.             // if no over lap
  48.             for (Interval in : intervals) {
  49.                 for (int i = in.start; i < in.end; i++) {
  50.                     result.add(i);
  51.                 }
  52.             }. 1point3acres.com/bbs
  53.             return result;
  54.         } else {. visit 1point3acres.com for more.
  55.             int max = 0;
  56.             for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
  57.                 if (entry.getValue() > max) {
  58.                     max = entry.getValue();
  59.                     result.clear();
  60.                     result.add(entry.getKey());
  61.                 } else if (entry.getValue() == max) {
  62.                     result.add(entry.getKey());
  63.                 }
  64.             }
    . 1point3acres.com/bbs
  65.         }. 鍥磋鎴戜滑@1point 3 acres
  66.         return result;
  67.     }
  68. }

  69. class Interval{. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  70.     //[ start, end )
  71.     int start;
  72.     int end;

  73.     public Interval(int start, int end) {
  74.         this.start = start;-google 1point3acres
  75.         this.end = end;
  76.     }
  77. }
复制代码
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2016-3-12 10:25):
HashMap的空間還能進一步減少,使用TreeMap, 每次有重疊的interval時,取出小於重疊部分之前的數據并計算最大值,這樣能保證總interval很長的時候map不會太大
回复 支持 反对

使用道具 举报

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

使用道具 举报

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,求拍。

class BIT(object):
    def __init__(self, n):
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷        self.size = size = n + 1. Waral 鍗氬鏈夋洿澶氭枃绔,
        self.bit = [0] * size

    def _lowbit(self, x):. 1point 3acres 璁哄潧
        return x & -x

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

    def sum(self, i):. From 1point 3acres bbs
        res = 0
        while i > 0:
            res += self.bit. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            i -= self._lowbit(i)
        return res
. more info on 1point3acres.com

class Solution(object):

    def frequent_timestamp(self, inputs):
        result = []-google 1point3acres
        # assume input is a list of timestamps [start, end]
        stamps = reduce(lambda x, y: x + y, inputs)
        stamps = sorted(set(stamps))
        # discretize
        time_idx_dict, idx_time_dict = {}, {}
        idx = 0. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        for i, time in enumerate(stamps):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            idx += 1.鏈枃鍘熷垱鑷1point3acres璁哄潧
            if i > 0 and time - stamps[i-1] > 1:-google 1point3acres
                idx_time_dict[idx] = range(stamps[i-1] + 1, time)
                idx += 1
            idx_time_dict[idx] = [time]
            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)]. From 1point 3acres bbs
        maxidx = max(idxcnts)
        for i in range(idx):
            if idxcnts == maxidx:
                result += idx_time_dict[i+1]
        return result


if __name__ == "__main__":
    timestamps = [[1, 3],  [2, 7],   [4, 8],   [5, 9]]. 1point 3acres 璁哄潧
    stampcounter = Solution()
    print stampcounter.frequent_timestamp(timestamps)

补充内容 (2016-3-12 12:41):. from: 1point3acres.com/bbs
有个小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 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
&#128077;这个代码很简洁啊!没做过meeting room,但是这么看和skyline也很像!results可能还要去个重。 ...

写了个heap的python版本。求指导。
  1. import heapq

  2. def frequent_timestamp2(intervals):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  3.     intvs = sorted(intervals, key=lambda x: x[0])  # sort by starting time
  4.     endtimes = []  # a heap to keep end times
  5.     results = []. from: 1point3acres.com/bbs
  6.     maxcnt, currcnt = 1, 0  # maximum overlap count and current overlap count
  7.     for i in range(len(intvs)):
  8.         newstart, newend = intvs[i]  # start and end time of a new interval. 1point 3acres 璁哄潧
  9.         while endtimes and endtimes[0] <= newstart:
  10.             # while start time of curr interval >= smallest end time of an visited interval, pop the old endtime from heap and check count
  11.             oldend = heapq.heappop(endtimes). from: 1point3acres.com/bbs
  12.             if currcnt > maxcnt:. visit 1point3acres.com for more.
  13.                 results = range(intvs[i-1][0], oldend)
  14.                 maxcnt = currcnt
  15.             elif currcnt == maxcnt:
  16.                 results += range(intvs[i-1][0], oldend)
  17.             currcnt -= 1
  18.         heapq.heappush(endtimes, newend)  # push endtime of curr interval to heap
  19.         currcnt += 1
  20.     if currcnt > maxcnt:
  21.         results = range(intvs[-1][0], endtimes[0])
  22.     elif currcnt == maxcnt:. 1point 3acres 璁哄潧
  23.         results += range(intvs[-1][0], endtimes[0])
  24.     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数。
. from: 1point3acres.com/bbs
然后对排序后的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。
. From 1point 3acres bbs
你可能需要仔细的琢磨一下,画个图什么的。考虑清楚一次以后就容易了。
回复 支持 反对

使用道具 举报

 楼主| primbo 发表于 2016-3-13 00:03:53 | 显示全部楼层
Chi2829 发表于 2016-3-13 00:00
他说的挺清楚的啊,我的写法和他细节有些小区别。. 1point3acres.com/bbs
. 鍥磋鎴戜滑@1point 3 acres
先对所有interval按照start time排序,得到排序后数 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
亲,求给一个java或者c++的版本。
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-3-13 00:07:14 | 显示全部楼层
primbo 发表于 2016-3-13 00:03
亲,求给一个java或者c++的版本。

亲,你这不是难为我吗...转专业现在只会写写python。你当伪码看啊!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 11:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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