Coding Interview: The Game Plan

I am doing interviews few times a year, and it's probably not enough[1]. Opportunities aside, I learn a valuable lesson every time.

Interview pressure uncovers weaknesses. Mine are overcomplication, impatience and panic:

• I somehow expect the problem to be hard. So, I dismiss valuable cues and intuitions if they look too obvious.
• If I feel a hunch, I dive in without full understanding. I keep stepping on this rake... and solving a wrong problem!
• I the problem sounds intimidating, I panic and freeze, not knowing where to start.

Brute-force

To compensate for these weaknesses, I now start with a simplest solution that comes to mind. I work on a naïve solution first, clarifying my understanding, and then brainstorm ideas to improve it.

Structuring your work this way reduces the cognitive load when you start working on an improved solution.

This is an intuitive and well-recommended technique. However, I feel that candidates are afraid to look inexperienced and skip this step. As an interviewer, you may want to offer your candidate to start easy.

The Game Plan

It helps to mentally structure the interview into phases. The opening is important as it sets the tone, and brute-force can help you get through. Early phases are head-up: collaborate, learn and explore. Late phases are head-down: focus and deliver.

The game plan also helps manage your time and deliver a solution before the interview is over.

Interview Pearls: Interleave array in-place

I got this problem in the real interview, and I thought it was interesting. I used the divide and conquer paradigm and came up with a linearithmic solution. After the interview, I could not help thinking about potential linear solution. Read on to see what I found with a little help from the number theory.

Problem Statement

"Given array [a₁, a₂, ..., a_n, b₁, b₂, ..., b_n], interleave it in-place to [a₁, b₁, a₂, b₂, ..., a_n, b_n]"

This problem is also known as "in-shuffle". Think about cutting a deck of cards into equal halves, and interleaving them perfectly, like some of poker junkies can do. It's easy to solve this problem in linear time if you can use additional memory, but the point here is to do it in-place.

Interview Pearls: Count Inversions (Advanced)

I am collecting problems that start easy and then lead to a deep conversation, touching on multiple aspects of computer science fundamentals. These problems are being asked during interviews in the top technology companies, often with a twist to see if you understand the underlying principles and can adapt your solution.

Part 1: Introduction, coding practice and simple solutions
Part 2: Advanced solutions
Part 3: Expert solutions

Here we have an innocent-looking problem that bled me dry (luckily, it was not in a real interview!). Turned out, there are many interesting ways to solve it, and I thought it could be a good illustration to some fundamental algorithms. In the previous post, I covered introductions and simple (but not very efficient) solutions. This is the fun part - we will use advanced concepts like self-balancing trees, binary index trees, and the divide and conquer strategy.

4. Self-balancing BST with counters

So, we implemented our very own BST that can efficiently tell us how many elements are smaller than any given value (solution #3 in the previous post). The run-time complexity is O (n * h), where h is the height of the tree. For a balanced tree, the height is log n, so the complexity is linearithmic. In an unbalanced tree the height can grow up to n, resulting in the quadratic time.

To fight the quadratic time, we can balance the tree to keep its height proportional to log n ^[1] by performing tree rotations when inserting new elements. Tree rotations require amortized ^[2] constant time, so the overall run-time will be still linearithmic. We need to extend our previous solution with the rotation operations and track the number of elements in the both left and right subtrees (so that we can efficiently recalculate these numbers after the rotation).

Interview Pearls: Count Inversions

I am collecting problems that start easy and then lead to a deep conversation, touching on multiple aspects of computer science fundamentals. These problems are being asked during interviews in the top technology companies, often with a twist to see if you understand the underlying principles and can adapt your solution.

Part 1: Introduction, coding practice and simple solutions
Part 2: Advanced solutions
Part 3: Expert solutions

Here we have an innocent-looking problem that bled me dry (luckily, it was not in a real interview!). Turned out, there are many interesting ways to solve it, and I thought it could be a good illustration to some fundamental algorithms. In this first post, we will start with three relatively simple (but not very efficient) solutions. In later parts, we fiddle with binary search trees, indexed trees, merge sort, and even segment trees.

Problem Statement

"Given an array of numbers, count pairs where i < j and numbers[i] > numbers[j]"

I saw this problem also referenced as "Reverse Pairs" and "Count of Smaller Numbers After Self". The result indicates how far the array is from being sorted. It's zero if the array is already sorted, and it's maximum (1 + 2 + ... + size - 1, or size * (size - 1) / 2) if it's sorted in the reverse order. Another way to look at this; the result is the number of swap operations required to sort the array using the bubble sort algorithm.