More On Coding Interview Tests §

The problem of coding interviews §

I find myself again considering a new software engineering job, and that means going through the dreaded coding interview. I’ve written previously on this topic, and I expect I’ll write more in the future.

I don’t think they are the best way to assess a candidate’s skills, but I also don’t know that I have a better suggestion. A blog post by Seth Corker talks about the pitfalls of this approach:

The idea of a technical interview where you have to recall obscure computer science trivia and jargon might not be a useful measure. It focuses on specialised knowledge that favours particular types of people. People who are capable of holding facts and algorithms in their head rise to the top. It’s not a great measure of skill and when used incorrectly it can be entirely meaningless.

~ Practicing Code Interview Questions is Like Studying For the Exam

My preferred answer to these sorts of questions is to say that I wouldn’t implement a data structure or algoritm from memory, I’d go research the solution, try to find an existing solution I can reuse. If I was forced to implement one because there isn’t an existing solution, then I’d probably learn as much as I can on the subject before trying to implement it. This goes doubly so with anything involving cryptography, with self-implementation being a big red flag.

But while in my mind that’s the best answer, it’s seldom sufficient for these things.

The popular dynamic programming problem §

A common type of coding question involves something known as dynamic programming. I remember learning about it back in college, but it’s not something I can easily recall at the drop of a hat, nor is it something I’ve ever had to know for any job I’ve had outside of these sorts of coding tests.

I haven’t implemented one of these in a while, so I’m going to walk through one today. I’ll be using Elixir for this, since it’s my language de jour and because I can provide a Livebook for this content, where you can play around with the code yourself (see the button at the top of this page).

This does complicate the solution because Elixir is a fairly pure functional language, which means immutable data structures, and most of the traditional CS algorithms and data structures are presented with an imperative solution. If this were for a real Elixir application and I had to write it myself (because of no existing solution) and performance were a real concern, I might consider writing a NIF in Rust using rustler.

There are two properties that a problem must exhibit in order for this to be a useful technique to apply.

1. The first is optimal substructure, which means that the solution to a problem involves solving smaller versions of that same problem.
2. The second property is overlapping sub-problems, which is where the smaller problems that need to be solved to solve the bigger problem involve repeated instances of those smaller problems.

A simple example is an algorithm to calculate the $n$th Fibonacci number. The mathematical definition of the Fibonacci sequence is:

$$\begin{align*} F_0 &= 0 \\ F_1 &= 1 \\ F_n &= F_{n-1} + F_{n-2} \end{align*}$$

Because $F_n$ depends on the values of $F_{n-1}$ and $F_{n-2}$, it means that those values will get calculated multiple times. For example when calculating $F_{n-1}$, we have to compute $F_{n-2}$ and $F_{n-3}$, and so on.

One solution to this problem is memoization, where we save the results of previous function calls and use the cached values when we need them again. This leads to the top-down approach to dynamic programming.

The other approach is to work from the base case up to the case we want to solve, and building a cache of results up as we go. This is the bottom-up approach.

Longest common subsequence §

A popular form of dynamic programming problem that shows up a lot in coding interviews is the longest common subsequence problem. It’s used in things like calculating diffs in Git or other version control software, as well as other applications.

Given two sequences $X$ and $Y$, return the longest common sequence of elements shared between them. The elements do not have to occupy consecutive indexes in the two sequences, i.e. there can be gaps.

There are two key insights that help us solve the problem using dynamic programming. The first is that the length of the common subsequence of two sequences that end in the same elements is equal to the length of the longest common subsequence of those two sequences with those elements removed, plus the length of the removed elements (usually we go one element at a time so this ends up being 1).

$$LCS(X + A, Y + A) = LCS(X, Y) + A$$

The second insight is that if the last element of each sequence, let’s call them $A$ and $B$, differ, i.e. $A \neq B$, then the longest common subsequence between them will either be from the longest common subsequence of $X$ with $A$ removed and $Y$, or from the longest common subsequence of $X$ and $Y$ with $B$ removed.

$$LCS(X + A, Y + B) = \max(LCS(X, Y + B), LCS(X + A, Y))$$

The first property gives us optimial substructure and the second gives us overlapping subproblems. So let’s apply some dynamic programming to this problem. We can use this convoluted definition I pulled from Wikipedia, which just says that the longest common subsequence up to some indexes $i$ and $j$ in each sequence, i.e. a sequence prefix, is dependent on the values of $i$, $j$, and whether the last elements match.

$$LCS(X_i, Y_j) = \begin{cases} \epsilon &\text{if } i = 0 \text{ or } j = 0 \\ LCS(X_{i-1}, Y_{j-1}) + x_i &\text{if } i,j > 0 \text{ and } x_i = y_j \\ \max\lbrace LCS(X_i, Y_{j-1}), LCS(X_{i-1}, Y_j)\rbrace &\text {if } i,j > 0 \text{ and } x_i \ne y_j \end{cases}$$

Enough math notation, let’s try to code this.

We’ll start with some basics. Let’s say we have two strings or lists of characters, and we want to find the common subsequence. I’m going to walk through some of the steps to finding the result and at the end we’ll pull it all together into a proper implementation.

Elixir lists and the definition above

In the definition above, we’re defining the prefixes $X_i$ and $Y_j$ in terms of the elements that came before it, deciding which branch to take based on the elements at the end.

Elixir lists are like Lisp lists in that they’re recursively defined as a head element and the rest of the list. As a result, my implementation considers the elements at the start of the prefixes instead of the elements at the end and recurses on the rest of the prefix lists.

One way to think about it is that we’re looking for the longest common subsequence in the reverse of the two sequences and then building up the answer in reverse. As we’ll see, the result ends up being the same.

We’ll define some test data first that we’ll reuse as we go along. The first is pulled from another article on this topic (I was searching for large test cases) and the second one I generated two sequences randomly.

# A simple test case
#
# The result should be 7 for "reipito"
x1 = "serendipitous" |> to_charlist
y1 = "precipitation" |> to_charlist
 
# Larger test based on comparing DNA sequences
#
# They're split across lines to keep the line length reasonable. The
# concatination will be handled at compile time, so it will have no
# effect on performance.
# The result should be 62
x2 = "GGATCAGAGAATGGAATCTCAGCCAGCGCATTGCAGTAGTGGGAAGCTTG" <>
     "TCCCTGAACTGCTTTCTACATTAAGCCCGTCATTCAGAGTCGGTTGCACG"
  |> to_charlist
y2 = "TGGATTCGCCGTTCTTCTGACACCCCTCGAATAGTACTAAACGAGGAGCC" <>
     "AGATCATTGTCCTTAAGATCCGGAGGCCATGCCCGGGAATTTCGTAGGCC"
  |> to_charlist

Elixir uses recursion for looping so we need to think of our base cases and go from there. We’ll be working from the start of the sequence and handling the rest as we go.

First implementation details

The first implementation will be naive in that it won’t do any caching of intermediate results. This means it’s not actually using dynamic programming, but it’s a useful step on the way and helps us focus on the problem we’re solving.

We’re also converting our Strings into Charlists so that we can write the code generically for lists. If we wanted this solution to work specifically on Strings, we’d change the pattern matching to match on binaries, but the logic would be similar.

defmodule NaiveLCSLength do
  def lcs_length(x, y)
 
  # case 1, the base cases
  def lcs_length([], _), do: 0
  def lcs_length(_, []), do: 0
 
  # case 2, the heads match
  # Note: this is the reverse of the way our definition defines it
  def lcs_length([head | x_tail], [head | y_tail]) do
    lcs_length(x_tail, y_tail) + 1
  end
 
  # case 3, the heads don't match
  def lcs_length([_x_head | x_tail] = x, [_y_head | y_tail] = y) do
    max(lcs_length(x, y_tail), lcs_length(x_tail, y))
  end
end
 
NaiveLCSLength.lcs_length(x1, y1)

7

This gives us the length of the common subsequence, but it doesn’t give us the sequence, and it does a lot of repeated work that we could avoid.

For example, if we try it on the larger problem, the calculation doesn’t finish in a reasonable amount of time, and it takes a lot of memory.

# The following call ran for over 5 minutes before I killed it
# NaiveLCSLength.lcs_length(x2, y2)
"Result times out"

"Result times out"

So, we need to cache the intermediate results because we have a lot of overlapping subproblems here. Let’s use a Map for this, mapping the prefixes to the longest subquence length found in those prefixes.

Normally these caches use the indexes of the prefix for the key, or they use a multi-dimensional array using those indexes as the indexes into each dimension of the array, but for simplicity, I’m just storing the actual prefix. It’s inefficent but works well enough for our needs here.

defmodule CachingLCSLength do
  # We'll define a helper function to first look in the cache for an answer
  # before computing the answer again, basically memoizing the results
  defp cached_lcs_length(x, y, cache) do
    if Map.has_key?(cache, {x, y}) do
      {Map.get(cache, {x, y}), cache}
    else
      lcs_length(x, y, cache)
    end
  end
 
  def lcs_length(x, y, cache \\ Map.new)
 
  # case 1, the base cases
  def lcs_length([], y, cache), do: {0, Map.put(cache, {[], y}, 0)}
  def lcs_length(x, [], cache), do: {0, Map.put(cache, {x, []}, 0)}
 
  # case 2, the heads match
  def lcs_length([head | x_tail] = x, [head | y_tail] = y, cache) do
    {length, cache} = cached_lcs_length(x_tail, y_tail, cache)
    {length + 1, Map.put(cache, {x, y}, length + 1)}
  end
 
  # case 3, the heads don't match
  def lcs_length([_x_head | x_tail] = x, [_y_head | y_tail] = y, cache) do
    {l_length, cache} = cached_lcs_length(x, y_tail, cache)
    {r_length, cache} = cached_lcs_length(x_tail, y, cache)
 
    if l_length > r_length do
      {l_length, Map.put(cache, {x, y}, l_length)}
    else
      {r_length, Map.put(cache, {x, y}, r_length)}
    end
  end
end
 
IO.puts CachingLCSLength.lcs_length(x1, y1) |> Tuple.to_list |> Enum.at(0)
IO.puts CachingLCSLength.lcs_length(x2, y2) |> Tuple.to_list |> Enum.at(0)

7
62

:ok

Now we have a solution that returns the length of the longest common subsequence and it works on large versions of the problem, we need to update the solution to return the result. We’ll focus on returning one of the solutions rather than try to return all of them.

Notice that each time the heads of both sequences match that’s when the common subsequence gets longer. So, we can just accumulate our answer, adding to it each time we find matching heads.

We need to add the sequence to our cached results so for simplicity I’ll store a Tuple of the length and the sequence.

Storing just the sequence

We could store just the sequence and use it to find the length but we need that information frequently, and in the general case where the sequence is a List, finding the length is $\mathcal{O}(n)$, not $\mathcal{O}(1)$.

If we’re only dealing with Strings then we could use Kernel.byte_size/1 and get $\mathcal{O}(1)$ performance but that wouldn’t count Unicode characters correctly.

This is the same reason why I’m storing the whole prefix, and not the index, or length of the prefix in the keys to the cache Map.

defmodule CachingLCS do
  # Our helper from the previous solution
  defp cached_lcs(x, y, cache, seq) do
    if Map.has_key?(cache, {x, y}) do
      {length, seq} = Map.get(cache, {x, y})
      {length, cache, seq}
    else
      lcs(x, y, cache, seq)
    end
  end
 
  def lcs(x, y, cache \\ Map.new, seq \\ [])
 
  # case 1
  def lcs([], y, cache, seq), do: {0, Map.put(cache, {[], y}, {0, []}), seq}
  def lcs(x, [], cache, seq), do: {0, Map.put(cache, {x, []}, {0, []}), seq}
 
  # case 2
  def lcs([head | x_tail] = x, [head | y_tail] = y, cache, seq) do
    {length, cache, seq} = cached_lcs(x_tail, y_tail, cache, seq)
    new_seq = [ head | seq ]
    {length + 1, Map.put(cache, {x, y}, {length + 1, new_seq}), new_seq}
  end
 
  # case 3
  def lcs([_x_head | x_tail] = x, [_y_head | y_tail] = y, cache, seq) do
    {l_length, cache, l_seq} = cached_lcs(x, y_tail, cache, seq)
    {r_length, cache, r_seq} = cached_lcs(x_tail, y, cache, seq)
 
    if l_length > r_length do
      {l_length, Map.put(cache, {x, y}, {l_length, l_seq}), l_seq}
    else
      {r_length, Map.put(cache, {x, y}, {r_length, r_seq}), r_seq}
    end
  end
end
 
IO.puts CachingLCS.lcs(x1, y1) |> Tuple.to_list |> Enum.at(2)
IO.puts CachingLCS.lcs(x2, y2) |> Tuple.to_list |> Enum.at(2)

reipito
GGATCGGTTCTCGCACCTCGTAGTGGGAAGCTTGTCCTAAGTCACATGCCCGATTTCGTGCC

:ok

Now that we have a working solution, we can consider some improvements we could make.

We’re only returning one solution when there might be multiple. Depending on what this is used for, that might be important, so we could modify our implementation to keep track of all the solutions. This might involve reworking how we calculate the sequences to instead use the cache after the fact to calculate them all.

Handling Tuples for the keys and values in the cache are complicated and easy to get wrong. We could consider creating a structure to hold our cache keys and state, and better indicate what the various values are by choosing descriptive key names.

We don’t need to hold the entire cache the whole time, so we could look at ways to prune the cache whenever we have matching heads. This might involve restructuring how the cache is stored since we don’t have access to the indexes that we’d need in order to remove unused rows of the table we’re building.

This solution isn’t tail-recursive. The Elixir/Erlang VM does tail call optimization, and we’re not taking advantage of that here. With some thought, we could probably get to a tail-recursive version, though in Elixir/Erlang, it may not be needed.

I leave these as an exercise for the reader, or my future self.

How did the candidate do? §

Let’s look at this solution as if it was the answer given by an interview candidate? What can we say about their solution and how they approached the problem?

Positive Aspects §

• They know about dynamic programming which means they either learned it on their own, or were introduced in a formal setting like a Computer Science program at university.
• They were able to describe when dynamic programming is a valid approach to a problem, i.e. when the problem has optimal substructure and overlapping sub-problems.
• Rather than going straight to the optimal solution, they worked up from simpler implementations so they could prove their understanding of the problem without overly complicating things prematurely. They were also able to show where their simple solution failed.
• They explained their solution as they went along, and were able to justify each choice along the way.

Negative Aspects §

• The choice of language doesn’t work well with the problem. If this was for a position that didn’t use Elixir, I’d question their judgement picking a language that makes the problem harder.
• They didn’t go straight to the optimal solution and took longer to get to it, “wasting” time on a naive solution that wouldn’t solve the problem. (I’ve had interview trainers who say this indicates a less senior candidate. I disagree.)
• A better version of the previous criticism would be, because they spent time starting with the naive solution, they maybe didn’t have time in the interview to get to the correct solution. This could indicate bad time management skills.
• They didn’t actually solve the general case of returning all the sequences that are equally the longest common subsequence.

These are the things I see. I’m sure others would come up with more or different critiques.

What are we actually trying to find out? §

I think my previous conclusion still stands:

What we’re trying to answer with these tests is, can this person program, and how do they write, document, and explain their code as they go. In some ways this might be better served by a short test outside of the interview setting and then a code review session with the interviewer where the candidate walks them through the code, and they have a conversation about it. Is that possible to cheat? Sure, but it will come up in the review. If the person doesn’t understand the code, isn’t able to defend their decisions, then it’s going to be obvious.

This sort of lower stress environment would also help with neurodivergent candidates, e.g. those with adult ADHD or autism. Those people tend to have a harder time getting through these sorts of tests.

In a real work environment, coding isn’t the majority of the work anyway. It’s thinking about and discussing what needs to be built. Those skills are better displayed in a code review setting.

I’ve since had interviews where there was a take home test and a code review session, and while I feel like I did better with that, I also didn’t get that job offer. So they’re clearly not a complete solution either.

My take home test experience §

I forget the details of the test, except that it was some sort of event processing system with multiple producers and multiple consumers. I had to choose a data store and could write it in whatever language I wanted. I chose Rust (because it was a Rust job) and SQLite for the database.

My reasoning for choosing SQLite was to keep things simple for anyone who wanted to run the code. What I didn’t know at the time is how terrible the SQLite default settings are, and that to get something useful out of it, you need to make changes to those defaults. Had I known that, I wouldn’t have run into the multiple problems that I did which sabotaged my solution (mostly around database locking).

Should I have gone with Postgres instead? Maybe, but I was trying to keep things simple for a toy example. I think the interviewers also thought I was suggesting SQLite as a full scale production solution, which I wasn’t, but that might have been a failure to communicate on my part.

The takeaway? §

I wrote this mainly as an exercise to refresh my memory on dynamic programming solutions.

But I still think about how this whole process works, and wonder about how we could improve things so that we’re not just optimizing for “people who are capable of holding facts and algorithms in their head” and excluding those people who don’t do well in the artificial environment of the coding interview.

Returning to Seth Corker’s post, he suggests focusing on a problem related to the job being hired for.

Interviews that value the interviewee and focus on problem solving with relevance to the day-to-day job are far more valuable for everyone involved. Make your questions relevant to the position you want to fill to really find a good fit for the role. If a candidate doesn’t know how to solve a given problem, why? Do they have the skill-set but are under pressure? Do they have strengths in other areas?

All of these things are hard to pull out of a thirty minute coding test, but I know we can do better.