Hacker News Reader

Comment by euphemize | Hacker News Reader

Interesting. Had a google interview not too long ago, and this was exactly the question asked to me - how would you design an algorithm to find overlapping free time from person X, Y and Z. I guess they got more practical with their questions over the years.

Looks great, liking that is suggests times too.

View on HN

Isn't that just a bit wise AND?

There might be a really clever hash you could build, but it's actually a somewhat complex problem. Finding an overlapping range between two entities is easy... finding it for n-entities is a bit more difficult particularly if you want to do it efficiently. I can imagine a couple of answers.. you can build a lookup table (which makes sense if the time resolution is low enough) and then find gaps in it.

It's actually a pretty good interview question if your going to ask a whiteboard question. It has lots of answers depending on requirements. You can get into parallelizing it for speed. It's more of a practical problem than most and you can implement it basically any language.

It is still just a bitwise AND

Sure, if you store everyones calendars as bitmaps of free minutes, but that seems like a very inconvenient format for other operations.

Try having actual time ranges, not just slots, and you need to find, say, a 30m contiguous block of time.

Also not on weekends, or outside hours during the week, also not at lunch time, though it may be 'free', also not 5PM, who's paying attention to a meeting then?

(just examples of what i might consider when setting up a meeting manually)

It is still just bitwise if you model the time slots e.g. like one bit stands for 5 or 1 minutes and then look for some contiguous 'free'-block in the result

Okay, how do you find a string of N 1's in a very long bit pattern? What's the space and time complexity of your solution? (hint: you can do a lot better)

Reply on news.ycombinator.com