一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2325|回复: 23
收起左侧

Uber电面

[复制链接] |试试Instant~ |关注本帖
lovingd7 发表于 2016-1-29 12:22:58 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Fail在职跳槽

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

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

x
一个月前面的了,一个中国小哥。. From 1point 3acres bbs

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


没有做出来,最后跪了。
面完了之后自己写了写,用BFS+DFS做出来了,感觉这道题当面试题略难。Uber bar也是有点高。

评分

2

查看全部评分

gavinzhang 发表于 2016-1-29 13:10:19 | 显示全部楼层
楼主能具体讲一下题目嘛
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-1-29 13:48:42 | 显示全部楼层
感觉greedy是能做的,有点像meeting room的感觉
回复 支持 反对

使用道具 举报

Evangileon 发表于 2016-1-29 14:07:22 | 显示全部楼层
能分享一下题目细节吗?比如房间预订是一个 interval,还是就是一个值?换房间的目的是什么,全部安排入住吗?
回复 支持 反对

使用道具 举报

 楼主| lovingd7 发表于 2016-1-31 03:22:35 | 显示全部楼层
gavinzhang 发表于 2016-1-29 13:10
楼主能具体讲一下题目嘛

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

使用道具 举报

 楼主| lovingd7 发表于 2016-1-31 03:23:32 | 显示全部楼层
johnjavabean 发表于 2016-1-29 13:48
感觉greedy是能做的,有点像meeting room的感觉

跟meeting room不一样的,greedy只能找出最少换几次,找不出所有情况。而且greedy的证明非常难,不好证
回复 支持 反对

使用道具 举报

 楼主| lovingd7 发表于 2016-1-31 03:26:12 | 显示全部楼层
Evangileon 发表于 2016-1-29 14:07. 1point3acres.com/bbs
能分享一下题目细节吗?比如房间预订是一个 interval,还是就是一个值?换房间的目的是什么,全部安排入住 ...
. 1point 3acres 璁哄潧
是interval,知道房间已被预定的interval和一个客人入住的interval。
酒店就是要给客人安排房间,尽量不要给客人换房间,所以需要你来写算法让换的房间次数尽量少
回复 支持 反对

使用道具 举报

linlin1990 发表于 2016-1-31 03:49:37 | 显示全部楼层
uber投简历多久有回复呢
回复 支持 反对

使用道具 举报

 楼主| lovingd7 发表于 2016-1-31 05:36:30 | 显示全部楼层
linlin1990 发表于 2016-1-31 03:49
uber投简历多久有回复呢
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我是内推的,很快
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-1-31 05:54:39 | 显示全部楼层
lovingd7 发表于 2016-1-31 03:22
就是现在知道所有房间已经被预定的时间段,现在输入是一个客人需要预定的时间段。
要让客人换的房间次数 ...

lz,可以给个例子不?

输入是什么,输出是什么?

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

订房间的时候,除了时间,还有房间号的要求?
回复 支持 反对

使用道具 举报

 楼主| lovingd7 发表于 2016-1-31 07:30:47 | 显示全部楼层
guixi107 发表于 2016-1-31 05:54
lz,可以给个例子不?. 鍥磋鎴戜滑@1point 3 acres

输入是什么,输出是什么?

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

如果房间已经在这段时间被预定,客人只能换房间了, 和房间号其实没什么关系
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-1-31 07:42:23 | 显示全部楼层
面试官现场没给些具体的提示?
回复 支持 反对

使用道具 举报

linlin1990 发表于 2016-1-31 08:10:28 | 显示全部楼层
lovingd7 发表于 2016-1-31 05:36-google 1point3acres
我是内推的,很快

哦哦谢啦!~我海投渺无音信。。。
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-1-31 12:40:09 | 显示全部楼层
lovingd7 发表于 2016-1-31 07:30. more info on 1point3acres.com
public List findAllMinIntervalPath(List busyTime, Interval guestTime)
. From 1point 3acres bbs
如果房间已经在这段时间被 ...

还是没follow
. From 1point 3acres bbs
可以给个例子和pseudo code吗?
回复 支持 反对

使用道具 举报

大眼珠子 发表于 2016-1-31 14:08:18 | 显示全部楼层
这个最终可以用DP来做
回复 支持 反对

使用道具 举报

 楼主| lovingd7 发表于 2016-1-31 15:22:09 | 显示全部楼层
guixi107 发表于 2016-1-31 12:40
还是没follow. 鍥磋鎴戜滑@1point 3 acres

可以给个例子和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;. From 1point 3acres bbs
               
                HashMap<Interval, ArrayList<Interval>> map = new HashMap<Interval, ArrayList<Interval>>();. visit 1point3acres.com for more.
                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){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                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); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                                }. visit 1point3acres.com for more.
                                                if(i.end >= range.end) {
                                                        findPath = true;
                                                }
                                        }
                                }
                        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                       
                        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>();
. 鍥磋鎴戜滑@1point 3 acres                for(Interval i : heads) {
                        list.add(i);. from: 1point3acres.com/bbs
                        dfs(min, map, range, list, res);
                        list.remove(i);. visit 1point3acres.com for more.
                }
               
                return res;-google 1point3acres
        }
       
        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;. Waral 鍗氬鏈夋洿澶氭枃绔,
                . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                ArrayList<Interval> neighbors = map.get(prev);.鏈枃鍘熷垱鑷1point3acres璁哄潧
               
                for(Interval i : neighbors){. from: 1point3acres.com/bbs
                        list.add(i);. 1point 3acres 璁哄潧
                        dfs(min - 1, map, range, list, res);. 1point3acres.com/bbs
                        list.remove(i);
                }
        }
回复 支持 反对

使用道具 举报

 楼主| lovingd7 发表于 2016-1-31 15:24:28 | 显示全部楼层
大眼珠子 发表于 2016-1-31 14:08
这个最终可以用DP来做

dp怎么做,请教一下
回复 支持 反对

使用道具 举报

大眼珠子 发表于 2016-2-1 07:01:31 | 显示全部楼层
lovingd7 发表于 2016-1-31 15:24. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
dp怎么做,请教一下
. visit 1point3acres.com for more.
求最小次数的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;
}

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

回复 支持 反对

使用道具 举报

yrb 发表于 2016-2-1 08:06:31 | 显示全部楼层
这个定义我不太理解,只给了interval,房间的号码在哪。怎么知道哪个interval是代表哪个房间?或者interval与interval有什么区别
回复 支持 反对

使用道具 举报

大眼珠子 发表于 2016-2-1 08:54:30 | 显示全部楼层
yrb 发表于 2016-2-1 08:06
这个定义我不太理解,只给了interval,房间的号码在哪。怎么知道哪个interval是代表哪个房间?或者interval ...

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

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


回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 04:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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