A few thoughts on preparing for the algorithmic part of an interview

A tangled scribble straightening out into a flowchart of shapes

Hi everyone! Petr Korobeinikov here again, tech lead for the DBaaS for Redis and RabbitMQ (release coming soon) services at #CloudMTS. In this article I want to share some of my experience preparing for algorithmic interviews. Of course, this isn’t an article about hardcore algorithms – it’s more of a rough sketch of a prep roadmap. Still, I hope it’ll be useful to newcomers (and even to a few “old hands”).

Get ready

This is the first and most important piece of advice. If you think that after wrangling databases spanning tens of terabytes, pushing 50-100k RPS to the frontend, and processing tens of millions of messages in Kafka, you’ll be able to carry that experience straight into solving algorithmic problems – I have some bad news for you.

Without preparation, the only place you’ll manage to spin a binary tree is somewhere indecent. It’s a bit like a math or physics exam: you won’t be able to derive the formula if you’re not familiar with the theory and haven’t solved problems ahead of time. And an embarrassing failure awaits you.

How can that be? So many years (decades, even) of experience on the resume, so many (millions of) lines of production-ready code, so many (hundreds of) incidents fixed on the fly – and yet, here we are. That’s because you know the system you work with inside out: you know exactly which bolt to tighten, and where, to keep everything running as it should.

That experience won’t help you with algorithms. You won’t be working with a large system, but with a handmade Swiss watch, where everything has to be calibrated with surgical precision.

Write tests

Even if you peek at a ready-made solution, redo it yourself, by hand, and cover it with tests. That will help you understand the edge cases that can come up when solving any given problem.

When solving a problem on LeetCode, use the examples as test data. Try adding your own if you notice the examples don’t cover every case.

If you’re working through or proposing several solutions, don’t forget to copy the original test data. Algorithmic solutions often end up mutating the input data. For example, say you’ve set up two linked lists to merge – after running one algorithm, the original data may already have changed. Here’s a snippet for copying a singly linked list:

func CopyList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    node := &ListNode{Val: head.Val}
    node.Next = CopyList(head.Next)

    return node
}

And here’s how you can copy a binary tree, for example:

func TreeClone(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }

    clone := &TreeNode{Val: root.Val}
    clone.Left = TreeClone(root.Left)
    clone.Right = TreeClone(root.Right)

    return clone
}

If you want to go even deeper, write benchmarks for your solutions. You’ll be surprised how much faster some solutions get once you swap arithmetic operators for bitwise ones.

A separate variable instead of a nested call

While solving a problem, a separate variable is more readable than a nested call, especially for recursive functions:

depthLeft, depthRight := MaxDepth(root.Left), MaxDepth(root.Right)

return 1 + Max(depthLeft, depthRight)

With this approach you don’t need to think about the number of opening and closing parentheses, especially if your editor’s capabilities are limited (for example, Yandex.Contest).

Nothing stops you from dropping the extra variables in your final solution.

Variable names

I think this is going to be one of the most controversial, most debated parts of this article. Try to get the main idea first.

There’s a lot of advice out there on this subject, and most of it applies to production code that describes business processes, where algorithmic approaches are rarely used.

Think through the following variable-naming principles for your solution:

k, v – key/value in foreach loops;
i, j, k – loop counters;
x, y – the value you’re looking for (by analogy with math notation);
out – the sought/output value of a function;
rev – a reversed value, e.g. in palindrome problems;
orig – a copy of the original value;
left, right – the left and right nodes of a tree;
slow, fast – slow and fast pointers;
head, last, prev, next, curr, node, prehead, sentinel – pointer names for working with lists;
top, front, rear – pointer names for working with stacks and queues;
max, min, low, high, mid, pivot – for storing values.

Why does it make sense to use single-letter variables? If their scope is the body of a short function, loop, or condition, a single-letter variable makes the code compact and readable.

What’s wrong with long, spelled-out names? The odds of slipping a mistake into a long name go up, especially when it strings together several consonants (say, width, height, depth versus w, h, d) or several words (maximumRectangleWidth). Your code editor won’t always be able to flag the mistake for you.

What if len is reserved in your language for the length of lists, arrays, and strings? The short name l is easy to confuse with the digit 1. Try replacing len with size where you can.

It might look like I’m contradicting myself in the next example. Let’s imagine a problem, or a class of problems, that requires working with a two-dimensional array. In exactly this kind of problem, iterating in O(n^2), it makes sense to give loop counters meaningful, yet still short and clear, names:

for person := 0; person < len(accounts); person++ {
    sum := 0
    for account := 0; account < len(accounts[person]); account++ {
        sum += accounts[person][account]
    }

    if sum > max {
        max = sum
    }
}

Referring to indexes that carry semantic meaning makes your code far easier to follow for problems like this, compared to faceless i and j used as indexes.

Here’s another example illustrating how readable well-chosen loop-counter names can be:

for row := 0; row < n; row += 1 {
    for col := 0; col < n; col += 1 {
        board[row][col]
    }
}

When solving a problem, spend a bit of time choosing your variable names. A well-chosen name makes the code more understandable, the problem-solving process simpler, and finding a mistake faster.

A tangled solution

If a solution looks tangled, it’s most likely neither the most efficient nor the most correct one. Take, for example, checking whether a number is a palindrome:

if x < 0 || (x%10 == 0 && x != 0) {
    return false
}

rev := 0
for x > rev {
    rev = rev*10 + x%10
    x /= 10
}

return x == rev || x == rev/10

This solution uses a large number of checks and conditions, and getting them right during an interview is always hard. And mind you, this happens to be the official LeetCode solution to the problem.

A more elegant solution:

rev, d, orig := 0, 0, x

for x > 0 {
    x, d = x/10, x%10
    rev = rev*10 + d
}

return orig == rev

While preparing, try to look for the most elegant solution: it’s easier to understand, remember, and reproduce.

The multiple assignment operator

If the language you’re solving problems in has a multiple/destructuring assignment operator, try using it, as long as the number of variables doesn’t exceed, say, three:

head.Next, prev, head = prev, head, head.Next

This saves you lines of code and gives a clearer picture of the action than, say, a stack of assignments written one under another.

There are cases where, having just learned what the = operator can do, people try to use it everywhere. Let’s look at an example of incorrect usage, using Kadane’s algorithm:

// Incorrect usage: the curr variable should be used after assignment
for i := 1; i < length; i++ {
    curr, max = Max(nums[i], curr+nums[i]), Max(max, curr)
}

Correct usage:

for i := 1; i < length; i++ {
    curr = Max(nums[i], curr+nums[i])
    max = Max(max, curr)
}

The increment and decrement operators

To avoid mistakes with operator precedence, use the explicit form i += 1 or i -= 1 instead of the shorthand i++ or i--.

This matters especially if you feel the urge to juggle the prefix (++i) and postfix (i++) forms.

For counters in simple loops, you can use the shorthand form, since in that case it doesn’t affect the order of evaluation.

As a reminder, Go doesn’t have prefix or postfix forms of the ++ and -- operators.

The loop condition as a stand-in for a check

Use this technique carefully, and only to optimize a solution that already exists. In practice, it’s safer to check edge cases up front, cut them off, and then focus your attention on the general solution.

In some situations, you can skip validating the input data.

if head == nil {
    return head
}

Not always, but often, you can fold a check like this into the loop condition:

for head != nil {
    head.Next, prev, head = prev, head, head.Next
}

The same trick applies to checking an array’s length:

if len(nums) == 1 {
    return nums
}

In this situation, the loop body simply won’t execute, since the check is already baked into the loop condition:

for i := 1; i < len(nums); i++ {
    nums[i] = nums[i-1] + nums[i]
}

The example above shows a solution for computing a running sum by modifying the array in place.

Read the problem statement carefully

Make sure to read the constraints described in the problem statement.

For example, if the problem states that the matrix dimensions can’t be smaller than 1x1, you don’t need to check the array length against 0.

Don’t forget about overflow. In some problems, a sum or a product can go out of the range of valid values.

Let’s take an example where there’s a risk of going out of range:

// the sum left + right can overflow int
pivot := (left + right) / 2

// or
pivot := (left + right) >> 1

Here’s how you can try to prevent overflow when looking for the middle element of an array:

pivot := left + (right-left)/2

Working with the binary representation of numbers

Try to remember at least a few patterns for working with binary representation, if not everything.

Remind yourself how to convert numbers from one number base to another.

For example, programmers very often use the inefficient remainder-of-division operation (usually the % operator) to check whether a number is even or not:

func IsEven(n int) bool {
    return 0 == n % 2
}

A much more efficient solution is one of the following:

func IsEvenXor(n int) bool {
    return n^1 == n+1
}

func IsEvenAnd(n int) bool {
    return !(n&1 == 1)
}

func IsEvenOr(n int) bool {
    return n|1 > n
}

Get familiar with solution patterns

Many problems share common approaches. Prepare yourself a set of template solutions, and try to match the right template to whatever problem you’re solving at the moment.

Here are some well-known approaches:

Slow and fast pointers.
Three pointers.
Traversing an array doesn’t have to start from the beginning – it can start from the end, too.
Sentinel/Guard – nodes in lists and trees.
Using binary search.

I’ve included a few links at the end of the article – take a look at them.

Remember how `O(n)` works

One of the most important skills is learning to gauge what’s sometimes called an algorithm’s “speed” – that’s what O(n) asymptotic notation, or big O of n, is used for.

Off the top of your head, what O(n) complexities are there?

O(1)
O(n)
O(log n)
O(n log n)
O(n ^ 2)
O(2 ^ n)
O(n!)

Work out which complexity a given algorithm represents, and in which case. Try to find out at what O(n) various operations in your language’s standard library run.

Remind yourself why O(k * n) = O(n), where k is a constant.

What’s the base of the logarithm in the notation O(n log n)?

Put together a study plan for algorithms and data structures

First and foremost, I’d recommend studying the data structures themselves. It might sound funny, but you should start with the simplest one – the array – and refresh your memory on stacks, queues, and deques. Then move on to singly and doubly linked lists, then to binary heaps and binary trees. It wouldn’t hurt to try implementing a hash table with open and closed addressing yourself.

Once you’re comfortable navigating the structures themselves and their implementations, with a solid understanding of how they’re laid out in memory, move on to the operations on them.

Try removing all duplicate values from an array, removing an element from a linked list, implementing your own queue and stack with max/min support. Traverse a tree level by level and in different orders: inorder, preorder, postorder. Rather than listing every problem here, you can pick your own from the list of problems on LeetCode or other resources, say HackerRank.

Most of the time, a lot of problems have more than one solution – say, a recursive one and an iterative one. Try implementing operations on a structure in several different ways.

What to read?

There are three books that let you dive into the subject. They’re listed here from simplest to most advanced:

Grokking Algorithms, by Aditya Bhargava;
The Algorithm Design Manual, by Steven Skiena;
Introduction to Algorithms, by Cormen et al.

If things are really bad – you don’t know what a linked list looks like, what a binary tree is, or how O(n) works – start with Grokking Algorithms. The material is explained in plain, simple terms. The best choice for a beginner.

Skiena is more for readers who already have some experience.

Cormen is wonderful, but it won’t help you prepare for an upcoming interview. It’s a thick, foundational book full of math. You should work through it as a matter of general education, not right before an interview.

If you thought I’d forgotten about Knuth’s three-volume set (four, four-and-a-half, or is it five by now) – no, I haven’t. Don’t even think about picking up that book to prepare. It’s hard to read without a math background, and even harder to apply in practice. That book is for experts.

Conclusion

Preparing for the algorithmic part of interviews takes time and effort, and some work on yourself. But it also brings a lot of value. If you prepare seriously, one way or another, you will:

get a deeper grasp of your language’s standard library, and probably learn some nuances you’d never applied in practice before;
get practice writing tests and spotting the various edge cases you can’t afford to forget;
work with benchmarks and learn the finer points of using them;
start seeing more optimal solutions to your current problems;
get better at expressing your intent in code;
and, naturally, learn or refresh the core algorithms.

Good luck with your prep! 💪

P.S. Of course, this article is far from covering every aspect of preparing for an algorithmic interview. I invite you to share your impressions of books, courses, and other resources in the comments. I’ll be glad to add the most interesting suggestions to it. Thanks for reading!

Promised links, tucked under a spoiler: