Facebook 实习两轮店面

报一个FB两轮店面面经
第一轮：
1.判断有效回文串
2.decode ways
3.number of islands
其中第一题稍微改得复杂了些，第三题要求返回个数
第二轮：
给定一堆interval（如果我们管这个list叫IntervalList）， 和一个target interval
我们的目标是去merge这些interval，让merge的结果能够『cover』这个target interval， 求这种merge

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

trong>补充内容 (2017-1-25 12:24):
最终再遍历一次dp，看下curEnd是否大于targetEnd，如果是的话，就可以去更新最终的答案了
（直接也应该对达不到targetStart的interval进行特殊处理）
这样最终的复杂度是O（n^2)

cntototo 发表于 2017-2-1 06:25
感觉第二轮的题更像是greedy。先把所有intervals按start排序，然后遍历。首先我们要从那些start小于等于tar ...

可以简化一点，不用全部排序，之排序那些和target有交集的interver。然后greedy

用greedy来做可以到O(nlogn)复杂度。

1. def find_min_intervals(intervals, target):
   
2.     intervals.sort()
   
3.     res = 0
   
4.     cur_target = target[0]
   
5.     i = 0
   
6.     max_step = 0
   
7.     while i < len(intervals) and cur_target < target[1]:
   
8.         while i < len(intervals) and intervals[i][0] <= cur_target:
   
9.             max_step = max(max_step, intervals[i][1])
   
10.             i += 1
    
11.         cur_target = max_step
    
12.         res += 1
    
13.     return res if cur_target >= target[1] else 0

复制代码

感觉第二轮的题更像是greedy。先把所有intervals按start排序，然后遍历。首先我们要从那些start小于等于target.start的intervals中选end最大的那个，假设我们用A来表示那个选出来的interval。如果A.end小于target.end，我们就得继续遍历，从那些start小于等于A.end的intervals中选end最大的那个。最终返回所选的interval个数。时间复杂度是O(nlogn)。隐约觉得很像jump game II。

问下楼主第二轮是怎么做的呀

同问第二轮

第二轮好像是set cover?

第二题是求最短路径长度使用标准的bfs应该就可以了吧

第二题代码，欢迎大家指正！

1.         public int find(Interval[] intervals, Interval target){
   
2.                 if(intervals == null || intervals.length == 0) return -1;
   
3.                 Arrays.sort(intervals, new Comparator<Interval>(){
   
4.                         public int compare(Interval a, Interval b){
   
5.                                 return a.start - b.start;
   
6.                         }
   
7.                 });
   
8.                 int res = 0;
   
9.                 int i = 0;
   
10.                 int start = target.start;
    
11.                 while(i < intervals.length){
    
12.                         int cur = greedy(intervals, i, start);
    
13.                         res++;
    
14.                         if(intervals[cur].end >= target.end) return res;
    
15.                         i = cur;
    
16.                         start = intervals[cur].end;
    
17.                 }
    
18.                 return -1;
    
19.         }
    
20. 
    
21.         public int greedy(Interval[] intervals, int i, int tar){
    
22.                 int res = i;
    
23.                 while(i < intervals.length){
    
24.                         if(intervals[i].start <= tar && intervals[i].end > intervals[res].end){
    
25.                                 res = i;
    
26.                         }else if(intervals[i].start > tar) return res;
    
27.                         i++;
    
28.                 }
    
29.                 return res;
    
30.         }

复制代码

补充内容 (2017-2-20 08:41):
nlogn

zhangxi1994 发表于 2017-2-20 08:41
第二题代码，欢迎大家指正！

层主考虑下特殊情况，所有区间都比target区间大，这样的话层主的第一个loop是跳不出来的

英伦十六世纪 发表于 2017-2-21 05:11
层主考虑下特殊情况，所有区间都比target区间大，这样的话层主的第一个loop是跳不出来的

有道理！不过这样就没有答案了诶。那就在loop前加一行判断好了！

楼主请问 第一面是 45 分钟吗？ 45 分钟 3题代码都要写出来？