The interviewer got on the call and, without saying a word, immediately dropped a problem on me.
I think I'd seen fragments of this one on the forum before — the hotel split stay problem. But I'd only ever seen little snippets of the description and didn't remember the actual problem in much detail, so I basically treated it as a brand new question.
The gist of the problem: it's about booking rooms on Airbnb, and how you can split one continuous date range across two different listings. Simplified, you're given n hotels, each with a list where the numbers represent the dates that listing is free, plus a requested date range [start_date, end_date].
You need to split that range into two consecutive segments, such that one hotel can cover the left segment and a different hotel can cover the right segment, and the two segments can't overlap backward — only forward. You have to return the matching hotel combinations, with no duplicates.
My approach was to first compress each hotel's available dates into contiguous ranges, then scan every possible split point, checking whether the left half could be covered by some hotel and the right half by another.
They required the code to be bug-free live, with every test case passing, so I ended up spending a lot of time debugging in the middle and handling deduplication. That meant I didn't have time left to get to the follow-up question, and my solution also didn't seem to be optimal. In the end I failed this round.
Going into this interview, even though a lot of the interview questions here looked familiar, I only ever had a rough sense of them, not a real understanding.
Discussion
Loading comments…