Uber电面

guixi107 发表于 2016-1-31 05:54
lz，可以给个例子不？

输入是什么，输出是什么？

public List<List<Interval>> findAllMinIntervalPath(List<Interval> busyTime, Interval guestTime)

如果房间已经在这段时间被预定，客人只能换房间了， 和房间号其实没什么关系

面试官现场没给些具体的提示？

lovingd7 发表于 2016-1-31 05:36
我是内推的，很快

哦哦谢啦！～我海投渺无音信。。。

lovingd7 发表于 2016-1-31 07:30
public List findAllMinIntervalPath(List busyTime, Interval guestTime)

如果房间已经在这段时间被 ...

还是没follow

可以给个例子和pseudo code吗？

这个最终可以用DP来做

guixi107 发表于 2016-1-31 12:40
还是没follow

可以给个例子和pseudo code吗？

这是我的代码，略繁琐。
public static ArrayList<ArrayList<Interval>> findAllMinIntervalPath(ArrayList<Interval> intervals, Interval range) {
                ArrayList<ArrayList<Interval>> res = new ArrayList<ArrayList<Interval>>();
                if(intervals.size() == 0) return res;
               
                HashMap<Interval, ArrayList<Interval>> map = new HashMap<Interval, ArrayList<Interval>>();
                Queue<Interval> queue = new LinkedList<Interval>();
                ArrayList<Interval> heads = new ArrayList<Interval>();
               
                Collections.sort(intervals, new Comparator<Interval>(){
                        public int compare(Interval a, Interval b){
                                return a.start - b.start;
                        }
                });
               
                for(Interval i : intervals) {
                        if(i.start <= range.start){
                                if(i.end >= range.end){
                                        ArrayList<Interval> list = new ArrayList<Interval>();
                                        list.add(i);
                                        res.add(list);
                                }
                                queue.add(i);
                                heads.add(i);
                        }
                }
                if(queue.isEmpty()) return res;
                if(res.size() != 0) return res;
               
                Iterator<Interval> iter = queue.iterator();
                while(iter.hasNext()){
                        intervals.remove(iter.next());
                }
               
                int min = 1;
                boolean findPath = false;
                while(!queue.isEmpty()){
                        Queue<Interval> tmp = new LinkedList<Interval>();
                        HashSet<Interval> set = new HashSet<Interval>();
                       
                        findPath = false;
                        while(!queue.isEmpty()){
                                Interval prev = queue.poll();
                                for(Interval i : intervals) {
                                        if(i.start > prev.start && i.start <= prev.end + 1){
                                                if(!map.containsKey(prev)){
                                                        ArrayList<Interval> inter = new ArrayList<Interval>();
                                                        inter.add(i);
                                                        map.put(prev, inter);
                                                }else {
                                                        map.get(prev).add(i);
                                                }
                                                if(!set.contains(i)){
                                                        set.add(i);
                                                        tmp.add(i);
                                                }
                                                if(i.end >= range.end) {
                                                        findPath = true;
                                                }
                                        }
                                }
                        }
                       
                        min++;
                        if(findPath) break;
                        Iterator<Interval> ite = tmp.iterator();
                        while(ite.hasNext()){
                                intervals.remove(ite.next());
                        }
                        queue = tmp;
                }
                if(!findPath) return res;
               
                ArrayList<Interval> list = new ArrayList<Interval>();
                for(Interval i : heads) {
                        list.add(i);
                        dfs(min, map, range, list, res);
                        list.remove(i);
                }
               
                return res;
        }
       
        public static void dfs(int min, HashMap<Interval, ArrayList<Interval>> map, Interval range, ArrayList<Interval> list, ArrayList<ArrayList<Interval>> res) {
                Interval prev = list.get(list.size() - 1);
                if(prev.end >= range.end && min == 1){
                        res.add(new ArrayList<Interval>(list));
                        return;
                }
               
                if(!map.containsKey(prev)) return;
               
                ArrayList<Interval> neighbors = map.get(prev);
               
                for(Interval i : neighbors){
                        list.add(i);
                        dfs(min - 1, map, range, list, res);
                        list.remove(i);
                }
        }

大眼珠子 发表于 2016-1-31 14:08
这个最终可以用DP来做

dp怎么做，请教一下

lovingd7 发表于 2016-1-31 15:24
dp怎么做，请教一下

求最小次数的DP
A[day][roomID] 表示这房间某天是否空闲
D[day][roomID] 表示第几天时呆在这房间时，已有的最小换房数

if (A[day][roomId]) {
  D[day][roomId]  = D[day-1][rooId];
} else {
  D[day][roomId] = min(D[day-1][otherRoomID],.....)  +1;
}

上述两种情况取最小值，再加上边界情况，这样就可以求出最少次数，要求出所有的换房顺序的话，在这个基础上改改。

这个定义我不太理解，只给了interval，房间的号码在哪。怎么知道哪个interval是代表哪个房间？或者interval与interval有什么区别

yrb 发表于 2016-2-1 08:06
这个定义我不太理解，只给了interval，房间的号码在哪。怎么知道哪个interval是代表哪个房间？或者interval ...

题目描述可能不是很完全，函数定义和题目描述不是完全匹配。
我理解的题目是

已知酒店房间已被预定的时间和客人想要入住的时间，要客人换房间的次数最少，返回所有可能。
例子，输入：
总共10个房间，每个房间的预定和空闲情况已知，即A[day][roomID]是在输入中
然后说新来一人，要求住宿第3天到第7天，求如何安排让客人换房次数最少