4 ms·

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

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.

CardenB 10y ago
Isn't that just a bit wise AND?
- enjo 10y ago
  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.
  - karussell 10y ago
    It is still just a bitwise AND
    - TorKlingberg 10y ago
      Sure, if you store everyones calendars as bitmaps of free minutes, but that seems like a very inconvenient format for other operations.
- dsymonds 10y ago
  Try having actual time ranges, not just slots, and you need to find, say, a 30m contiguous block of time.
  - bobbles 10y ago
    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)
  - karussell 10y ago
    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
    - dsymonds 10y ago
      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)

CardenB 10y ago

Isn't that just a bit wise AND?

enjo 10y ago
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.
- karussell 10y ago
  It is still just a bitwise AND
  - TorKlingberg 10y ago
    Sure, if you store everyones calendars as bitmaps of free minutes, but that seems like a very inconvenient format for other operations.
dsymonds 10y ago
Try having actual time ranges, not just slots, and you need to find, say, a 30m contiguous block of time.
- bobbles 10y ago
  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)
- karussell 10y ago
  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
  - dsymonds 10y ago
    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)