A somewhat typical but not-so-great technical interview question

Assume that you are in a technical interview for a software engineering position, which usually lasts from 45min to 1h, and you are asked to provide an efficient algorithm to solve the following problem:

Given a vector/array X of N floating-point numbers, find the contiguous subvector/subarray of X with the maximum sum.

As a great interviewee, you first ask questions to clarify this problem: What if all the numbers in X are positive? The solution is trivial then as the whole vector is the solution. What if all the numbers in X are negative? The solution is trivial again as the empty vector with the zero sum is the solution (may need to be given). The remaining case is what if X contains both negative and positive numbers as well as zero. This is the non-trivial case that needs an efficient algorithm.

This problem is actually a well known problem, called the maximum subarray problem or the maximum subvector problem. Refer to the Wikipedia entry here [1] for more details.

This problem is somewhat popular as a technical interview question for hiring software engineers. Many technical interview preparation sites refer to it. The Web has lots of resources for it. For example, Google returns 10s of 1000s of search results for the search query "maximum subarray problem interview".

In this article, I will make the case that this problem, though a great problem with real applications, is not a good technical interview question. I will refer to the history of this problem to provide evidence for my case.

For the history of this problem, I will refer to the 1st edition of the Programming Pearls book by Jon Bentley. If you have not read this book, I would highly recommend it; it is full of useful insights on the art and practice of programming. Jon Bentley is also a master expositor. If you do not have this book, you may instead want to refer to the Wikipedia article for this problem and its history.

Jon Bentley mentions four names in the history section for this problem. Each name refers to a world-class scientist and/or algorithms expert. Each name is/was also a professor at a top USA university. You can google these names yourself; each has a Wikipedia article.

1. Ulf Grenander was a statistician and professor of applied mathematics at Brown University, USA. He contributed to many areas of mathematics, published many books and research papers, gained 1000s of citations to his research publications.
2. Michael Shamos is a professor of computer science at Carnegie Mellon University (CMU). He is one of the founders of the field of computational geometry [2], a field rich with lots of sophisticated insights and algorithms about geometry and computer science!
3. Jon Bentley is a computer scientist. He was a professor of computer science at Carnegie Mellon University. His contributions include the k-d tree data structure, multiple key algorithms, and the Programming Pearls books. He was also an advisor to multiple well-known computer scientists (see the Wikipedia entry for the famous students of his).
4. Jay Kadane is a professor of statistics at Carnegie Mellon University. He has many research contributions and 1000s of citations to his research publications.

Here is how Bentley describes the search for the optimal solution to this problem. I am of course rephrasing the description by Bentley.

Ulf Grenander was working on a pattern-matching problem. The problem involved finding the maximum-sum submatrix of a given matrix (which can be represented using a 2-dimensional array in a computer program). To gain more insight into this problem, he simplifies the maximum-sum submatrix problem to the maximum-sum subvector problem, i.e., reducing the dimensions from two to one. For the now simplified problem, he first designs the cubic-time algorithm (Alg1) but then improves it to the quadratic-time algorithm (Alg2).

Grenander describes his problem to Michael Shamos. Shamos overnight designs the divide-and-conquer algorithm (Alg3). Shamos also shows the problem to Bentley. Bentley thinks Shamos's algorithm is probably the best.

A few days later Shamos presents the problem, its history, and his algorithm in a seminar at CMU. Jay Kadane, who was in the audience, proposes the linear-time and optimal algorithm (Alg4) within 1 minute. Kadane's algorithm is the efficient algorithm expected as the answer for the original interview question. His algorithm is also very simple, taking only six lines in the Python programming language, as given in the Wikipedia article [1].

Here is a table to summarize this history. The 'Time Complexity' column refers to the time complexity [4] of the algorithm proposed. The 'Time to Solution' column refers to how much time each designer is known to have taken to propose his algorithm.

The software code from Bentley's book is at Github. In particular, the software code for this problem is here [3]. You can find the code for each of the algorithms Alg1-Alg4 there too.

Now suppose you were the interviewer. How would you rate the performance of each of these people on this problem? Grenander, Shamos, and Bentley could not find the linear-time algorithm; they probably also took more time than allowed in a typical interview. Kadane, on the other hand, not only finds the linear-time algorithm but he does so within a minute!

Now I am hoping you will agree with me that these people are extremely smart and successful people; they, especially Shamos and Bentley, are also world-class experts on algorithms. Given their achievements and impact so far, I hope it is easy to see that their performance on this problem is not an indication of anything useful about these people in a technical interview setting.

Now suppose you were interviewing a software engineer candidate and you asked this question. How would you rate the performance of the candidate if s/he fails to find the linear-time algorithm? Is it an automatic 'no hire' decision? What if s/he does find the linear-time algorithm? Is it an automatic 'hire' decision? Given the history of this problem, I hope your answer to both decision questions is a no; I think it is simply not fair to judge either way.

I know as an interviewer you will make your decision based on many factors that you will observe in a technical interview and 'finding the expected solution' is only one of these factors, albeit an important one. I am of course oversimplifying the situation so that we can focus on the core of my argument.

What is the learning from this problem? At a high level, I think the following is a good start. I am planning to cover a longer list in an upcoming article. As an interviewer, I think you should

• Review the history of an interview question, especially if you have not come up with the question yourself. As discussed in this article, the history may contain surprises.
• Not ask questions that are puzzles, trick questions, yes/no questions, definitions, famous questions, and the like. I think the maximum subarray problem is or close to a trick question; it is also a famous interview question now due to its popularity on the interview preparation sites.
• Not ask a question that you have not solved yourself. Especially avoid any questions (like the maximum subarray problem) whose solutions look (really) simple after you have seen the solution.

I hope this article has provided some evidence that the maximum subarray problem should not be asked in a technical interview.

References:

1. Wikipedia article for the maximum subarray problem: https://en.wikipedia.org/wiki/Maximum_subarray_problem
2. A (personal) history of computation geometry by M. Shamos: https://euro.ecom.cmu.edu/people/faculty/mshamos/1999EarlyYears.pdf
3. Code for this problem: https://github.com/alxn/ppearls/blob/master/part-2/column-8/maxsum.c
4. Note that the time complexity of an algorithm describes how much time an algorithm takes, usually in terms of some problem parameters (e.g., the size of the array N as in this problem). To express time complexity, computer scientists use the O-notation, as in the table above. For the sake of (over)simplicity, the O-notation roughly means this: An algorithm that takes O(X) time roughly means the algorithm takes X steps to return its result.

Note (Jan 1, 2024): I had to revise this article and add images again as it seems LinkedIn lost the original formatting and images.

Disclaimer: This article presents the opinions of the author. It does not necessarily reflect the views of the author's employer(s).