Uber电面

大眼珠子 发表于 2016-2-1 08:54
题目描述可能不是很完全，函数定义和题目描述不是完全匹配。
我理解的题目是

非常感谢！这下清楚了不少，赞！

可以先用 dp 求出某一天入住某间房到最后一天，需要的最少换房次数和下次换房的日期，以及某一天入住哪些房间可以做到换房次数最少。然后用DFS求出所有可能的换房路径：(日期, 房号) -> (日期, 房号)……假如有 n 间房，住 T 天，则 dp 可以在 nT + T ^ 2 时间完成，DFS 需要 nT 时间。空间需要 nT。
假如时间不是按整天算，而是连续的，那么可以把整段时间按照所给的时间点划分成小段，然后按上面的方法做。
不过具体写起来可能还是比较麻烦……

补充内容 (2016-2-1 13:01):
空间需要 nT + T ^ 2……

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

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

复制代码

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

大眼珠子 发表于 2016-2-1 07:01
求最小次数的DP
A[day][roomID] 表示这房间某天是否空闲
D[day][roomID] 表示第几天时呆在这房间时，已 ...

我觉得这个DP有问题，应该是第i天，第j间房如果是空闲的话， dp[i][j] = Min(dp[i-1][j]（如果i-1天也是空闲）, Min(dp[i-1][k] k从1到n，除掉j之外)+1）,如果第i天，第j间房不是空闲的话，算dp[i][j]根本没有意义，可以令其等于0

                • 求出新客人入住时间段内所有房间得空闲情况  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.

wangxinbo1123 发表于 2017-1-3 14:34
• 求出新客人入住时间段内所有房间得空闲情况  A[day][room] = true: a room is available at a da ...

其实这是greedy，你每次就找当前可用房间里面，到期最晚的那个就可以了。

关键这道题要输出的是所有可能情况，这就很尴尬了，半个小时哪里做的完。把输入数据整理出来Index一下都要好久了。

补充内容 (2017-4-5 09:46):
应该是一个BFS，每个interval之间只要有时间上的重叠，就是邻接点。

然而这道题真心蛋疼，怎么可能做的完，整理输入数据就要花好久。

电面出这种题。。扣电话就好了，在开玩笑么。。根本写不完