Algorithm interview from Google

Question

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 (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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

Store the number of used nights per year, quarter, and month. To find a free night, find the first year that is not fully booked, then the quarter within that year, then the month. Then check each of the nights in that month.

Irregularities in the calendar system makes this a little tricky so instead of using years and months you can apply the idea for units of 4 nights as "month", 16 nights as "quarter", and so on.

Answer 5

Assume, at level 1 all schedule details are available. Group schedule of 16 days schedule at level 2. Group 16 level 2 status at level 3. Group 16 level 3 status at level 4. Depends on number of days that you want to expand, increase the level.

Now search from higher level and do binary search at the end.

Answer 6

Asymtotic complexity:- It means runtime is changing as the input grows. suppose we have an input string “abcd”. Here we traverse through each character to find its length thus the time taken is proportional to the no of characters in the string like n no of char. Thus O(n). but if we put the length of the string “abcd” in a variable then no matter how long the string be we still can find the length of thestring by looking at the variable len. (len=4). ex: return 23. no matter what you input is we still have the output as 23. thus the complexity is O(1). Thus th program will be running in a constant time wrt input size. for O(log n) - the operations are happening in logarithmic steps.

https://drive.google.com/file/d/0B7eUOnXKVyeERzdPUE8wYWFQZlk/view?usp=sharing

Observe the image in the above link. Over here we can see the bended line(logarithmic line). Here we can say that for smaller inputs the O(log n) notation works good as the time taken is less as we can see in the bended line but when the input grows the linear notation i.e O(n) is considered as better way. There are also the best and worst case scenarios to be seen. Like the above example.

You can also refer to this cheat for the algorithms: http://bigocheatsheet.com/

Answer 7

It was already mentioned above, but basically keep it simple with a binary tree. You know a binary tree has log N complexity. So you already know what algorithm you need to use. All you have to do is to come up with a tree node structure and use binary tree insertion algorithm to find next available date: A possible one: The tree node has two attributes: d (date of the concert) and d+5 (end date for the blocking period of 5 days). Again to keep it simple, use a timestamp for the two date attributes. Now it is trivial to find next available date by using binary tree inorder insertion algorithm with initial condition of root = null.

Answer 8

Why not try to use Union-Find? You can group each concert day + the next 5 days as part of one set and then perform a FIND on the given day which would return the next set ID which would be your next concert date.

If implemented using a tree, this gives a O(log n) time complexity.