This is exactly how to interview with me

I’ve been asking the exact same interview question for 15 years. This gives me an absolutely enormous (say, 500–1000) sample size of answers to compare to and a decent idea of where the applicant pool has been going over time. I still see novel solutions to the problem, even today, but, I’ve got to say, the quality of answers to this question has taken a steep dive over the last five years and I don’t know why.

Here’s the question: “Pretend I own a chain of hotels and I’m hiring you to write a hotel reservation system. Imagine there are no databases; everything the system does has to be done as the interactions of classes and data structures in memory. And you have infinite memory. What would the design or class diagram of this system look like?”

That is literally, verbatim, what I ask. I’ve asked it hundreds of times. I’ve seen some truly brilliant designs come out of this question. But, much more often, I’ve mostly seen horrendous-to-mediocre solutions come out of it. Interestingly, seniority seems to have essentially zero correlation one way or the other with the elegance of the candidate’s design.

The first part of this interview session is the only “trick question” part of the interview. I fully recognize that this question is somewhat ambiguous, exactly the way that business requirements from stakeholders are ambiguous. So I expect a very strong candidate to ask clarifying questions before just diving into a design. The very best always do. But most people don’t.

The very best kinds of questions are simple things, like:

• How many hotels do you have? How many rooms do they have?
• What kinds of rooms are in these hotels?
• Do I need to support different rates for different rooms or time periods?
• Do I need to support overbooking the hotel?
• Do rooms have things like optional amenities? Different bed sizes?
• Are guests allowed to reserve specific rooms, or do they need to just reserve a type of room and we’ll figure out which one, exactly, when they arrive? (This last question is very, very important. We’ll get to that later.)

Everyone has stayed in a hotel at least once. Hell, some of these candidates are staying in a hotel we put them up in to get to this interview. So, the concept of a hotel reservation system should not be some kind of special domain knowledge. If you don’t ask any clarifying questions then I let you flounder around for about five minutes and then I bail you out by saying:

“Let’s focus on one use case. Say someone calls up and asks if I have one, queen-sized, non-smoking bed for July 1 through July 4. How do the classes and data structures in the system interact with each other in order to answer this question?”

This is the end of the trick questions. Absolutely everything I say (including this question) from this point forward is an attempt to help you perform better. No, really. I think trick questions are lame.

From here on out, all I really care about is seeing you reason through all the tradeoffs inherent in this problem. Will you keep track of rooms that are booked, or rooms that are not booked? Why did you choose one over the other? Did you store reservations in a data structure that’s optimized for writing or optimized for searching? Why? Will you even bother to keep track of reserved rooms at all, or will you keep track of reserved room types and figure out the exact room later? Do you seem to understand that, for a computer, iterating through a list of only 500 items in memory is basically the same thing as iterating through a list of 2, performance-wise?

Historically, I used to get into really interesting discussions about these tradeoffs. These days, many of the candidates I’m interviewing don’t even understand that these tradeoffs are there and don’t have a clue what I mean when I ask about them. For that matter, literally 50% of the candidates I interview these days leave the concept of dates out of their answer entirely on the first go. Seriously. They design a reservation system that only understands what’s happening right now, not in the future or in the past. Like a big, dopey yellow lab catching a frisbee, their software lives perpetually in the moment, blissfully unaware of who’s going to arrive next, or when.

Anyway.

A really good candidate will tend to quickly create a solution that’s functionally correct and semi-efficient-ish, but has some room for optimization. That’s ok! In fact, I get excited if there’s room for optimization because that means we get to talk through the problem together and I get to see how you think.

Let’s take this straw-man solution, for example. Say we have one array containing one Room object for each room in the hotel, kinda like this:

rooms = [{roomNum: 1, bed: “queen”, reservations: {…}},
{roomNum: 2, bed: “queen”, reservations: {…}},
{roomNum: 3, bed: “king”, reservations: {…}},…..]

Say each “reservations” property is itself a map where the key is a date like “2018–07–01” and the value is true or false depending on if the room is reserved for that day. Not super efficient, but not horrific either and it can be reliably navigated to answer the question. The pseudo code for this might be like this (imagine “criteria” is a structure that holds things like “queen size non-smoking”):

def isAvailable?(startDate, endDate, criteria)
  foreach room in rooms
    if room.matchesCriteria(criteria)
      booked = false
      foreach date between startDate and endDate
        if room.reservations[date]
          booked = true
        end
      end
      return true if not booked
    end
   end
   return false
end

As you can see from my mishmash of Python/Ruby/Java/Totally Fictitious syntax, I don’t care what language you know or if you can create perfect syntax for it. I care about your algorithm. If you’d been performing really solidly up to this point, I won’t bother digging into how “matchesCriteria” works or what, exactly “criteria” looks like. If you’ve been a little shakey, then I will dig into them.

Some candidates never really get an answer that actually works correctly, regardless of how efficient or inefficient the solution is. In fact, it’s the people who try to prematurely optimize too dramatically that most often get incorrectly working answers. As a rule of thumb, if you’re trying to do things with bit fields and whatnot right from the beginning, you’re probably going to screw it up irrecoverably (and you’re hyper-optimizing something that won’t have a perceptible impact on performance, anyway). These people obviously don’t get hired, so let’s focus on people who do get correctly working answers.

After you’ve produced something that works, then I’ll ask “ok, that’s awesome. It’s going to work for our problem and get the right answer. Now, if you wanted to optimize it to go faster, what would you do?” Don’t be embarrassed by this question. Absolutely every first try at a problem has some inefficiency in it. The very best candidates own that and are willing to revisit their solution. Horrible candidates stick to their answer like a drowning person at sea clinging to a piece of driftwood and refuse to admit there are ways to improve it.

There are lots of things you could do. For example, you could keep the rooms themselves in a map instead of a list where the key to the map is the room type. That’s fine, but if you do that then I want to see that you’ve thought about partial matches, for example if someone definitely wants non-smoking, but they don’t care about what bed type they get. Maybe you’ll decide to flip the problem on its head and keep a map where the date is the key and the value is a list of available rooms. I’ve seen some really interesting answers that make use of set operations to come up with the verdict. Anyway, the main point is I’ll take whatever your answer is and probe you on all the places where you traded something off against something else and see 1) if you made that tradeoff with your eyes open, and 2) how you decided where to draw the line.

We work through the various ways to optimize the solution until we run out of them, or (more likely) I get a good enough idea of how you’re doing. That’s when I throw this at you:

“Ok, I want to throw a change in requirements at you. Not everybody knows this, but it’s common practice in the hotel industry to take more reservations in a day than you actually have rooms. This is because some percentage of people don’t actually show up, and we want to keep the hotel as full as possible. Let’s say I’ve done some data crunching and I figure I can take an educated risk and overbook my hotel by up to 10% on any given night without leaving anyone short of a room, most of the time. What would you have to change about your design, if anything, in order to accommodate this change in requirements?”

You always have to change something. Trust me. Only a half-dozen times in 15 years has someone not had to change anything.

At this point, people who designed the system to reserve specific rooms, as opposed to room types, are really hating life. That’s ok! You’re not in the hotel industry so I didn’t expect you to know that! Ok, once I actually did give this question to someone who had worked in the hotel industry. But only once. Boy was that weird.

Anyway, I fully expect you to have to refactor your design. The very best candidates are willing to revisit everything, if necessary. Mediocre candidates will only tweak their design around the edges the bare minimum necessary to get the job done. Horrible candidates will bludgeon their exact design into submission, forcing it to do truly unnatural things to avoid changing anything and, yet, somehow still get the right answer.

If you started your design with something that reserves specific rooms and you change it to something that reserves room types instead, you will blow my mind away. Very few people are willing to revisit their design to that extent mostly just for the benefit of getting the most elegant answer, beyond simply getting a correct answer. To a certain extent, if you’ve gotten this far, I don’t even care about what your solution is. What I really care about is how well you handle changing requirements and what you’re willing to revisit in your previous assumptions.

At this point, a good solution might look like this, where we have a map of maps like this:

room type => date => integer

Where the integer is the count of the number of rooms of that type that have been reserved for that day and the system checks that number vs the total number of rooms of that type that exist and returns true if it’s less than 110%.

If things are going really well, I throw a few more complicated variants of this changing requirement at you and see if you can accommodate them, too, and where you made tradeoffs.

That’s it. That’s the end of the interview. The whole process takes about 40 minutes and it very accurately surfaces the three things I truly care about when hiring someone:

1. Can you deal well with ambiguity?
2. Do you make tradeoffs with your eyes open and how do you weigh them?
3. Can you deal with change and revisit your assumptions or do you dig in your feet?
4. Ok, fine, the fourth thing is do you have a shred of software design sense? See, I revisited my design there by adding a fourth thing.

Those qualities, more than almost anything else (including if you’ve ever even worked in the language I’m hiring for) are the best predictors of your success on my team. And, so, I screen for them like a man on a mission.

Why am I giving away my one, prized interview question? Because you can’t study for it. It’s a conversation, not a single, correct answer. And I want better conversation. Please.