0

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

Given a requested time d which is impossible (i.e. within 5 days of an already scheduled 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.

Thanks!

NoNameY0
  • 612
  • 2
  • 8
  • 18
  • Does my answer suit you? If not, I would like to know what else you need to accept it... – L0j1k Mar 28 '13 at 01:33
  • Awesome. Thank you! By any chance do you have a blog where you wrote about your interview experience? – L0j1k Mar 28 '13 at 02:24

1 Answers1

4

This is completely firing from the hip because I'm not sure if the question is complete, but if you had a list of dates in an array such that d[0] < d[1] < ... < d[n], the simple answer would be a binary search tree to find the next day.

L0j1k
  • 12,255
  • 7
  • 53
  • 65
  • But it says within 5 days of an already scheduled performance. – NoNameY0 Feb 28 '13 at 01:29
  • Well you're going to need to adjust your BST so that you account for those kinds of restrictions (i.e. x < target-5). But those kinds of operations only add n to your algorithm (e.g. O(logn) + 2) and won't affect the overall efficiency of the algorithm. – L0j1k Feb 28 '13 at 01:32
  • And actually something like `x < target - 5` wouldn't add anything to your O(log n) time, because it's a part of one of the conditions. – L0j1k Feb 28 '13 at 01:37