My Code Interview

I used to ask many interview questions to test knowledge in different areas. I still do that to fill time, but most of my interview is filled with one large coding question instead. I realized somewhere along the way that coding is the great interview equalizer. Some candidates feel more confident when coding. It gives them a better chance to succeed at showing me they can do the job they’re interviewing for. Other candidates can answer questions of theory and give textbook explanations all day long, but haven’t written a line of code in years. I don’t want to hire people like that.

I wanted to find a coding question that avoided common pitfalls that make the candidate feel stupid or don’t tell me anything about them.

I think I found one that fits these criteria.

A Note About Languages

This interview question was designed around OO languages with static typing. I generally let the candidate choose any language they want, but most people are comfortable with at least one OO language, and of those, most consider it their primary language. Most of those people use Java, so I’ve written this entire thing in Java. I’ve seen people write it in C# and that works well. I’ve rarely seen someone attempt to use something like Ruby, Python, or JS, and this problem doesn’t lend itself to those sorts of languages in my opinion. It’s my primary issue with this question.

The Setup

(I am typing absolutely everything I can remember being asked by candidates. How much detail you provide initially is up to you, and I guarantee you will forget some details until asked by the candidate, or you see the candidate doing something dangerous because they made a bad assumption. Most of these details are designed to handwave away the less important aspects of implementation and focus on the important parts of the problem.)

I am building a system to schedule meetings or reserve people’s time.

interface Resource {
    // Sorted, non-overlapping
    List<DateRange> getBusyTimes(Date start, Date end);
}

This is the only exposed API into the system I’ve written so far and I want you to program against it. Breaking down the interface,

DateRange is a simple model class

class DateRange {
    Date start;
    Date end;

    // ctor(s), getters, setters
}

It represents a simple continuous slice of time. start and end are exclusive, meaning that two adjacent DateRange objects may have the same value for the end of one and start of the other without being considered overlapping.

Part 1 - Easy

I never used to ask this part of the problem and just jump to part 2, but I had trouble getting anyone to make enough progress on part 2 to make a good judgement. The unfortunate consequence of asking part 1 is that it tends to imply something about the solution to part 2 that isn’t optimal, but we’ll get to that later.

The actual problem is implementing this function:

List<DateRange> getFreeTimes(Resource r, Date start, Date end);

Given an instance of a class that implements Resource, and two Dates, find all the times when that Resource is free.

Solution

This is my favorite solution, and I believe it is basically optimal.

List<DateRange> getFreeTimes(Resource r, Date start, Date end) {
    // Validate start/end
 
    List<DateRange> busyTimes = r.getBusyTimes(start, end);
    List<DateRange> freeTimes = new ArrayList<>(); // I don't care which List implementation
 
    Date walker = start;
    for (DateRange busyTime : busyTimes) {
        if (busyTime.getStart() > walker) {
            freeTimes.add(new DateRange(walker, busyTime.getStart()));
        }
 
        walker = busyTime.getEnd();
    }
 
    if (end > walker) {
        freeTimes.add(new DateRange(walker, end));
    }
 
    return freeTimes;
}

Solution Notes

Candidate often realize they need to do a loop. That loop also needs to consider more than one element in the list at a time, so a naive approach often is to use a for-loop instead of for-each. This runs a higher risk of accounting for the same free block twice, or failing to account for free blocks.

Special cases: - Empty busy times list - Gap/no gap between start and first busy start - Gap/no gap between last busy end and end

Signs of danger: - Doing arithmatic on Dates. Subtraction seem especially common. - That’s disallowed according to the setup, but… - Ask the candidate to describe conceptually what happens when they subtract 1pm from 2pm and how it helps them solve the problem - Converting Dates to numbers or strings - Again, not allowed, but… - Ask why. Usually I see this happen when the candidate assumes some minimum increment (one minute? five minutes? one hour?) that doesn’t exist.

Evaluation

This is something I struggle to explain and there’s nuance in every single interview. I will focus on only very general observations in aggregate that I have seen to be generally true. Even if someone satisfies these criteria, it’s up to you to judge the code they actually wrote, their problem solving process, their willingness to ask questions and communicate, personality, and many other factors. I am merely hoping this coding problem gives you the opportunity to evaluate all those factors.

Entry level/junior developers should be able to get through this part in about 30-40 minutes with coaching from the interviewer.

Mid level should be able to solve it in ~30 minutes and require minimal/no coaching.

Senior level should be able to solve it in <30 minutes with minimal/no coaching.

If you feel like you have the time, begin part 2

Part 2 - Hard

Implement this function

List<DateRange> getFreeTimes(List<Resource> resources, Date start, Date end);

Find the list of free times that all provided Resources have in common. You have access to your implementation from part 1 because it would be unfair to take that away from you.

Solution 1 - Using the Busy Times

List<DateRange> getFreeTimes(List<Person> people, Date start, Date end) {
    List<DateRange> busyTimes = new ArrayList<>();
    // or something else clever with streams
    people.stream().forEach(p -> busyTimes.addAll(p.getBusyTimes(start, end)));

    // If they ask to sort the list, I don't need them to write real code here.
    // sort(list) is enough for me. It's not important.
    Collections.sort(busyTimes, DATE_RANGE_COMPARATOR);

    List<DateRange> freeTimes = new ArrayList<>();

    Date walker = start;
    for (DateRange busyTime : busyTimes) {
        if (busyTime.getStart() > walker) {
            freeTimes.add(new DateRange(walker, busyTime.getStart()));
        }

        if (busyTime.getEnd() > walker) {
            walker = busyTime.getEnd();
        }
    }

    if (end > walker) {
        freeTimes.add(new DateRange(walker, end));
    }
        
    return freeTimes;
}

Solution Notes

The most important insight to make when solving part 2 is thinking about what happens if you consider the free times vs. the busy times. Most times, the candidate will immediately assume they need to consider the free times, because that’s what they just spent 30 minutes coding in part 1 (which is why I lament having to ask part 1 at all). However, some simple analysis of the problem may change their mind.

An instant in time is part of the output if ALL Resources have that instant in time free

Conversely,

An instant in time is part of the output if ANY Resource has that instant in time busy

Consider the relative difficulty of counting any vs. all in a system where the instants in time are arbitrarily precise. In my solution above, it’s enough to solve part 2 by solving part 1 without the caveat that getBusyTimes returns a sorted, non-overlapping list. The presence of any busy time is enough to disqualify the segment as a free time.

Generally, I let the candidate begin solving and implementing however they choose to do it. Once they run out of time, I try to guide them into making the above insight. Sometimes they consider the busy times without explicitly making the above insight. I find that many good programmers are good because they have good instincts. The truly great programmers can examine those instincts and figure out why they’re good, and maybe find something even better.

Complexity is a good discussion topic as well. My solution is roughly O(NlogN) for certain definitions of N.

Solution 2 - Using The Free Times

eventually…

Evaluation

Choosing the more complex route is not failure, in my mind. The discussion I get out of working through this problem with the candidate is my basis of judgement. Working through a problem together is a good way to see if the candidate would like to tackle problems like these in the workplace, or if they’re too dense or stubborn or confused. I also look for what questions they ask me and what assumptions they make. Challenge their assumptions and ask why they made them. If they ask for the ability to do something irrelevant or dangerous, ask them what they intend to do with that ability and work through it with them.

If they can solve this problem sight unseen within the 45 minute or even 1 hour interview, they are really really smart and if nothing else, they can be taught. Whether they’re a good cultural fit is another story, but you should be able to figure that out by working on this problem with them.