Uber电面

一个月前面的了，一个中国小哥。

已知酒店房间已被预定的时间和客人想要入住的时间，要客人换房间的次数最少，返回所有可

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

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

id="105" border="0" alt="" />

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);
                }
        }

                • 求出新客人入住时间段内所有房间得空闲情况  A[day][room] = true: a room is available at a day
                • state dp[m][n]: the minimum number of room change at day m if live in room n
                • function:
                        § at a day i, if room j is available, dp[i][j] = min{dp[i-1][j] (if room j is available at day i-1), 1 + dp[i-1][k], ...}, where k is avaialble room at day i-1
                • Initialize,
                        § dp[0][*] = 0, day 0 is the first day when the guest want to stay, * is available on day 0.
                        § dp[*][j] = INT_MAX, if room j is not available at day *
                • return:
                        § minimum room change: min{dp[last day][*]}
                        § if need to return the room change sequence, we need to maintain another matrix prevRoom[i][j] to record the room that guest stays at day i-1, before guest live in room j at day i.
                        § We need to retrieve every sequence with the minimum room change number.

题目描述和 function signature 不太匹配，我觉得改为下面这个更合理

1. List<List<List<Interval>>> findAllMinIntervalPath(List<List<Interval>> intervals, Interval range)

复制代码

因为每个房间有可能有不连续的多个 intervals，然后新客人需要在这些房间的 intervals 间隙中入住，在下一个 busy interval 前换到另一个房间。
返回的是所有的可能，需要一层 list。然后每一种可能是新客人在每个房间住的 interval，不住则是 null，两层 list。所以返回值一共需要 三层 list

楼主能具体讲一下题目嘛

感觉greedy是能做的，有点像meeting room的感觉

能分享一下题目细节吗？比如房间预订是一个 interval，还是就是一个值？换房间的目的是什么，全部安排入住吗？

gavinzhang 发表于 2016-1-29 13:10
楼主能具体讲一下题目嘛

就是现在知道所有房间已经被预定的时间段，现在输入是一个客人需要预定的时间段。
要让客人换的房间次数最少，返回所有的方案

johnjavabean 发表于 2016-1-29 13:48
感觉greedy是能做的，有点像meeting room的感觉

跟meeting room不一样的，greedy只能找出最少换几次，找不出所有情况。而且greedy的证明非常难，不好证

Evangileon 发表于 2016-1-29 14:07
能分享一下题目细节吗？比如房间预订是一个 interval，还是就是一个值？换房间的目的是什么，全部安排入住 ...

是interval，知道房间已被预定的interval和一个客人入住的interval。
酒店就是要给客人安排房间，尽量不要给客人换房间，所以需要你来写算法让换的房间次数尽量少

uber投简历多久有回复呢

linlin1990 发表于 2016-1-31 03:49
uber投简历多久有回复呢

我是内推的，很快

lovingd7 发表于 2016-1-31 03:22
就是现在知道所有房间已经被预定的时间段，现在输入是一个客人需要预定的时间段。
要让客人换的房间次数 ...

lz，可以给个例子不？

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

如果现在已经知道那些房间在哪些时间段已经被预订了，如果房间总数不变的话，为什么通过客人换房间，可以让客人入住？

订房间的时候，除了时间，还有房间号的要求？