facebook 二面题目求解题思路

pinkfloyda

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

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

pinkfloyda

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

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

pinkfloyda

guschen802 发表于 2016-3-12 09:53
补充内容 (2016-3-12 10:25):
HashMap的空間還能進一步減少，使用TreeMap, 每次有重疊的interval時，取出 ...

但是你的代码发现有side effect，原来intervals里面的值会被改动

zjuzqh

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

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

guschen802

pinkfloyda 发表于 2016-3-24 10:39
但是你的代码发现有side effect，原来intervals里面的值会被改动

感謝驗證，改變值這個好解決，如果要求保持原本的不便的話就在放到newinterval裡面克隆一個新的就好了，就是會多浪費空間

sealove999

写一个java，排序的，nlgn

public class Solution {
class timepoint {
int t;
int end;
public timepoint(int tt, int se) {
t = tt;
end = se;
}
}
public List<Integer> find(int[][] intervals) {
List<timepoint> timepoints = new ArrayList<>();
for (int[] interval : intervals) {
timepoints.add(new timepoint(interval[0], 0));
timepoints.add(new timepoint(interval[1], 1));
}
timepoints.sort((x, y) -> {
if (x.t != y.t)
return x.t - y.t;
return x.end - y.end;
});
// find
List<timepoint> ret = new ArrayList<>();
int max = 0;
int count = 0;
for (timepoint tp : timepoints) {
if (tp.end == 0) {
count++;
if (count > max) {
max = count;
ret.clear();
ret.add(tp);
} else if (count == max) {
ret.add(tp);
}
} else if (tp.end == 1) {
if (count == max) {
ret.add(tp);
}
count--;
}
}
// build ret
List<Integer> ret2 = new ArrayList<>();
for (int i = 0; i < ret.size(); i += 2) {
for (int j = ret.get(i).t; j < ret.get(i + 1).t; j++) {
ret2.add(j);
}
}
return ret2;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.find(new int[][] {{1, 3}, {2, 7}, {4, 8}, {5, 9}}));
System.out.println(s.find(new int[][] {{1, 10}}));
System.out.println(
s.find(new int[][] {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}}));
System.out.println(s.find(new int[][] {{1, 2}}));
System.out.println(s.find(new int[][] {{5, 9}, {5, 10}, {7, 13}}));
System.out.println(s.find(new int[][] {}));
System.out.println(s.find(new int[][] {{1, 4}, {1, 4}, {1, 4}}));
}
}

复制代码

何打发123

感谢楼主分享~~ 自己写了一个大概思路是记录到了每一点目前有的interval的数量各位求指正~~

import java.util.*;
class Interval{
int start, end;
public Interval(int s, int e){
start = s;
end = e;
}
}
class Point{
int time;
boolean flag;
Interval interval;
public Point(int t, boolean f, Interval i){
time = t;
flag = f;
interval = i;
}
}
class myComparator implements Comparator<Point>{
public int compare(Point i1, Point i2){
if(i1.time == i2.time){
//finish first
if(!i1.flag && i2.flag){
return -1;
}else return 1;
}
return i1.time - i2.time;
}
}
class Solution {
public ArrayList<Integer> scheduel(ArrayList<Interval> arr){
ArrayList<Integer> res = new ArrayList<Integer>();
if(arr == null || arr.size() == 0) return res;
ArrayList<Point> pointList = new ArrayList<Point>();
for(int i = 0; i < arr.size(); i++){
Interval cur = arr.get(i);
Point startPoint = new Point(cur.start, true, cur);
Point endPoint = new Point(cur.end, false, cur);
pointList.add(startPoint);
pointList.add(endPoint);
}
//sort as start time
Collections.sort(pointList, new myComparator());
ArrayList<Interval> maxIntervalList = new ArrayList<Interval>();
int max = 0, num = 0;
for(Point p : pointList){
if(p.flag == true){
num++;
if(num >= max){
if(num > max){
maxIntervalList.clear();
}
max = num;
Interval x = new Interval(p.time, p.time);
maxIntervalList.add(x);
}
}else{
if(num == max){
Interval lastInterval = maxIntervalList.get
(maxIntervalList.size() - 1);
lastInterval.end = p.time;
}
num--;
}
}
for(Interval temp : maxIntervalList){
for(int moment = temp.start; moment < temp.end; moment++){
res.add(moment);
}
}
return res;
}
public static void main(String[] args) {
Solution r = new Solution();
Interval a = new Interval(2,7);
Interval b = new Interval(1,3);
Interval c = new Interval(4,8);
Interval d = new Interval(5,9);
Interval f = new Interval(7,9);
ArrayList<Interval> res = new ArrayList<Interval>();
res.addAll(Arrays.asList(a, b, c, d, f));
ArrayList<Integer> m = r.scheduel(res);
for(Integer k : m){
System.out.println(k);
}
}
}

复制代码

997562971@qq.co

面另外一家公司，竟然也被面这道题。。。

tigercode

line scan, 唯一要注意的是sort的时候 end排在start的前面

www_boy

Java 版本的，感觉跟skyline很像，最后没返回结果直接打印出来了

public static void FindMaxStamp(List<int[]> intervals){
List<int[]> ret = new ArrayList<>();
List<int[]> res = new ArrayList<>();
for(int[] interval : intervals){
System.out.println("input:" + interval[0] + "," + interval[1]);
res.add(new int[]{interval[0], 1});
res.add(new int[]{interval[1], -1});
}
Collections.sort(res, new Comparator<int[]>(){
public int compare(int[] a, int[] b){
return a[0] - b[0];
}
});
int max = 0, num = 0, start = 0;
for(int[] pos : res){
if(pos[1] == 1){//start point
num++;
start = pos[0];
}else{// end point
if(num == max){
ret.add(new int[]{start, pos[0]});
}else if(num > max){
max = num;
ret = new ArrayList<>();
ret.add(new int[]{start, pos[0]});
}
num--;
}
}
for(int[] temp : ret){
System.out.println(":["+temp[0] + "," + temp[1] + ")");
}
}

复制代码

facebook 二面题目求解题思路

浏览过的版块