《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 9791|回复: 51
收起左侧

facebook 二面题目求解题思路

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

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

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

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

x
interval [startTime, stoptime)   ----integral  time stamps
给这样的一串区间 I1, I2......In  
找出 一个 time stamp  出现在interval的次数最多。. 1point3acres.com/bbs
startTime <= t< stopTime 代表这个数在区间里面出现过。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
example:  [1,3),  [2, 7),   [4,  8),   [5, 9)
5和6各出现了三次, 所以答案返回5,6。
有没有大神有思路 求指导. From 1point 3acres bbs


补充内容 (2016-3-13 03:47):. Waral 鍗氬鏈夋洿澶氭枃绔,
具体代码参照后面。meeting room 变形。

评分

2

查看全部评分

emmarong 发表于 2016-3-12 13:35:45 | 显示全部楼层
这题就是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])-google 1point3acres
  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). visit 1point3acres.com for more.
  12.         while ongoing and e >= ongoing[0]:
  13.             heapq.heappop(ongoing)
  14.         while intvid < len(intvs) and e >= intvs[intvid][0]:. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.             heapq.heappush(ongoing, intvs[intvid][1])
  16.             intvid += 1
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  17.         if len(ongoing) > moccurs:
  18.             moccurs = len(ongoing)
  19.             results = [e]. 鍥磋鎴戜滑@1point 3 acres
  20.         elif len(ongoing) == moccurs:-google 1point3acres
  21.             results.append(e)
  22.     return results
复制代码
回复 支持 4 反对 0

使用道具 举报

xutopia 发表于 2016-3-12 10:22:40 | 显示全部楼层
把所有的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){. from: 1point3acres.com/bbs
  2.                 List<int[]> ret = new ArrayList<>();
  3.                 List<int[]> res = new ArrayList<>();
  4.                 for(int[] interval : intervals){
  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.                 }. more info on 1point3acres.com
  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;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  15.                 for(int[] pos : res){
  16.                         if(pos[1] == 1){//start point
  17.                                 num++;. 1point 3acres 璁哄潧
  18.                                 start = pos[0];. 1point 3acres 璁哄潧
  19.                         }else{// end point
  20.                                 if(num == max){
  21.                                         ret.add(new int[]{start, pos[0]});
  22.                                 }else if(num > max){
  23.                                         max = num;
  24.                                         ret = new ArrayList<>();
  25.                                         ret.add(new int[]{start, pos[0]});
  26.                                 }
  27.                                 num--;
  28.                         }. more info on 1point3acres.com
  29.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  30.                
  31.                 for(int[] temp : ret){
  32.                         System.out.println(":["+temp[0] + "," + temp[1] + ")");. visit 1point3acres.com for more.
  33.                 }
    .1point3acres缃
  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. }
  9. . from: 1point3acres.com/bbs
  10. class Point{
  11.         int time;
  12.         boolean flag;
  13.         Interval interval;
  14.         public Point(int t, boolean f, Interval i){
  15.                 time = t;
  16.                 flag = f;
  17.                 interval = i;
  18.         }
  19. }

  20. class myComparator implements Comparator<Point>{
  21.         public int compare(Point i1, Point i2){
  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.         }
  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;. From 1point 3acres bbs
  35.                
    . more info on 1point3acres.com
  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>();
  50.                 int max = 0, num = 0;
  51.                 for(Point p : pointList){
    . more info on 1point3acres.com
  52.                         if(p.flag == true){
  53.                                 num++;
  54.                                 if(num >= max){
  55.                                         if(num > max){
  56.                                                 maxIntervalList.clear();
  57.                                         }
  58.                                        
  59.                                         max = num;. more info on 1point3acres.com
  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.                                 }
  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.                 }
  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.                 -google 1point3acres
  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){. From 1point 3acres bbs
  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):
應該有更好的做法吧?求大神、
回复 支持 反对

使用道具 举报

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);. 1point 3acres 璁哄潧
  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)
  17.             return result;

  18. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  19.         Map<Integer, Integer> map = new HashMap<>();. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.         List <Interval> newIntervals = new ArrayList<>();//merged list
  21.         newIntervals.add(intervals.get(0));
  22.         for (int i = 1; i < intervals.size(); i++) {
  23.             Interval pre = newIntervals.get(newIntervals.size() -1);
  24.             Interval cur = intervals.get(i);
  25.             int s = -1, e = -1;//overlap interval
  26.             if (cur.start < pre.end) {
  27.                 s = cur.start;
  28.             } else {
  29.                 newIntervals.add(cur);
  30.                 continue;. visit 1point3acres.com for more.
  31.             }
  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)) {
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  40.                     map.put(j, map.get(j)+1);
  41.                 } else {
  42.                     map.put(j, 2);
  43.                 }
  44.             }
  45.         }. from: 1point3acres.com/bbs

  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.             }. 鍥磋鎴戜滑@1point 3 acres
  53.             return result;
  54.         } else {
  55.             int max = 0;
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.             }
  65.         }
  66.         return result;
  67.     }
  68. }

  69. class Interval{
  70.     //[ start, end )
  71.     int start;
  72.     int end;.鏈枃鍘熷垱鑷1point3acres璁哄潧

  73.     public Interval(int start, int end) {. 鍥磋鎴戜滑@1point 3 acres
  74.         this.start = start;
  75.         this.end = end;
  76.     }. visit 1point3acres.com for more.
  77. }
复制代码

补充内容 (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,求拍。

class BIT(object):
    def __init__(self, n):. 1point 3acres 璁哄潧
        self.size = size = n + 1
        self.bit = [0] * size
. more info on 1point3acres.com
    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
        while i > 0:
            res += self.bit
            i -= self._lowbit(i)
        return res


class Solution(object):
. from: 1point3acres.com/bbs
    def frequent_timestamp(self, inputs):
        result = []
        # assume input is a list of timestamps [start, end]
        stamps = reduce(lambda x, y: x + y, inputs). from: 1point3acres.com/bbs
        stamps = sorted(set(stamps))
        # discretize. Waral 鍗氬鏈夋洿澶氭枃绔,
        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:
                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)]
        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()
    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. 1point 3acres 璁哄潧
把所有的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,也就是某个时刻有几个并行的 ...
. more info on 1point3acres.com
&#128077;这个代码很简洁啊!没做过meeting room,但是这么看和skyline也很像!results可能还要去个重。明天好好研究一下!多谢!
回复 支持 反对

使用道具 举报

 楼主| primbo 发表于 2016-3-12 21:48:05 | 显示全部楼层
emmarong 发表于 2016-3-12 13:35-google 1point3acres
这题就是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-google 1point3acres
这题就是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可能还要去个重。 ...
.1point3acres缃
研究出来了指导一下。
回复 支持 反对

使用道具 举报

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-google 1point3acres
  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. 鍥磋鎴戜滑@1point 3 acres
  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)-google 1point3acres
  17.             currcnt -= 1. more info on 1point3acres.com
  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
研究出来了指导一下。

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

先对所有interval按照start time排序,得到排序后数组 intvs。同时初始化一个min heap用来保存现在visit过interval的endtime。用两个变量maxcnt和currcnt记录到最大overlap数和现在的overlap数。. 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。

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

使用道具 举报

 楼主| 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
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷亲,求给一个java或者c++的版本。
. From 1point 3acres bbs
亲,你这不是难为我吗...转专业现在只会写写python。你当伪码看啊!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 10:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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