从谷歌的算法采访 [英] Algorithm interview from Google
问题描述
我是一个很长一段时间潜伏者，而刚刚接受了一次采访与谷歌，他们问我这个问题：
I am a long time lurker, and just had an interview with Google where they asked me this question:
群星希望在皇家阿尔伯特音乐厅演出，你是负责调度 他们的演唱会。请求执行的大厅被安置在一个先到先得 政策。仅一个表现为每天可能，此外，不能有任何的音乐会 发生在5日内对方
Various artists want to perform at the Royal Albert Hall and you are responsible for scheduling their concerts. Requests for performing at the Hall are accommodated on a first come first served policy. Only one performance is possible per day and, moreover, there cannot be any concerts taking place within 5 days of each other
文（即5天之内已经sched-请求的时间d这是不可能的 ULED性能），给出一个O（log n）的 - 时间算法来寻找下一个可用天D2 （D2> D）。
Given a requested time d which is impossible (i.e. within 5 days of an already sched- uled performance), give an O(log n)-time algorithm to find the next available day d2 (d2 > d).
我不知道如何解决它，而现在，面试结束了，我就要死要弄清楚如何解决它。知道如何聪明你最乡亲是，我在想，如果你能给我一只手在这里。这不是做作业，或那样的话。我只是想了解如何解决它的将来的面试。我试着问跟进的问题，但他说，这就是我能告诉你。
I had no clue how to solve it, and now that the interview is over, I am dying to figure out how to solve it. Knowing how smart most of you folks are, I was wondering if you can give me a hand here. This is NOT for homework, or anything of that sort. I just want to learn how to solve it for future interviews. I tried asking follow up questions but he said that is all I can tell you.
推荐答案
您需要提供日期间隔的普通二叉搜索树。只需搜索含有D-间隔。如果它不存在，以间隔下（按顺序），以在其中进行搜索停止点
You need a normal binary search tree of intervals of available dates. Just search for the interval containing d. If it does not exist, take the interval next (in-order) to the point where the search stopped.
注：连续的间隔必须熔合在一起在一个单一的节点。例如：可供日期间隔{2 - 15}和{16 - 23}应该成为{2 - 23}。这可能发生，如果开演唱会预订被取消了。
Note: contiguous intervals must be fused together in a single node. For example: the available-dates intervals {2 - 15} and {16 - 23} should become {2 - 23}. This might happen if a concert reservation was cancelled.
可替换地，可使用的非可用的日期的树代替，条件是相邻的非可用间隔熔合在一起。
Alternatively, a tree of non-available dates can be used instead, provided that contiguous non-available intervals are fused together.
这篇关于从谷歌的算法采访的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
