Coding Interview: painless and leetcodeless

When we talk about coding interviews, many people get flashbacks with topics from tree traversal to 14-hour take-home assignments.

I've been entertaining myself with interviewing for over a decade. For about five years, I ran the SRE Interview Club for fellow pager-bearers and built up a small set of my favorite questions. I ask them on a whim, depending on the moon's phase; they work for any situation.

It doesn't matter what language the candidate plans to code in (yes, I've even seen Perl from a manager who hadn't coded for a while), and it doesn't matter what level I'm interviewing for.

In theory, all my questions have long been analyzed and added to Google's internal list of banned questions -- but I've never received any complaints, because the signal is clear and distinct, which is the whole point of this shenanigan. :)

Let's look at one of my favorite questions. Get out your whiteboards or notebooks; we're starting to code on the board!

The Task

Imagine we've decided to launch a new product: a robot vacuum. The engineers have built a solid platform, the designers have created a beautiful look, we have our own cloud, and a wonderful framework. All the user has to do is place the robot wherever they want at home and press a button. The robot will connect to the cloud, where a function will be launched with an interface to the physical robot as its argument.

Roughly speaking, it looks like this:

class Robot:
    def Move(self) -> bool:
        """Moves robot 1 step ahead. Returns True on success, False if it hits an obstacle."""
        
    def TurnLeft(self):
        """Turns robot in place counter-clockwise 90 degrees."""
    
    def TurnRight(self):
        """Turns robot in place clockwise 90 degrees."""

def DoClean(robot: Robot):
    ...        

Our robots are already packaged and shipped, the platform is debugged, but one small thing is missing: no one has written the DoClean function. Your task is to write some kind of solution so that the robots stop being useless hunks of metal. We can always change it later, make it better, etc., but first, we need to get rooms clean.

Phase 0: Adapting the Task

This is one of those questions that requires virtually no adaptation when you ask it. All you need is a sufficient number of templates for different programming languages, so you can copy-paste the version for their chosen language into an online editor. (If a person is a senior with a dozen languages, I usually copy a different language than the one they chose for the interview, but one that is still on their list of experience.)

Phase 1: Discussing the Problem

Those who treat interviews like a job know that you have to discuss any problem before solving it. Those who don't will ask these questions sooner or later anyway. If not, I'll provide hints as we go, since time is limited, and I want to see their thought process.

Here are the questions that, in one way or another, affect the solution. The more of them asked before the coding starts, the better:

• Where exactly in the room is the robot located? => Anywhere, we don't control the user.
• What exactly is a "room"? Is it a rectangle? Or a convex polygon? Are there obstacles? => Basically "anything." We don't know where the user will place the robot. There might be obstacles, we don't control them.
• Do the obstacles move? => Great question... For the first version, let's assume no, but we'll definitely need to think about it.
• Is the polygon enclosed? What if the user leaves the apartment door open? => If the user leaves the door open, they'll have a very clean neighborhood.
• So, there's no limit on the room's size? => We would prefer not to limit it.
• Are all the corners 90 degrees? => The first firmware model can only move in a straight line and turn 90 degrees. We'll clean as best we can with that.
• What if an obstacle is in the middle of a step? => The robot will back up if it hits an obstacle, and we'll get False.
• Can the robot get stuck and not be able to turn in place? => A good question... We'll need to account for that in the next firmware version.

In principle, these answers should be enough to make it clear what's needed.

Phase 2: The MVP Attempt

Almost all candidates (often even those who asked all the questions and seemed to understand the task) begin to solve the problem by attempting to build a stateless algorithm. I suspect this is a matter of mental inertia ("Oh, a maze problem, you don't need state, just walk along the wall").

They write something like this:

def Clean(robot: Robot):
    while True: # I'll fix this later
        if not robot.Move():
            robot.TurnRight()        

Oh, wait, that won't work. Maybe I need to first get to a corner, and then do something else:

def Clean(robot: Robot):
    while robot.Move(): # Go to the wall
        pass
    robot.TurnRight()
    while robot.Move(): # Go to another wall
        pass
    robot.TurnRight()
    # Now we're in a corner, and looking along a wall

    while True: # I'll fix this later
        while robot.Move():
            pass # Go to the opposite wall
        robot.TurnRight()
        if not robot.Move():
            break # We're in a corner!
        robot.TurnRight()
        while robot.Move():
            pass # Go to the top wall
        robot.TurnLeft()
        if not robot.Move():
            break # We're in a corner!
        robot.TurnLeft()
        # Done, we're at the top wall again, looking down        

Somewhere around this point, if the candidate hasn't figured it out themselves, I hint that there are, in fact, obstacles in the room. And that the room isn't necessarily rectangular. Even if it is, the robot might not have started facing perfectly along the walls. In short, you can't rely on an inductive algorithm. For every attempt to complicate it, it's easy to create a counterexample that makes the entire heuristic fall apart.

So, after about 10 minutes, we nudge them toward the next phase, if the counterexamples weren't enough.

Phase 3: Recursion - See Recursion

Okay, if we can't be stateless, we'll solve the problem differently. The room is an N by M rectangle. Let N and M be a thousand. Or 10 thousand. Computers are powerful, there's plenty of memory, so why not? We start at coordinate [0,0]. (Pause for 2-3 seconds.) Oh, no, let's start at [N/2, M/2]. Let's assume "forward" means "looking up." And we just recursively fill the entire area: for each cell, we try to go up, left, right, down. If we hit a wall, stop. If we hit a spot we've already been to, stop. Otherwise, we remember that we've been there and recursively repeat. A perfect solution, ideal for an MVP, and it guarantees that "everything accessible is processed."

So, we aim for something like this:

state = set()

def Clean(robot: Robot, x=0, y=0):
    state.add((x,y))
    if (x,y-1) not in state and robot.Up():
        Clean(robot, x, y-1)
    if (x,y+1) not in state and robot.Down():
        Clean(robot, x, y+1)
    if (x-1,y) not in state and robot.Left():
        Clean(robot, x-1, y)
    if (x+1,y) not in state and robot.Right():
        Clean(robot, x+1, y)        

When a candidate writes this, I'm happy on the inside! Because often they write something else:

def Clean(robot: Robot):
    state = dict()
    while True:
        for range(4):
            if robot.Move():
                ...
            robot.TurnLeft()        

And then they try for a long, long time not to get confused about their position. The only way is to hint that even though the Robot only knows how to go up-down-left-right, nothing prevents us from encapsulating it in a helper class that will track position and direction and provide the necessary methods.

Once the person gets to this point, things usually go smoothly. The wrapper class is sketched out in a minute, the main code quickly boils down to something similar to the example above, and you can say the job is done.

The only thing left is to clarify why, instead of cleaning everything if you start in the middle, you get a strange infinite loop. We give an example of a small room, and the person walks through the code manually...

And fixes it:

Usually, the fix involves modifying the function so that upon exiting Clean, the robot is always in the same place it was before entry, possibly even keeping the same direction—but in the general case, the direction doesn't need to be saved. You can just replace Up/Down/Left/Right with North/South/West/East methods and be happy with the obviousness of this approach.

Phase 4: Making It Better

Rarely is there enough time at this point for more than a discussion, but it's essential to ask about the algorithm's complexity. And then we drop a hint: What about memory? And why does trying to clean a 50x50 room with the robot cause an exception? (That's for Python, we guide them to the same question via a slightly different route for other languages). Yes, recursion is a depth-first search, and the depth is directly proportional to the number of cells. Python's default recursion depth is only 1000, so a 32x32 room or larger will cause an overflow.

Also, we can remember that obstacles don't necessarily occupy an entire cell: a thin wall is possible, where you can't pass from [0,0] to [0,1], but you can from [1,1] to [0,1]. What's notable is that this problem doesn't manifest in all the implementations that are typically produced by this point in the interview. For example, the solution above is immune to it.

We can also ask: How can we avoid traversing the same spot multiple times? The battery isn't infinite. Of course, we said we'd handle optimization later, but what if something can be done now?

In general, you have to throw in enough constraints to make the person think and switch from a brute-force approach to an intelligent traversal.

Of course, the first step is to rewrite the recursion into a loop:

def Clean(robot: Robot):
    state = [(0,0)]
    while state:
        x,y = state.pop(0)
        robot.MoveTo(x,y)
        ...        

At this moment, they realize we need MoveTo, and if we need MoveTo, we need a map search (how else would we get there?), which means we need to track not just the map but also the state of the connections (see above about thin walls), add a search for the nearest unvisited cell, and so on.

All of this is a lot of fun and can fill any remaining interview time, even if the interview isn't for a game dev position (and if it is for game dev, the A* should be organic; absolutely no libraries!).

Phase 5: Wrapping Up

Regardless of how the candidate is progressing, at the beginning of the interview, I always say that the question is infinite, that we'll finish on a timeout, and that not finishing what you're doing at that moment means nothing.

Therefore, strictly on a timeout, we stop the interview. The timeout is chosen to always leave about 5 minutes for the candidate to ask questions in return.

In the case of a double interview (coding + system design), it's the perfect time to tell a joke about a sysadmin. After that, we move on to system design:

Excellent, now let's design a system that will allow us to service these robots in such a way that the user just presses a button on the robot, and everything is done in the cloud, where the specified Clean function is launched.

Phase 6: Report and Analytics

During the interview, I take regular snapshots of the code after each checkpoint: a pause for thought, a "I did it!" moment, or before each hint. I also try to write down the candidate's words as accurately as possible, plus I record what hints I gave and how the question was phrased. There's no time to write everything down, so I use a compressed form, which I expand right after the interview while it's fresh in my mind.

The report is set aside for 1-2 days, then reread and analyzed with a fresh perspective.

Evaluated:

• Analytics: What the candidate asked about at the beginning, how they resolved contradictions, what assumptions they stated explicitly, and what they left implicit;
• Architecture: How the code was structured, in what order the solution was built (bottom-up or top-down);
• Reliability: Were there attempts to make the code testable? Did the candidate even try to test the code? Did they build invariants?
• Readability: Was there an attempt to make the code readable? Were there comments, function breakdowns, and function naming?
• Adaptability: How did their thoughts change when the task requirements changed or when previously hidden constraints necessitated throwing out the current solution?

NOT evaluated:

• Indentation, ijkl internal variables, CamelCase vs snake_case vs THIS_IS_THE_BEST_JAVA_VARIABLE_BY_SOME_ONE_WHO_ONLY_HEAR_ABOUT_JAVA_ONE_IN_THEIR_LIFE_BUT_THEY_CANT_STOP_GIGGLE_ABOUT_IT.
• Code compilability.
• Order of arguments for system functions.
• Existence of system functions.
• Sorting of imports.
• The imports themselves.

Other Questions

What else can be asked (instead of walking over matrix)?

Essentially, I ask something from this list:

• How to sum the leaves of an arbitrary tree in O(1) space.
• How to find a node in a tree based on an arbitrary condition.
• How to implement an LRU cache.
• How to implement a linked list.

And none of these questions are asked in their literal form. They are always presented as a hypothetical task that could be a real one. Because understanding the problem is 80% of the task. The coding is just the other 80%...