This is the coding topic most interview candidates struggle with | by Minhaz | March 2022

It’s none other than our friend “Recursion”.

Are you disappointed? Did you expect me to throw you some dynamic programming or a segment tree? Maybe those are big problems too – but that’s what I saw several candidates are struggling with it.

I’m talking about a typical programming interview here – an interview where you are given one or more problem statements and you have to come up with an optimal solution (algorithm) and write code for it within 45-60 minutes.

These are usually called “Data Structures and Algorithmic Interviews” and most software companies use this type of interview to hire software engineers from entry level to senior level.

Disclaimer: This article is not affiliated with Google or Microsoft. This is purely my opinion.

Recursion is probably easy to describe but difficult to formulate and code. —Minhaz (Me)

Usually, coding interviews are broken down into two key steps

  • First, the candidate must find an optimal solution for a given problem.
  • Second, the candidate is asked to code the solution live.

Often, I see promising candidates do well in the first part.

They explain the solution well and correctly state the time and space complexity. After that – I ask them to take the next step where I am interested in learning

  • How well can the candidate convert the algorithm into code?
  • To what extent does the candidate formulate the code (design aspect)?
  • And, to some extent, how well the candidate code – code style, language fluency, etc.

I have seen several candidates blocked at this stage. Probably not always true, but I believe

Recursion is hard to visualize, you can’t solve it ad hoc

Looking back, I feel like there are some common mistakes that many candidates make. In this article, I’d like to take a moment and share my 2 cents on how they could be avoided.

Let’s talk about the problem and the solutions!

I will use the ACL problem as an example to demonstrate the issues.

You are given a root node of a binary tree and two other nodes. The problem is to find the lowest common ancestor of the two nodes in the given tree.

Once the candidate has described the solution verbally and explained the temporal and spatial complexity, the usual conversations would be.

Interviewer: That sounds about right, I’d like to see you code. Don’t hesitate to start. Also, feel free to simply define the data type, interface, and LCA implementation.

And then they start coding with a starting skeleton like this:

Skeleton code to find the lowest common ancestor

Here’s a series of mistakes candidates make – all of which can be avoided.

Candidate: First I need to find the path of the two nodes from the root.

[1] One-shot search — Complex over-optimization

Sometimes the candidate tends to solve the whole problem in one run.

Candidate: Since both nodes are in the tree, I can try to follow the path of both nodes from the root node in one traversal – because I have to traverse the whole tree. In this way, we avoid several crossings.

Problems:

  • This does not improve the worst-case complexity, it remains O(N).
  • The candidate ends up trying to write complex, non-modular code. This does not present good design signals.
  • Quite often, candidates get stuck with complex code and cannot complete it.

All of these elements give the wrong signals to the interviewers who are evaluating the candidate.

Example of complex code, candidates sometimes end up writing trying to find the path of two nodes at once. The code snippet is only partially complete – but should give some idea of ​​the complex solution I’m referring to.

This is very much related to a general point that I tried to make in this article.

[2] Not knowing what the recursive function should do

One way to solve this problem is to find the path from the root node to the individual target nodes and then analyze those paths to determine the ACV.

Some candidates do well at designing a modular code structure. And I really like that in an interview with a candidate as well as all the other engineers I work with. This often requires: Take a step back before starting to write code.

I generally feel good at this point, but then I see some candidates jumping into writing code without formulating exactly what the recursive function should do.

Another code skeleton that does good for initial code modularization.

Although I agree that this is a good start (from an interface point of view) – if you continue without formulating “what this function will do”, you risk taking ad hoc routes.

I’ve seen some applicants struggle with how to return this std::vector at different levels of recursion. Some end up trying to solve this problem iteratively inside the function etc. Some end up realizing that it might be easier to pass the vector as an output parameter.

But there is a ticking clock. Formulating what the function should do could help save a lot of ticks.

[3] Not thinking about the exit condition first

This is probably very much related to the previous point. This isn’t something new, it’s probably written all over the place as a rule of thumb when thinking about recursive function.

Just as a “while” loop must have a place to stop, a recursive function must have a “base case”. The first major rule of recursion is that there must be an endpoint. – by Colton Kaiser.

And I agree, thinking about the final or base condition will help you better formulate the overall function. Think about it before writing code. In this example, you want to quit recursive calls if you find the target or a leaf node. Also, in the recursive chain, you want to know if you have already found the target in the child subtree. One way for a function call to tell the parent function call is to return a Boolean value.

Once the candidate has decided on the exit condition, at some level they force the entire interface to terminate and the next step is to fill in the rest of the function definition.

I think this tip from Colton is super important!

Thinking about the exit condition first helps you formulate the recursive function better. And since this task isn’t completely independent of how the rest of the function is worded, you should think about staying at some level as well.

And then you can fill in the rest of the definition to get a simple, modular and easy to read code.

Although it’s not emphasized enough, I think recursion is a subject that requires practice. Practice not just coming up with a solution mentally, but converting it into code. Even in practice, an inaccurate implementation can lead to problems such as Stack Overflow mistakes.

During a technical interview, you are in a much more stressful situation than regular work or writing code on LeetCode – practice can help you weather this storm better.

A general tip (you may have already noticed this throughout this article) is to

Take a step back before formulating code and think first about the interface and the implementation. Maybe draw on a piece of paper. Most of the time, you will still arrive at the correct solution, but it could save you valuable time.

And this is not limited to technical interviews.

Jessica C. Bell