近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

facebook 二面题目求解题思路

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

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

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

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

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。. Waral 鍗氬鏈夋洿澶氭枃绔,
有没有大神有思路 求指导.鏈枃鍘熷垱鑷1point3acres璁哄潧
. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (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版本的:. 鍥磋鎴戜滑@1point 3 acres
  1. . visit 1point3acres.com for more.
  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:. from: 1point3acres.com/bbs
  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
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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

使用道具 举报

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

使用道具 举报

www_boy 发表于 2017-2-13 01:27:11 | 显示全部楼层
Java 版本的,感觉跟skyline很像, 最后没返回结果直接打印出来了
  1. public static void FindMaxStamp(List<int[]> intervals){
  2.                 List<int[]> ret = new ArrayList<>();
  3.                 List<int[]> res = new ArrayList<>();
  4.                 for(int[] interval : intervals){. 1point 3acres 璁哄潧
  5.                         System.out.println("input:" + interval[0] + "," + interval[1]);
  6.                         res.add(new int[]{interval[0], 1});
  7.                         res.add(new int[]{interval[1], -1}); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.                 Collections.sort(res, new Comparator<int[]>(){
  10.                         public int compare(int[] a, int[] b){
  11.                                 return a[0] - b[0];
  12.                         }
  13.                 });
  14.                 int max = 0, num = 0, start = 0;. visit 1point3acres.com for more.
  15.                 for(int[] pos : res){
  16.                         if(pos[1] == 1){//start point
  17.                                 num++;. 1point 3acres 璁哄潧
  18.                                 start = pos[0];
  19.                         }else{// end point
  20.                                 if(num == max){. 1point 3acres 璁哄潧
  21.                                         ret.add(new int[]{start, pos[0]});
    . 1point3acres.com/bbs
  22.                                 }else if(num > max){-google 1point3acres
  23.                                         max = num;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.                                         ret = new ArrayList<>();. Waral 鍗氬鏈夋洿澶氭枃绔,
  25.                                         ret.add(new int[]{start, pos[0]});
  26.                                 }
  27.                                 num--;
  28.                         }
  29.                 }
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  30.                
  31.                 for(int[] temp : ret){
  32.                         System.out.println(":["+temp[0] + "," + temp[1] + ")");
  33.                 }
  34.         }
复制代码
回复 支持 1 反对 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){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.                 start = s;
  6.                 end = e;
  7.         }
  8. }. from: 1point3acres.com/bbs

  9. class Point{
  10.         int time;
  11.         boolean flag;. From 1point 3acres bbs
  12.         Interval interval;
  13.         public Point(int t, boolean f, Interval i){
  14.                 time = t;. 1point 3acres 璁哄潧
  15.                 flag = f;
  16.                 interval = i;
  17.         }
  18. }
  19. . visit 1point3acres.com for more.
  20. class myComparator implements Comparator<Point>{
  21.         public int compare(Point i1, Point i2){
  22.                 if(i1.time == i2.time){
  23.                         //finish first. visit 1point3acres.com for more.
  24.                         if(!i1.flag && i2.flag){
  25.                                 return -1;
  26.                         }else return 1;
  27.                 }.1point3acres缃
  28.                 return i1.time - i2.time;
  29.         }
  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;. 鍥磋鎴戜滑@1point 3 acres
  35.                
  36.                 ArrayList<Point> pointList = new ArrayList<Point>();
  37.                
  38.                 for(int i = 0; i < arr.size(); i++){
  39.                         Interval cur = arr.get(i);
  40.                         Point startPoint = new Point(cur.start, true, cur);
  41.                         Point endPoint = new Point(cur.end, false, cur);
  42.                         pointList.add(startPoint);
  43.                         pointList.add(endPoint);
  44.                 }
  45.                 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  46.                 //sort as start time
  47.                 Collections.sort(pointList, new myComparator());
  48.                 .鐣欏璁哄潧-涓浜-涓夊垎鍦
  49.                 ArrayList<Interval> maxIntervalList = new ArrayList<Interval>();.1point3acres缃
  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){
  56.                                                 maxIntervalList.clear();
  57.                                         }
  58.                                        
  59.                                         max = num;
  60.                                         Interval x = new Interval(p.time, p.time);
  61.                                         maxIntervalList.add(x);
    . visit 1point3acres.com for more.
  62.                                 }
  63.                         }else{
  64.                                 if(num == max){
  65.                                         Interval lastInterval = maxIntervalList.get
  66.                                         (maxIntervalList.size() - 1);
  67.                                         lastInterval.end = p.time;. 1point3acres.com/bbs
  68.                                 }
  69.                                 num--;
  70.                         }
  71.                 }
  72.                 for(Interval temp : maxIntervalList){
  73.                         for(int moment = temp.start; moment < temp.end; moment++){
  74.                                 res.add(moment);
  75.                         }
  76.                 }.1point3acres缃
  77.                 return res;
  78.         }
  79.        
  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.                
  92.                 for(Integer k : m){
  93.                         System.out.println(k);
  94.                 }
  95.         }
  96.                 . from: 1point3acres.com/bbs
  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):
應該有更好的做法吧?求大神、
回复 支持 反对

使用道具 举报

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<>();
  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) {
  14.         //assume intervals sorted
  15.         List<Integer> result = new ArrayList<>();
  16.         if (intervals == null || intervals.size() == 0)-google 1point3acres
  17.             return result;

  18.         Map<Integer, Integer> map = new HashMap<>();
  19.         List <Interval> newIntervals = new ArrayList<>();//merged list
    . more info on 1point3acres.com
  20.         newIntervals.add(intervals.get(0));-google 1point3acres
  21.         for (int i = 1; i < intervals.size(); i++) {
  22.             Interval pre = newIntervals.get(newIntervals.size() -1);
  23.             Interval cur = intervals.get(i);
  24.             int s = -1, e = -1;//overlap interval
  25.             if (cur.start < pre.end) {
  26.                 s = cur.start;. From 1point 3acres bbs
  27.             } else {. Waral 鍗氬鏈夋洿澶氭枃绔,
  28.                 newIntervals.add(cur);. 鍥磋鎴戜滑@1point 3 acres
  29.                 continue;
  30.             }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  31.             if (cur.end <= pre.end) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  32.                 e = cur.end;
  33.             } else {
  34.                 e = pre.end;
  35.                 pre.end = cur.end;
  36.             }
  37.             for (int j = s; j < e; j++) {
  38.                 if (map.containsKey(j)) {
  39.                     map.put(j, map.get(j)+1);-google 1point3acres
  40.                 } else {
  41.                     map.put(j, 2);
  42.                 }
  43.             }
  44.         }

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

  68. class Interval{. visit 1point3acres.com for more.
  69.     //[ start, end )
  70.     int start;
  71.     int end;

  72.     public Interval(int start, int end) {
  73.         this.start = start;
  74.         this.end = end;
  75.     }
  76. }
复制代码

补充内容 (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. 鍥磋鎴戜滑@1point 3 acres
把所有的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,求拍。
. 鍥磋鎴戜滑@1point 3 acres
class BIT(object):
    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):-google 1point3acres
        while i < self.size:
            self.bit += val
            i += self._lowbit(i)

    def sum(self, i):. more info on 1point3acres.com
        res = 0
        while i > 0:.鏈枃鍘熷垱鑷1point3acres璁哄潧
            res += self.bit
            i -= self._lowbit(i)-google 1point3acres
        return res


class Solution(object):

    def frequent_timestamp(self, inputs):
        result = []. Waral 鍗氬鏈夋洿澶氭枃绔,
        # assume input is a list of timestamps [start, end]
        stamps = reduce(lambda x, y: x + y, inputs)
        stamps = sorted(set(stamps)). from: 1point3acres.com/bbs
        # discretize
        time_idx_dict, idx_time_dict = {}, {}
        idx = 0
        for i, time in enumerate(stamps):
            idx += 1
            if i > 0 and time - stamps[i-1] > 1:.鏈枃鍘熷垱鑷1point3acres璁哄潧
                idx_time_dict[idx] = range(stamps[i-1] + 1, time). 1point 3acres 璁哄潧
                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)]
        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]]
    stampcounter = Solution(). more info on 1point3acres.com
    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. Waral 鍗氬鏈夋洿澶氭枃绔,
这题就是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 = []
  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.鐣欏璁哄潧-涓浜-涓夊垎鍦
  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. more info on 1point3acres.com
  11.             oldend = heapq.heappop(endtimes)
  12.             if currcnt > maxcnt:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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:
  23.         results += range(intvs[-1][0], endtimes[0])
  24.     return results
复制代码
回复 支持 反对

使用道具 举报

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

他说的挺清楚的啊,我的写法和他细节有些小区别。
.1point3acres缃
先对所有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
他说的挺清楚的啊,我的写法和他细节有些小区别。

先对所有interval按照start time排序,得到排序后数 ...

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

使用道具 举报

Chi2829 发表于 2016-3-13 00:07:14 | 显示全部楼层
primbo 发表于 2016-3-13 00:03. 1point 3acres 璁哄潧
亲,求给一个java或者c++的版本。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
亲,你这不是难为我吗...转专业现在只会写写python。你当伪码看啊!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-27 08:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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