Fork me on GitHub

Hey anybody want to help me with an interview problem?


I don't know the exact problem yet but I know what the nature of the problem is...


Basically there are cabins that you rent out by the night, and people want to make reservations


Say you have 4 cabins and 10 guest-groups that are going to stay in them over the course of a month


The task is to find a good packing of timeslots so that all the guests get their preferred days and we also minimize the number of "gap days" or one-day-span free slots, since it's hard to rent out a remote cabin for just a single night.


why are we not maximizing profit ?


Well, it kind of leads that direction. profit will increase with more reservations, we just want to pack them efficiently so that when new reservations surface we don't have fragmented days that we can't rent out.


But you're saying that maybe the cabins are different prices, and therefore we would want to maximize cha-ching$$


I'm just focused on the leave-no-one-day-gaps issue at the moment. But you're right, that's probably a smart way to go ...


These details are important; they determine what algorithm should be used.


I have not received any details yet


But I was given a generous hint ^


So, I'm trying to do my mental prep beforehand ^^


but let's say instead of maximizing profit$ we are maximizing the number of contiguous stretches of free days...


packing is NP complete, so it's good you only have small numbers to work with


Yeah, that's true! I was thinking ... np-complete, but then noticed there are quite a lot of "restraints" so-to-speak. It's 2D which is convenient, and it's possible to brute-force over all the solutions. It's certainly an interesting exercise


A lot of places do set quantities of days for rental (e.g. Fri to Mon, Fri to Fri, Mon to Fri, and Mon to Mon). You could possibly work that into the mix if they'd consider that route. It would negate the single day gap issue


so i'm actually building a booking platform and i can tell you that much of the complexity of the entire exercise is in how to deal with booking and pricing rules


aligning week-long bookings to start on a monday is a common thing, for example


it would help if you had historical bookings data to determine how different strategies have fared in the past