Home

Flunking the Coding Interview

Most hackers come to dread the coding interview. It’s a labyrinthine rigamarole that rarely tests your ability to perform your job. I’ve been on both sides of the table; and as both an interviewer and interviewee I can say that the process is absolutely gameable.

Interviewers understand that candidates cram for common coding questions and the best interviewers evaluate you based on the way you approach the problem, not on your final solution.

Despite the shortcomings of a whiteboard interview, it remains a barrier between many would-be hackers and a steady paycheck for applying their skills. Let’s reduce the stakes and do a practice run: I’ll purposefully botch the interview by choosing the wrong algorithm and still pass with flying colors. If you dedicate a little time learning what interviewers actually care about, you’ll breeze through and start getting paid.

The Problem

I started running a trendy peer-to-peer network (hermie!) and need your help finding the shortest route between two nodes of my network. I’ll give you a sample network representing nodes and their immediate neighbors which looks like this:

import qualified Data.Map.Strict as M

network = M.fromList [
    ("Jake",     ["Arnold", "Omega", "Frank"]),
    ("Arnold",   ["Jake", "Chomsky"]),
    ("Omega",    ["Jake", "Taliyah", "San", "Chomsky"]),
    ("San",      ["Omega", "Frank"]),
    ("Taliyah",  ["Omega", "Larry", "Arragon"]),
    ("Larry",    ["Taliyah", "Arragon", "Rengar", "VoidStar"]),
    ("Arragon",  ["Taliyah", "Larry", "Liam", "Nathan"]),
    ("Chomsky",  ["Nathan", "Omega", "Arnold"]),
    ("Frank",    ["San", "Jake", "Scott"])]

Each node can only send messages to their immediate neighbors. For example, Jake can send a message to Arnold, Omega, or Frank, but can’t send a message directly to Chomsky.

I want you to implement a function which finds a shortest path between two nodes. The function signature should look like this:
shortestPath :: Text -> Text -> M.Map Text [Text] -> Maybe [Text]

Reduce Cognitive Overhead

How do we go about approaching this problem? Before jumping into a choice of algorithm or considering runtime complexities, it’s important to reduce cognitive overhead as much as possible. Taking a few minutes to do this at the start of the problem by defining type aliases for common types will show returns throughout the entire problem solving process.

type User = Text
type Path = [User]

type Network = M.Map User [User]

Now we can redefine the type signature of the function that we’d like to implement as:

shortestPath :: User -> User -> Network -> Maybe Path

Much more clear. It’s immediately evident what arguments this function takes and exactly what it should produce.

Determine a Suitable Algorithm

Next we turn our focus towards a choice of algorithm which is appropriate for this problem. In problems exploring trees or graphs, two common algorithms worth considering are depth-first search and breadth-first search. Understanding these two algorithms will give you an easy out for a high percentage of interview questions.

So how do we choose between them? Start by considering a depth-first search to find the shortest path. A depth-first search will take a single possible path and explore it until the very end before considering any other path. If we explore one option using a depth-first search, we still have to look at every other option since we can’t say for sure that the path we chose is the shortest. This guarantees some measure of inefficiency!

In our case, we only care about the shortest path possible, and ideally we’d like to be able to stop as soon as we find any valid path. A breadth-first search can give us that guarantee. If we go down all paths at once, taking a single step in each, then we know that we can stop looking as soon as any of those paths turn out to be valid. There is no possible way to find a shorter path since we looked at all options each step of the way. If a path was shorter, we would have found it earlier and stopped looking!

Naive Implementation

That said, sometimes you don’t choose the right search algorithm, and if your interviewer is wiley, they will let you discover this on your own. Let’s walk through a hypothetical example where you chose to solve this problem using a depth-first search, and explore how you could discover your mistake.

When doing interview problems, the most common mistake is to worry about getting the perfect implementation and complexity guarantee on the first try. I’ve seen so many bright candidates who get trapped in analysis paralysis. It’s much better to complete a naive solution first, then at the interviewer’s prompting, refine the solution.

import           Control.Monad   (join)
import           Data.Foldable   (find)
import           Data.List
import qualified Data.Map.Strict as M
import           Data.Maybe
import           Data.Text       (Text)

firstJust :: [Maybe a] -> Maybe a
firstJust = join . find isJust

shortestPath1 :: User -> User -> Network -> Maybe Path
shortestPath1 from to network =
  dfs to [] $ network M.!? from
    where dfs :: User -> [User] -> Maybe Path -> Maybe Path
          dfs to path mNeighbors = do
            neighbors <- mNeighbors
            case to `elem` neighbors of
              False ->
                firstJust $
                  map
                    (\n -> dfs to (n:path) (network M.!? n))
                    neighbors
              True -> Just $ to:path

There’s a few techniques I want to highlight in this approach:

Define a Recursive Sub-Function

This is an extremely common technique. Often when solving a problem functionally, you want to recurse with a slightly modified set of arguments. In this case, I needed to lookup the set of neighboring nodes before starting the first iteration of depth-first search.

Join to Reduce Monadic Layers

Note in the firstJust function we use join to get rid of an extra layer of the Maybe monad. This works well in this situation since we directly return the result of firstJust. If we wanted to use the inner monadic value in another function, the >>= or bind function would be more appropriate.

Handle Maybes Using Do-Notation

When we lookup the neighbors of a node, we don’t know for certain that the node actually exists in our network. To handle this case, we use the Maybe monad. When you’re thinking about the implementation of a depth-first search, remembering that a search could fail is an example of cognitive overhead.

Try to abstract away this detail as early as possible. In this case, we can use do-notation to fail early if mNeighbors happens to be Nothing. After that we can assume that it returns a valid list of neighboring nodes.

Test Cases

Often the interviewer will want you to define your own test cases. This lets them see what sort of problems you’ve encountered in the past and how you think about edge-cases. Putting extra thought into this area is extremely important for security facing roles. The interview is essentially asking you to perform a security focused code-review on your own code. This is a common task for most security engineers and they will be keen to see what cases you check.

If you’re following along at home, try to come up with tests which would cover the following cases:

Null Cases

The first thing you should always think about is null input. What happens if to or from doesn’t exist in the network? What happens if there is no valid path?

In our case, these issues were solved in advance by using the Maybe monad. We simply return Nothing if the path doesn’t exist due to firstJust.

Infinite Loops

What if one of the paths we explore contains a cycle? Will the code loop indefinitely? Spoiler: The answer is yes! This was my first implementation and I didn’t think to track which nodes we had already visited. As a result, any cycles in the graph will result in an infinite loop.

This is a common mistake, and interviewers expect people to make it under pressure. The key will be seeing how you diagnose the issue and identify a solution.

Expected Output

When we run this implementation on input which doesn’t produce an infinite loop, we notice that our path starts with the recipient and works backwards to the sender. This is the reverse of what one would expect a shortest path to produce.

This is a result of using the (:) or cons operator which adds elements to the start of the list while we were building our path. Reversing the list at the end is a simple fix, but the bug was not immediately evident while writing the code!

We also can see that the path returned by our function isn’t actually the shortest path. firstJust returns the first valid path, which is not guaranteed to be the shortest.

Iterate and Debug

Let’s improve our implementation by addressing the infinite loop and expected outcome problems. We have already built a path of seen nodes for each option in our depth-first search. If we tweak our algorithm to filter out any neighbors which are in our current path, then we should be able to avoid the infinite loop error.

To actually obtain the shortest path, we can sort the list of possible paths at each step and take the head of the list. Since we sorted the list by length, this is guaranteed to be the shortest path. Then we just have to reverse the final list to get our desired output.

import           Data.List
import qualified Data.Map.Strict as M
import           Data.Maybe
import           Data.Text       (Text)

shortestPath2 :: User -> User -> Network -> Maybe Path
shortestPath2 from to network = reverse <$> dfs to from [from]
    where
      dfs :: User -> User -> Path -> Maybe Path
      dfs to next path = do
          neighbors <- network M.!? next
          case to `elem` neighbors of
            False -> listToMaybe $ sortOn length $ mapMaybe
                (\n -> dfs to n (n:path))
                (filter (not . (`elem` path)) neighbors)
            True -> Just $ to:path

mapMaybe

It is easy to get lost in multiple layers of Maybe contexts. Whenever possible I’d recommend trying to abstract the details of monadic contexts as soon as possible so they don’t clutter your thinking. In this case we can use mapMaybe to discard the Maybe context and keep only the valid items.

Functors (<$>)

The utility of functors cannot be overstated. Although we are dealing with values that may not exist, we never have to validate this fact. When we reverse the list at the end of our implementation using reverse <$> dfs ... we are taking advantage of the (<$>) or fmap operator to convert the regular reverse function to a reverse function that works on the Maybe monad. Always operate in the highest monadic context to reduce cognitive overhead.

By converting all our functions to work in the highest monadic context (Maybe in this case), we can pretend that we’re operating on the inner data. This prevents us from having to think about possibly non-existent values and frees up our mind to think about the happy path implementation!

Repeat Tests and Optimize

Re-run the tests you derived for the infinite loop and expected output cases. Did they pass?

If you’ve followed this example to the letter, they should have! Now that we have a functional solution it’s time to to think about run-time. Typically a breadth-first search or a depth-first search should run in O(N + M) time where N represents the number of nodes and M represents the number of connections between these nodes.

Does this implementation match that runtime? If you look closely at the way we are sorting our possible lists, you’ll see that it does not. Because we sort the list of possible options at every single step of our depth-first search, the runtime complexity is actually O(N + M*N(log N)).

To solve this problem, we need to move our sorting to the very end of the process so that it’s only performed a single time.

import           Data.List
import qualified Data.Map.Strict as M
import           Data.Maybe
import           Data.Text       (Text)

shortestPath3 :: User -> User -> Network -> Maybe Path
shortestPath3 from to network = sortOn length <$> dfs to from [from]
                          >>= listToMaybe
    where
      dfs :: User -> User -> Path -> Maybe [Path]
      dfs to next path = do
          neighbors <- network M.!? next
          case to `elem` neighbors of
            False -> Just $ concat $ mapMaybe
                (\n -> dfs to n (n:path))
                (filter (not . (`elem` path)) neighbors)
            True -> Just [to:path]

Concat

Note that now we utilize the concat function to add all our found paths together and sort a single time at the end.

Final Runtime

So after making this change, what’s our final runtime? Well we still have to walk the list of nodes, walk all their edges, and sort the final list. This results in a runtime of O(N*log N + N + M).

Wait a minute — this runtime is still worse than the expected O(N + M) because we have that pesky final sort! At this point you can clearly see that the runtime overhead results from the final sort and can start thinking of ways to eliminate it.

As an interviewer, if a candidate was able to walk through and refine a solution using a sub-optimal algorithm, I would be impressed. If they demonstrated how they identified the inefficiency in that algorithm, I would be more impressed than if they just knew the answer!

Interviewers understand that people memorize solutions and are looking to see how you approach and debug a problem. They won’t care if you can recite a memorized StackOverflow solution. The product is less important than the process the candidate used to arrive at the solution.

Afterword

If you liked this article, I wrote a second one! It explains how to use Dynamic Programming in a Functional Programming language.

I hope that this walkthrough helped you see visualize common stumbling blocks and explore methods to demonstrate your problem solving process in a technical interview. If you’re preparing for your first technical interview, I’d highly recommend taking a look at Interview Cake. I’ve used them a couple times and find that the step-by-step content they offer is absolutely worth the money.

If this guide was helpful to you, or if you have comments about this article, please feel free to reach out. I want to hear what you think! If you want to see more content like this, view the archive, subscribe to my newsletter or support me on Ko-Fi.