Algorithm interview from Google

I am a long time lurker, and just had an interview with Google where they asked me this question:

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

Given a requested time d which is impossible (ie 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.

---

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.

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.

---

Store the scheduled concerts in a binary search tree and find a feasible solution by doing a binary search.

Something like this:

FindDateAfter(tree, x):
  n = tree.root
  if n.date < x 
    n = FindDateAfter(n.right, x)
  else if n.date > x and n.left.date < x
    return n
  return FindDateAfter(n.left, x)

FindGoodDay(tree, x):
  n = FindDateAfter(tree, x)
  while (n.date + 10 < n.right.date)
    n = FindDateAfter(n, n.date + 5)
  return n.date + 5

---

I've used a binary search tree (BST) that holds the ranges for valid free days that can be scheduled for performances. One of the ranges must end with int.MaxValue, because we have an infinite amount of days so it can't be bound.

The following code searches for the closest day to the requested day, and returns it.

The time complexity is O(H) when H is the tree height (usually H=log(N), but can become H=N in some cases.). The space complexity is the same as the time complexity.

public static int FindConcertTime(TreeNode<Tuple<int, int>> node, int reqDay)
{
    // Not found!
    if (node == null)
    {
        return -1;
    }
    Tuple<int, int> currRange = node.Value;
    // Found range.
    if (currRange.Item1 <= reqDay &&
        currRange.Item2 >= reqDay)
    {
        // Return requested day.
        return reqDay;
    }
    // Go left.
    else if (currRange.Item1 > reqDay)
    {
        int suggestedDay = FindConcertTime(node.Left, reqDay);
        // Didn't find appropriate range in left nodes, or found day
        // is further than current option.
        if (suggestedDay == -1 || suggestedDay > currRange.Item1)
        {
            // Return current option.
            return currRange.Item1;
        }
        else
        {
            // Return suggested day.
            return suggestedDay;
        }
    }
    // Go right.
    // Will always find because the right-most node has "int.MaxValue" as Item2.
    else //if (currRange.Item2 < reqDay)
    {
        return FindConcertTime(node.Right, reqDay);
    }
}

链接地址: http://www.djcxy.com/p/40034.html

上一篇: 证明一个平衡二进制的高度

下一篇: 来自Google的算法访谈